Wadge Degrees of ω-Languages of Deterministic Turing Machines
Theoretische Informatik, Fachbereich 6, Germany; email@example.com.
2 Novosibirsk State Pedagogical University Chair of Informatics and Discrete Mathematics, Russia; firstname.lastname@example.org .
Accepted: April 2003
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 .
Mathematics Subject Classification: 03D55 / 04A15 / 68Q05
Key words: Hierarchy / Wadge degree / ω-language / ordinal / Turing machine / set-theoretic operation.
© EDP Sciences, 2003