Which Turing machine problems are Decidable?

Question

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 :-

Prove that this language is decidable or undecidable

Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable?

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 ?

Answer 1

You can simulate a given Turing machine to a given number of steps. This allows you to decide Problem 1 and Problem 3, by running $M_N$ on the empty type for $N$ steps (or fewer, if it halts earlier).

Regarding Problem 2, assuming that $N$ is in the language if

1. $M_N$ halts on the empty tape, and
2. $M_N$ doesn't halt within the first $N$ steps,

then you can use this language to solve the halting problem (using the same effective enumeration). Given $N$, in order to determine whether $M_N$ halts on the empty tape:

1. Run $M_N$ for $N$ steps. If it halts, answer Yes.
2. Otherwise, use Problem 2 to determine whether $M_N$ halts on the empty tape, but not within the first $N$ steps.

Hence Problem 2 is undecidable.