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.
Asked
Active
Viewed 159 times
0
-
So you think every algo is O(1)? – gukoff Apr 03 '13 at 04:47
-
How is this related to the question I posted? – user55531 Apr 03 '13 at 06:13
1 Answers
1
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...
Robert Israel
- 448,999
-
There are $2^{481}$ possible contents. For each these input strings the Turing machine is simulated. If for some input it takes more than 481 steps , accept. Whats the rejection criterion? – user55531 Apr 03 '13 at 06:10
-
Reject if, after trying all possible inputs, you haven't accepted. – Robert Israel Apr 03 '13 at 07:16