Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437226 | Theoretical Computer Science | 2012 | 11 Pages |
We develop a model of computation as an unbounded process, measuring complexity by the number of observed behavioural changes during the computation. In a natural way, the model brings effective unbounded computation up to the second level of the Arithmetical Hierarchy, unifying several earlier concepts like trial-and-error predicates and relativistic computing. The roots of the model can be traced back to the circular a-machines already distinguished by Turing in 1936. The model allows one to introduce nondeterministic unbounded computations and to formulate an analogue of the P-versus-NP question. We show that under reasonable assumptions, the resource-bounded versions of deterministic and nondeterministic unbounded computation have equal computational power but that in general, the corresponding complexity classes are different (Pmind⊊NPmind).