TOC-Undecidability

Question

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.

Comments

@Ayush Upadhyaya

For P1 and P3 we can't apply rice theorem as ...rice theorem is applied when we are given properties of languages of TM not properties of TMs  am I right ?..For P3 it is RE but not REC ..we have to use interleaved order?

 

---

Also if we are not able to find Tyes and Tno such that Tyes $\subset$ Tno

Then we can't comment about RE / Not RE

L =  {<M> | L(M) is infiinite} is non RE . but we cant find T yes $\subset$  Tno 

Here how you concluded this 

 but since we cannot have TyesTyes such that it should be a proper subset of TnoTno, this is Recursively Enumerable.So, this RE but not REC.

---

reply to the question:

Your conclusion for P2 is wrong since RICE theorem’s 2^nd part is not 2-way.

For @srestha comment:

I think that will be undecidable but REL, since we can go on checking if for any length we have at least 2 strings getting accepted.