Is the following language decidable?
L = {(M) : M performs at least 100 steps on every accepted input.}
I tried to use reduction from the halting problem, but still no dice.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Cross-posted: cs.stackexchange.com/q/70747/755, stackoverflow.com/q/42428695/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W.♦ Feb 24 '17 at 19:23
Add a comment
|
$\begingroup$
$\endgroup$
1
Yes, it is decidable. There is a limited amount of input that any Turing machine could look at in ≤ 100 steps, so you can test a simulation of any given machine $M$ against all of those possibilities.
-
2$\begingroup$ Next time, consider waiting until the OP reveals what effort, if any, they expended on solving the problem themselves. $\endgroup$ – Yuval Filmus Feb 24 '17 at 3:17
