I have an exam coming 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.

  • 5
    $\begingroup$ What have you tried? Here is a hint: what can a machine do in 10 steps on input of size 12? $\endgroup$
    – Shaull
    Apr 8, 2013 at 7:28
  • 2
    $\begingroup$ @Shaull if there should be an answer to this question (and there should), your comment should be it. Can you make it into a short answer? $\endgroup$
    – Pål GD
    Apr 8, 2013 at 8:45
  • 2
    $\begingroup$ Dumping your exercise problem without any own effort is bad style. $\endgroup$
    – Raphael
    Apr 8, 2013 at 15:09
  • $\begingroup$ cs.stackexchange.com/questions/3101/… $\endgroup$
    – d'alar'cop
    May 24, 2014 at 5:23

1 Answer 1


Consider the following hint:

If $M$ is a TM, and it is given an input of length $12$ (for example), but you only allow $M$ to operate for $10$ steps, what can it do with the input?


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