Computation as an Unbounded Process

0368246 - ÚI 2013 RIV NL eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GAP202/10/1333
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: arithmetical hierarchy * hypercomputation * mind change complexity * nondeterminism * relativistic computation * unbounded computation
Kód oboru RIV: IN - Informatika
Impakt faktor: 0.489, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0202642