Decidablility Turing machine

160 Views Asked by At

Is it decidable whether a Turing machine takes more than 481 steps for some input?

This was asked in one of the exams. I found some solutions but are not clear to me.

1

There are 1 best solutions below

2
On

In $481$ steps the Turing machine can't look at more than the first $481$ positions on the input tape. Therefore, just simulate the first $481$ steps for each of the possibilities for the contents of those positions of the input tape...