Alternating Turing machines for inductive languages

We show that alternating Turing machines, with a novel and natural definitionof acceptance, accept precisely the inductive (Pi-1-1) languages. Totalalternating machines, that either accept or reject each input, accept preciselythe hyper-elementary (Delta-1-1) languages. Moreover, bounding the permissiblenumber of alternations yields a characterization of the levels of thearithmetical hierarchy. Notably, these results use simple finite computingdevices, with finitary and discrete operational semantics, and neither theresults nor their proofs make any use of transfinite ordinals. Ourcharacterizations elucidate the analogy between the polynomial-time hierarchyand the arithmetical hierarchy, as well as between their respective limits,namely polynomial-space and Pi-1-1