Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable?

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