# TM decidable or undecidable problem

Problem:

Given a TM $$M$$ on the alphabet $$\{0,1\}$$, determine if there is some input on which $$M$$ executes for at least 5 steps.

Is this problem decidable or not?

To check if the problem is decidable or undecidable, I describe an algorithm as follow:

$$A$$: on input the TM $$M$$

1. $$A$$ generates all strings $$w$$ of length at least 5 characters.
2. For each string $$w_i$$, $$A$$ runs $$M$$ on $$w_i$$ and checks whether it performs at least 5 steps. If yes, $$A$$ accepts, otherwise $$A$$ repeats the control on the string $$w_{i+1}$$.

Algorithm $$A$$ could run forever, and so one could not tell whether $$M$$ performs at least 4 steps on some input string. The problem sounds to me undecidable. However I can build a complementary algorithm of $$A$$ (i.e. $$A'$$) and I can build a new algorithm $$B$$ using $$A$$ and $$A'$$ in parallel. In this case the problem sounds to me decidable.

Your problem is decidable. If $$M$$ always executes less than 5 steps, then it never sees more than the first 4 symbols of its input. Hence it suffices to run $$M$$ on all inputs of length at most 4.
• If $M$ runs for at least 5 steps on some string, then it runs for at least 5 steps on some string of length at most 4. – Yuval Filmus Nov 29 '19 at 22:38