| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428689 | Information Processing Letters | 2009 | 4 Pages |
Abstract
We answer two questions posed by Castro and Cucker (1989) in [1], giving the exact complexities of two decision problems about cardinalities of ω-languages of Turing machines. Firstly, it is -complete to determine whether the ω-language of a given Turing machine is countably infinite, where is the class of 2-differences of -sets. Secondly, it is -complete to determine whether the ω-language of a given Turing machine is uncountable.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
