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].
Язык оригиналаанглийский
Страницы (с-по)67-83
Число страниц17
ЖурналRAIRO - Theoretical Informatics and Applications
Том37
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2003

ID: 127140896