WADGE DEGREES OF ω-LANGUAGES OF DETERMINISTIC TURING MACHINES

摘要

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 ξ = ω_1~(CK) is the first non-recursive ordinal known as the Church-Kleenc ordinal. Thia answers a question raised in [2].