1
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.