Answered By : Niel de Beaudrap
Let’s consider the more general problem of machines which stop after at most $N$ steps, for some $N geqslant 1$. (The following is a substantial simplifcation of a previous version of this answer, but is effectively equivalent.) As swegi remarks in an earlier response, if the machine stops after at most $N$ steps, then only the cells $0,1,ldots,N-1$ on the tape are significant. Then it suffices to simulate the machine $M$ on all input strings of the form $x in Sigma^N$, of which there are a finite number.
- If any of these simulations fail to enter a halting state by the $N^{text{th}}:!$ transition, this indicates that any input string starting with $x$ is one for which the machine does not stop within the first $N$ steps.
- If all of these simulations halt by the $N^{text{th}}:!$ transition, then $M$ halts within $N$ steps on all inputs of any length (of which the substring of length $N$ is all that it ever acts on).
Problem Detail: F = { ⟨M⟩ : M is a turing machine which stops on every input in no more than 50 steps }. I need to decide whether F is decidable or recursive enumerable. This “50 steps” part immediate turns the R sign for me, I know that if it was for specific input it was decidable for sure, but here it’s for every input, so I need to check it for all inputs in some way. checking it for infinite inputs makes me think that the problem is co-RE, i.e. its complement is acceptable, but still I’m not sure. I have a feeling it’s decidable, but I don’t know to prove it, Any help? Or maybe I can check the configurations and see that all configurations after 50 steps don’t lead to accept state- how do I do that?
Asked By : Jozef
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3101
