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.

  • $\begingroup$ Hey Yuval, thanks for help. However the problem ask me if exist a string w. Do I need to switch the problem from w to TM? $\endgroup$ – Gianni Spear Nov 29 '19 at 22:36
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 29 '19 at 22:38
  • $\begingroup$ Yes. I understand. For example If I give to M a string w of 5 character. if M only reads w, at least M runs 5 steps (each character = 1 step). If M runs 3 steps on the string w with |w| = 5, this mean there is not a string w (of the problem question) $\endgroup$ – Gianni Spear Nov 29 '19 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.