Decision Problems For Turing Machines
Finkel, Olivier · Lecomte, Dominique
Original · EN
We answer two questions posed by Castro and Cucker, giving the exact complexities of two decision problems about cardinalities of omega-languages of Turing machines. Firstly, it is D₂(Σ₁¹)-complete to determine whether the omega-language of a given Turing machine is countably infinite, where D₂(Σ₁¹) is the class of 2-differences of Σ₁¹-sets. Secondly, it is Σ₁¹-complete to determine whether the omega-language of a given Turing machine is uncountable.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.