All Title Author
Keywords Abstract

Mathematics  2009 

Decision Problems For Turing Machines

Full-Text   Cite this paper   Add to My Lib

Abstract:

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_2(\Sigma_1^1)$-complete to determine whether the omega-language of a given Turing machine is countably infinite, where $D_2(\Sigma_1^1)$ is the class of 2-differences of $\Sigma_1^1$-sets. Secondly, it is $\Sigma_1^1$-complete to determine whether the omega-language of a given Turing machine is uncountable.

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

微信:OALib Journal