zbMATH — the first resource for mathematics

Alternating Turing machines for inductive languages. (English) Zbl 1322.03030
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.
03D10 Turing machines and related notions
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03D70 Inductive definability
Full Text: DOI