Computational Complexity in Non-Turing Models of Computation

摘要

We preliminarily recap what is meant bycomplexityandnon-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 differentresources, and whether or not the computers be instances of differentmodels 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 ofQuantum Physics and Logic/Development of Computational Models 2008—find these ideas both useful and interesting.