930 views
2 votes
2 votes

Here is my analysis.

P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes finite and by running TM in an interleaved mode I can decide whether TM M halts on x within k steps.

So, P1 is Decidable or REC.

P2: Here I can have two TM for this say $T_{yes}=\{\epsilon,a\}$ and $T_{no}=\{aaa\}$. This is Undecidable, but since we cannot have $T_{yes}$ such that it should be a proper subset of $T_{no}$, this is Recursively Enumerable.So, this RE but not REC.

P3:I can fix the moves of TM to 99, and only $| \sum|^{99}$ inputs are possible. I can run TM on such inputs in an interleaved way and hence I can decide P3.

Hence, P3 is decidable.->REC.

So, I think here answer must be 1.

Please let me know what's right.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1