Daniel M Leivant - Alternating Turing machines for inductive languages

lmcs:1115 - Logical Methods in Computer Science, October 1, 2013, Volume 9, Issue 3 - https://doi.org/10.2168/LMCS-9(3:29)2013
Alternating Turing machines for inductive languagesArticle

Authors: Daniel M Leivant

    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.


    Volume: Volume 9, Issue 3
    Published on: October 1, 2013
    Imported on: August 27, 2012
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 884 times.
    This article's PDF has been downloaded 575 times.