1
$\begingroup$

in order for M to belong to L, it must halts on all inputs after 5 steps exactly. is the problem not decidable ? how can it be proved ? I could not succeed in doing a reduction from Htm as the attempt to count M(w) steps failed.

update: apparently the language is in R. can anyone provide a proof?

$\endgroup$
2
$\begingroup$

It is NOT NECESSARY to read the whole input for a Turing Machine to halt.

Imagine a Turing Machine M that receives any input such that it reads anything and moves right exactly 5 times. On fifth step it reaches the accept state and halts.

M belongs to L.

Contrary to what I was thinking before, L is indeed decidable.

Consider all Σ $^5$ configurations of the first 5 cells of the tape. For each of these configurations execute 5 steps. If TM is nondeterministic execute 5 steps for all possible paths. If TM does not halt for some configuration (or execution when TM is nondeterministic) reject. Otherwise, accept.

As Σ $^5$ is finite, L is decidable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ the simulation M on w can take more than 5 steps. you have no indication how many steps M does on w $\endgroup$ – Itamar Silverstein Mar 7 '18 at 16:32
  • $\begingroup$ can anyone offer a reduction from Htm maybe? or a more clear proof? $\endgroup$ – Itamar Silverstein Mar 7 '18 at 16:38
  • 1
    $\begingroup$ In 5 steps a TM can only read at most 9 cells of its tape. So you need only simulate a given TM for all possible states of those 9 cells, which is finitely many. And you need only simulate for 5 steps. How is that uncomputable? $\endgroup$ – Reinstate Monica Mar 8 '18 at 1:26
  • 1
    $\begingroup$ Although reading 9 cells in 5 steps doesn't seem right, the idea is there. I completely ignored the fact that there are finite configurations. I edited the answer. $\endgroup$ – Kyrylo Yefimenko Mar 8 '18 at 10:26
  • 1
    $\begingroup$ @KyryloYefimenko If the tape is bidirectional, the TM can move and then read 4 times to the left or to the right and can read its initial position, so 9 cells. If the tape is unidirectional, the TM can read up to 5 cells. $\endgroup$ – Reinstate Monica Mar 8 '18 at 14:17

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.