TM decidable or undecidable problem

Question

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.

Answer 1

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.