Alternating Turing machines for inductive languages. (English) Zbl 1322.03030

Leivant, Daniel M.

Log. Methods Comput. Sci. 9, No. 3, Paper No. 31, 12 p. (2013).

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.

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

Keywords:

alternating Turing machine; inductive language; hyper-elementary language; arithmetical hierarchy; polynomial-time hierarchy