edited by
825 views
2 votes
2 votes

Here My explanation is :

I. We run TM for 1,2,3,4,5....n if it stops in any of these then yes otherwise no

II. We run TM for n steps if it stops yes otherwise no

III. We run TM for n, n+1, n+2.....infinity so if it halts we can say yes but if do not halt we can't say anything because we have to run it infinite number of times

Is my explanation correct?

edited by

2 Answers

0 votes
0 votes
Your explaination for third one is not correct. You can not run it for infinity since there should be some limit( memory limiation) since you are not sure it will halt or not it might be possible it may keep running forever and you are waiting for halting because you condition atleast one is still satisfied. So, third one is not decidable.

Related questions

0 votes
0 votes
1 answer
3
learncp asked Jan 26, 2016
774 views
$L$ is surely decidable if (A) both $L$ and its complement are not recognizable (B) $L \subseteq \{0\}^*$(C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$(D) $L^R$ is decidable