Alternating Turing machines for inductive languages (Q2850842)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Alternating Turing machines for inductive languages |
scientific article; zbMATH DE number 6213051
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Alternating Turing machines for inductive languages |
scientific article; zbMATH DE number 6213051 |
Statements
Alternating Turing machines for inductive languages (English)
0 references
1 October 2013
0 references
alternating Turing machine
0 references
inductive language
0 references
hyper-elementary language
0 references
arithmetical hierarchy
0 references
polynomial-time hierarchy
0 references
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.
0 references
