×

zbMATH — the first resource for mathematics

Hierarchies of recursive \(\omega\)-languages. (English) Zbl 0627.03024
The paper investigates in a self-contained manner the sets of infinite words accepted by Turing machines. The presentation uses the description of recursive \(\omega\)-languages by means of the arithmetical hierarchy as in the previous paper by L. Staiger and K. Wagner [Z. Math. Logik Grundlagen Math. 24, 523-538 (1978; Zbl 0421.03035)].
The first two sections deal with the Borel and the arithmetical hierarchies of \(\omega\)-languages, recalling also several results of the above mentioned paper. In the third section the classes of \(\omega\)- languages accepted by Turing machines under various acceptance conditions are characterized via the arithmetical hierarchy, and the results are compared to the corresponding ones obtained for the classes accepted by finite automata.
The following part is devoted to the presentation of three new hierarchies of recursive \(\omega\)-languages. These hierarchies consist of exclusively open, closed and finite resp. \(\omega\)-languages and form subhierarchies of the arithmetical hierarchy consisting of \(\omega\)- languages of bounded Borel complexity but unbounded arithmetical complexity.

MSC:
03D25 Recursively (computably) enumerable sets and degrees
03D55 Hierarchies of computability and definability
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D10 Turing machines and related notions
PDF BibTeX XML Cite