Alternating Turing machines for inductive languages

DOI10.2168/LMCS-9(3:29)2013MaRDI QIDQ2850842zbMATH OpenOpenAlexFDO

Authors Daniel M. Leivant

Publication date 1 October 2013

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.5544

zbMATH Keywords

alternating Turing machinearithmetical hierarchyhyper-elementary languageinductive languagepolynomial-time hierarchy

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Inductive definability (03D70)

Abstract: 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.

Review text

In this paper, a new semantics of acceptance/rejection of an alternating Turing machine (ATM) is developed. It is proved that the languages accepted by such machines are exactly the inductive languages. An analogue of Post's theorem is established, which states that a language L is accepted by a total ATM iff L and its complement are accepted by some ATM, i.e. iff L is hyper-elementary. The languages in the arithmetical hierarchy are also characterized, namely as those, accepted by ATM with a bounded number of alterations. The approach deals directly with the inductive definitions and does not make use of transfinite induction on constructive ordinals.

Recommendations

• scientific article; zbMATH DE number 4118351
• Possibilities of various types of alternating automata
• On input read-modes of alternating Turing machines
• ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
• scientific article; zbMATH DE number 19775

Cited in

(6)

• Alternation and -type Turing acceptors
• ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
• scientific article; zbMATH DE number 1088283 (Why is no real title available?)
• scientific article; zbMATH DE number 4118351 (Why is no real title available?)
• On log-time alternating Turing machines of alternation depth k
• On input read-modes of alternating Turing machines

This page was built for publication: Alternating Turing machines for inductive languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2850842)