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

Authors: J. van Leeuwen, Jiří Wiedermann
Publication year: 2013
Publication type: Kapitola v monografii
Periodical: Alan Turing - His Work and Impact
Projects: NoSCoM: Non-Standard Computational Models and Their Applications in Complexity, Linguistics, and Learning
Bibliographic citation: 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

Abstract

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.