Decidability of a Turing machine always halting in at most ten steps

1.7k Views Asked by At

I've exam comping up soon and I need help with this. Consider the problem:

Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input.

Is this decidable? Prove your answer.

1

There are 1 best solutions below

4
On

Hint: If a Turing machine halts in at most ten steps, then it can read at most ten cells from the input tape.