Let $M_0$, $M_1$, $M_2$,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ?
- Given a natural number $N$, does $M_N$ starting with an empty tape halts in fewer than $N$ steps ?
- Given a natural number $N$, does $M_N$ starting with an empty tape halts after at least $N$ steps?
- Given a natural number $N$, does $M_N$ starting with an empty tape halts in exactly $N$ steps?
I've looked some of these similar problems like :-
I've got some idea that $TM$ problems related to $N$ steps, only the cells upto $N$ are significant.
Such problems are decidable, however long input we take.
Hence, I come to the conclusion that $1$st part of my problem will be decidable similar to the reasoning as given above.
Similarly, for $3$rd part, if we check $N$th cell we can say $Y/N$ hence Decidable.
But, I am stuck in $2$nd part.
(What I think is that upto $N$th cell we can check if it halted, making it semidecidable otherwise it will definitely halt after the $N$th cell. Hence, I think it is also Decidable).
Please let me know how much correct progress I made. I don't have solutions for these questions. Need some confirmation ?