| Summary: | <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>
|
|---|