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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI 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.
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?