Alternating Turing machines for inductive languages.

*(English)*Zbl 1322.03030In 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.

Reviewer: Stela K. Nikolova (Sofia)

##### MSC:

03D10 | Turing machines and related notions |

03D60 | Computability and recursion theory on ordinals, admissible sets, etc. |

03D70 | Inductive definability |