0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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 '13 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 '13 at 8:45
  • 2
    $\begingroup$ Dumping your exercise problem without any own effort is bad style. $\endgroup$ – Raphael♦ Apr 8 '13 at 15:09
  • $\begingroup$ cs.stackexchange.com/questions/3101/… $\endgroup$ – d'alar'cop May 24 '14 at 5:23
13
$\begingroup$

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?

Improve this answer
$\endgroup$

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