The detailed question is:

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

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 proofe this question (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?

  • $\begingroup$ Please clarify the question. Is the language you asking for: $\{w \in \{0, 1\}^\ast \mid \exists M \text{ s.t. } M \text{ halts on } w \text{ after } \leq |w| \text{ steps}\}$ or rather $\{\langle M, w \rangle \in \{0, 1\}^\ast \mid M \text{ halts on } w \text{ after } \leq |w| \text{ steps}\}$? $\endgroup$ – ttnick Nov 6 '19 at 21:52
  • $\begingroup$ The language is $H=\{⟨M⟩ | \textrm{ M halts after a maximum of |w| steps for some word w} \}$. I don't know what more I should clarify $\endgroup$ – Werlin Nov 6 '19 at 21:58

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.

  • $\begingroup$ Thank you for your answer! So the proof is that simple? :o $\endgroup$ – Werlin Nov 6 '19 at 18:51
  • $\begingroup$ And would the Turing machine be capable of solving the halting problem or the $\epsilon$-halting-problem? $\endgroup$ – Werlin Nov 6 '19 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 Nov 6 '19 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 Nov 6 '19 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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