0
$\begingroup$

L = {< M > $\mid$ L(M) = M halts on all inputs in atleast 100 steps }.

Answer to this question is given undecidable in my book without any explanation but I think it is decidable.


$\overline{L}$ = {< M > $\mid$ L(M) = M halts on some input in atmost 100 steps }

For the above language, we can feed strings of length ranging from 1-100 (finite amount of strings) and run Turing machine for finite amount of steps (100) on each string and check if at least one of them halts in atmost 100 steps.

So, as the complement of L is recursive, L should also be recursive and decidable according to me.

Where am I going wrong ?

$\endgroup$
  • $\begingroup$ To check if there exists an input which halts in atmost 100 steps, it is enough to check only strings of length upto 100 I guess. For strings of length greater than 100, we can check if it's prefix of length 100 halts in atmost 100 steps or not. $\endgroup$ – Rajesh R Jan 25 '18 at 5:50
  • $\begingroup$ Your $\overline{L}$ doesn't include machines which don't halt at all on some input, so it isn't really the complement of $L$. $\endgroup$ – rici Jan 25 '18 at 6:07
  • $\begingroup$ @rici, Ok. Even if I include it, we check only finite amount of strings for finite amount of steps right ? So shouldn't it be decidable? $\endgroup$ – Rajesh R Jan 25 '18 at 6:16
  • 1
    $\begingroup$ No. The complement of $L$ contains machines which halt in less than 100 steps for some input (which is a finite set of possibilities, as you say) and machines which don't halt for some input. The second part requires a solution to the halting problem. How do you know that a machine doesn't halt ever for some input? $\endgroup$ – rici Jan 25 '18 at 6:18
  • 1
    $\begingroup$ Right. Which is what your book says, no? $\endgroup$ – rici Jan 25 '18 at 6:21
0
$\begingroup$

You have not correctly computed $\overline{L}$. It contains

  • machines which halt in less than 100 steps for some input (which is a finite set of possibilities, as you say), and

  • machines which don't ever halt for some input.

The second part requires a solution to the halting problem, so $\overline{L}$ is not decidable (nor recursively enumerable).

$\endgroup$

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.