0
$\begingroup$

Is the following language decidable?

L = {(M) : M performs at least 100 steps on every accepted input.}

I tried to use reduction from the halting problem, but still no dice.

|cite|improve this question
$\endgroup$
2
$\begingroup$

Yes, it is decidable. There is a limited amount of input that any Turing machine could look at in ≤ 100 steps, so you can test a simulation of any given machine $M$ against all of those possibilities.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Next time, consider waiting until the OP reveals what effort, if any, they expended on solving the problem themselves. $\endgroup$ – Yuval Filmus Feb 24 '17 at 3:17

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.