Computational complexity in non-Turing models of computation: The what, the why and the how
<p>We preliminarily recap what is meant by <em>complexity</em> and <em>non-Turing computation</em>, by way of explanation of our title, 'Computational Complexity in Non-Turing Models of Computation'.</p><p> Based on investigation of a motivating ex...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2011
|
| Subjects: |
| _version_ | 1826306267653603328 |
|---|---|
| author | Blakey, E |
| author_facet | Blakey, E |
| author_sort | Blakey, E |
| collection | OXFORD |
| description | <p>We preliminarily recap what is meant by <em>complexity</em> and <em>non-Turing computation</em>, by way of explanation of our title, 'Computational Complexity in Non-Turing Models of Computation'.</p><p> Based on investigation of a motivating example, we argue that traditional complexity theory does not adequately capture the true complexity of certain non-Turing computers, and, hence, that an extension of the theory is needed in order to accommodate such machines.</p><p>We propose a framework of complexity that is not computation-model-dependent—that, rather, is extensible so as to accommodate diverse computational models—, and that allows meaningful comparison of computers' respective complexities, whether or not the comparison be with respect to different <em>resources</em>, and whether or not the computers be instances of different <em>models of computation</em>.</p><p>Whilst, we suggest, complexity theory is—without some modification—of limited applicability to certain non-standard models, we hope that the ideas described here go some way to showing how such modification can be made, and that members of the non-Turing-computation community—not least participants of <em>Quantum Physics and Logic/Development of Computational Models 2008—</em>find these ideas both useful and interesting.</p> |
| first_indexed | 2024-03-07T06:45:21Z |
| format | Journal article |
| id | oxford-uuid:faafe420-68ea-40de-85da-161dbff1a38b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:45:21Z |
| publishDate | 2011 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:faafe420-68ea-40de-85da-161dbff1a38b2022-03-27T13:07:59ZComputational complexity in non-Turing models of computation: The what, the why and the howJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:faafe420-68ea-40de-85da-161dbff1a38bComputer science (mathematics)EnglishOxford University Research Archive - ValetElsevier2011Blakey, E<p>We preliminarily recap what is meant by <em>complexity</em> and <em>non-Turing computation</em>, by way of explanation of our title, 'Computational Complexity in Non-Turing Models of Computation'.</p><p> Based on investigation of a motivating example, we argue that traditional complexity theory does not adequately capture the true complexity of certain non-Turing computers, and, hence, that an extension of the theory is needed in order to accommodate such machines.</p><p>We propose a framework of complexity that is not computation-model-dependent—that, rather, is extensible so as to accommodate diverse computational models—, and that allows meaningful comparison of computers' respective complexities, whether or not the comparison be with respect to different <em>resources</em>, and whether or not the computers be instances of different <em>models of computation</em>.</p><p>Whilst, we suggest, complexity theory is—without some modification—of limited applicability to certain non-standard models, we hope that the ideas described here go some way to showing how such modification can be made, and that members of the non-Turing-computation community—not least participants of <em>Quantum Physics and Logic/Development of Computational Models 2008—</em>find these ideas both useful and interesting.</p> |
| spellingShingle | Computer science (mathematics) Blakey, E Computational complexity in non-Turing models of computation: The what, the why and the how |
| title | Computational complexity in non-Turing models of computation: The what, the why and the how |
| title_full | Computational complexity in non-Turing models of computation: The what, the why and the how |
| title_fullStr | Computational complexity in non-Turing models of computation: The what, the why and the how |
| title_full_unstemmed | Computational complexity in non-Turing models of computation: The what, the why and the how |
| title_short | Computational complexity in non-Turing models of computation: The what, the why and the how |
| title_sort | computational complexity in non turing models of computation the what the why and the how |
| topic | Computer science (mathematics) |
| work_keys_str_mv | AT blakeye computationalcomplexityinnonturingmodelsofcomputationthewhatthewhyandthehow |