Computational complexity in non-Turing models of computation: The what, the why and the how

Journal article

We preliminarily recap what is meant by complexity and non-Turing computation, by way of explanation of our title, 'Computational Complexity in Non-Turing Models of Computation'.

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.

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 resources, and whether or not the computers be instances of different models of computation.

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 Quantum Physics and Logic/Development of Computational Models 2008—find these ideas both useful and interesting.

Authors: Blakey, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Electronic Notes in Theoretical Computer Science
• Volume: 270
• Issue: 1
• Pages: 17-28
• Edition: Author's Original
• DOI: 10.1016/j.entcs.2011.01.003
• ISSN: 1571-0661
• Language: English
• Keywords: Non-standard/non-Turing computational models; computational complexity; precision
• Subjects: Computer science (mathematics)