Počet záznamů: 1

Computation as an Unbounded Process

  1. 1.
    0368246 - UIVT-O 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
    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