DOI

We describe Wadge degrees of ω-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ξω where ξ = ω1CK is the first non-recursive ordinal known as the Church-Kleene ordinal. This answers a question raised in [2].
Original languageEnglish
Pages (from-to)67-83
Number of pages17
JournalRAIRO - Theoretical Informatics and Applications
Volume37
Issue number1
DOIs
StatePublished - 1 Jan 2003

    Research areas

  • Hierarchy, Ordinal, Set-theoretic operation, Turing machine, Wadge degree, ω-language

ID: 127140896