2
$\begingroup$

The question is: Is there a word $w$ on which a TM $M$ halts after a maximum of $|w|$ (word length) steps?

More formerly, is the language below decidable? $$H=\{\langle M\rangle \mid \text{ TM $M$ halts after a maximum of $|w|$ steps for some word }w \}$$

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn't a proof and I have to prove this conclusion (without the Rice's theorem).

My idea was to use the subroutine technique to "convert" the problem into the halt-problem, the $\epsilon$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one - could you help me here please?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Let $M$ be a Turing machine and consider the Turing machine $M'$ that simulates $M$ on an empty input (regardless of the input to $M'$).

If $M$ halts on empty input then $M'$ eventually halts too. This means that there is a word $w$ of sufficiently large length $|w|$ such that $M'$ halts after at most $|w|$ steps (actually, there are infinitely many such words).

If $M$ does not halt, then also $M'$ doesn't halt (regardless of the its input).

Therefore your problem cannot be decidable as otherwise there would be a Turing machine capable of solving the halting problem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your answer! So the proof is that simple? :o $\endgroup$
    – Werlin
    Commented Nov 6, 2019 at 18:51
  • $\begingroup$ And would the Turing machine be capable of solving the halting problem or the $\epsilon$-halting-problem? $\endgroup$
    – Werlin
    Commented Nov 6, 2019 at 18:57
  • $\begingroup$ If the $\epsilon$-halting problem is that of deciding whether a Turing machine halts on empty input, then it would solve the $\epsilon$-halting problem. Not that it makes much difference since if you're given a TM $X$ with input $y$ you can always define a Turing machine $X_y$ that first writes $y$ on tape and then simulates $X$... If the $\epsilon$-halting problem where decidable then so would be the halting problem by simply checking where $M_y$ halts on empty input. $\endgroup$
    – Steven
    Commented Nov 6, 2019 at 19:00
  • $\begingroup$ Okay yeah, that's true. One last question: We also have to proof the correctness. In the examples we had a given TM and a input $w$. Then we had two cases $<M>w\in H$ and $<M>w\notin H$ with H being the set of TMs which I described in the original question. However in this case we don't have a given input $w$. Rather the word isnt really fixed so I don't know how I want to proof the correctness (that the described TM really has the desired behaviour. (if you understand my problem :D) $\endgroup$
    – Werlin
    Commented Nov 6, 2019 at 19:08

Your Answer

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

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