1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Nov 29, 2019 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$ Nov 29, 2019 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$ Nov 29, 2019 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.