Computation as an unbounded process

作者：van Leeuwen Jan^*; Wiedermann Jiri

来源：Theoretical Computer Science, 2012, 429: 202-212.

DOI：10.1016/j.tcs.2011.12.040

• Arithmetical Hierarchy
• Hypercomputation
• Mind change complexity
• Nondeterminism
• Relativistic computation
• Unbounded computation

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 (P-mind subset of NPmind).

• 出版日期2012-4-20