Decision Problems For Turing Machines

Details Decision Problems For Turing Machines Decision Problems For Turing Machines

2009-09-03

arxiv.org/abs/0909.0736v1

Information Processing Letters 109, 23-24 (2009) 1223-1226

Computer Science

Logic in Computer Science

To appear in Information Processing Letters

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Decision Problems For Turing Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decision Problems For Turing Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decision Problems For Turing Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664455