L = {<M> | M is a TM and halts on every input after 5 steps exactly } - is L decidable?

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?

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.

• the simulation M on w can take more than 5 steps. you have no indication how many steps M does on w – Itamar Silverstein Mar 7 '18 at 16:32
• can anyone offer a reduction from Htm maybe? or a more clear proof? – Itamar Silverstein Mar 7 '18 at 16:38
• 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? – Reinstate Monica Mar 8 '18 at 1:26
• 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. – Kyrylo Yefimenko Mar 8 '18 at 10:26
• @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. – Reinstate Monica Mar 8 '18 at 14:17