Leivant, Daniel M - Alternating Turing machines for inductive languages

lmcs:1115 - Logical Methods in Computer Science, October 1, 2013, Volume 9, Issue 3
Alternating Turing machines for inductive languages

Authors: Leivant, Daniel M

We show that alternating Turing machines, with a novel and natural definition of acceptance, accept precisely the inductive (Pi-1-1) languages. Total alternating machines, that either accept or reject each input, accept precisely the hyper-elementary (Delta-1-1) languages. Moreover, bounding the permissible number of alternations yields a characterization of the levels of the arithmetical hierarchy. Notably, these results use simple finite computing devices, with finitary and discrete operational semantics, and neither the results nor their proofs make any use of transfinite ordinals. Our characterizations elucidate the analogy between the polynomial-time hierarchy and the arithmetical hierarchy, as well as between their respective limits, namely polynomial-space and Pi-1-1.

Source : oai:arXiv.org:1309.5544
DOI : 10.2168/LMCS-9(3:29)2013
Volume: Volume 9, Issue 3
Published on: October 1, 2013
Submitted on: August 27, 2012
Keywords: Computer Science - Logic in Computer Science


Consultation statistics

This page has been seen 74 times.
This article's PDF has been downloaded 127 times.