Number of the records: 1
Computation as an Unbounded Process
- 1.0368246 - ÚI 2013 RIV NL eng J - Journal Article
van Leeuwen, J. - Wiedermann, Jiří
Computation as an Unbounded Process.
Theoretical Computer Science. Roč. 429, 20 April (2012), s. 202-212. ISSN 0304-3975. E-ISSN 1879-2294
R&D Projects: GA ČR GAP202/10/1333
Institutional research plan: CEZ:AV0Z10300504
Keywords : arithmetical hierarchy * hypercomputation * mind change complexity * nondeterminism * relativistic computation * unbounded computation
Subject RIV: IN - Informatics, Computer Science
Impact factor: 0.489, year: 2012
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.
Permanent Link: http://hdl.handle.net/11104/0202642
Number of the records: 1