The Computational Power of Turing's Non-Terminating Circular a-Machines

Autoři: prof. RNDr. Jiří Wiedermann, DSc.
Rok vydání: 2013
Typ publikace: Kapitola v monografii
Periodikum: Alan Turing - His Work and Impact
Projekty: NoSCoM: nestandardní výpočetní modely a jejich aplikace ve složitosti, lingvistice a učení
Bibliografická citace: VAN LEEUWEN, J., WIEDERMANN, Jiří. The Computational Power of Turing's Non-Terminating Circular a-Machines. In: COOPER, B.S., LEEUWEN, J. van, eds. Alan Turing - His Work and Impact. Amsterdam: Elsevier, 2013, S. 80-85. ISBN 978-0-12-386980-7.
ID: 384527

Abstrakt

A variant of Turing's original a-machines --- the so-called non-terminating circular a-machine --- is shown to be computationally equivalent to a model of unbounded computational processes whose computational power reaches up to higher levels of the arithmetical hierarchy.