$L = \{ \langle M \rangle \mid L(M) = \Sigma^∗ \}$

Is above problem R.E ?

I found an explanation in one of the websites and I have doubt in few lines of paragraph.

The explanation was

Now, given a halting problem $(\langle H \rangle, w)$, we proceed as follows: We make a new TM say $A$, which on input $x$, just simulates $H$ on $w$ for $|x|$ steps. If $H$ halts on $w$, $A$ goes to reject state. Otherwise it accepts. So, $L(A)=\Sigma^*$ if $H$ does not halt on $w$ and $L(A) =$ a finite set if $H$ halts on $w$. So we can reduce non halting problem to this problem. Hence given language is non R.E

Can someone please explain me how is $L(A) = \Sigma^∗$ if $H$ does not halt on $w$ ? It says if $A$ doesn't halt within $|x|$ steps then $L(A)$ is infinite. How can we say that ? What it TM $A$ halts on $|x+1|$ th step? Even then it will be finite but this explanation considers it as infinite.

I understand how is it finite set if $H$ halts on w but I am not able to understand the non halting part.


1 Answer 1


Assume $H$ does not halt on $w$. To prove $L(A) = \Sigma^∗$ we need to show that $A$ accepts every $x$. Indeed, whatever $x$ is, we simulate the execution of $H$ on $w$ for only $|x|$ steps (a finite, known amount of steps). I.e., we do not simply run that program on its own, we keep an "alarm clock" counting the steps $H$ as it is running, and as soon as it reaches $|x|$ the alarm rings and we stop the simulation. In this way, no matter what $H$ does on $w$, the simulation will always terminate: either because $H$ halts before $|x|$ steps, or because the alarm rings and we abort the simulation.

Now, since $H$ does not halt on $w$ by hypothesis, $H$ will always make the alarm ring. In such case, $A$ accepts $x$ by construction, hence $A$ indeed accepts all inputs $x$.

For the other direction, assume that instead $H$ does halt on $w$. Let's write $k$ for the number of steps that make $H$ halt on $w$. We now need to prove that $L(A) \neq \Sigma^∗$. Take $x = 1^k$: we prove that $A$ rejects it. By definition, $A$ simulates $H$ on $w$ for $|x|=k$ steps, and that's just enough time to make $H$ halt. So, by construction $A$ rejects.

  • $\begingroup$ How can you say that " H does not halt on w" by just simulating for x steps ? If we run the TM for x steps, we can only say that H doesn't halt on w within x steps right ? H may halt on w after x steps. $\endgroup$
    – Ramesh
    Jan 9, 2018 at 19:11
  • $\begingroup$ @RajeshR That's correct: we can't decide whether H halts on w. We can decide another property, namely if x steps are enough for H to halt on w. If x is enough, we are sure H does halt on w. But, as you say, if it is not enough, we can not conclude that H diverges on w (nor that it halts). I can't see the relation to the answer above, though (?) $\endgroup$
    – chi
    Jan 9, 2018 at 19:17
  • $\begingroup$ According to me, non halting problem says whether M does not halt on w or not (yes case being M does not halt on w) and not whether M does not halt on w within x steps . So how are you solving non halting problem(which is part of your proof) by simulating M for just x steps? $\endgroup$
    – Ramesh
    Jan 9, 2018 at 19:32
  • $\begingroup$ @RajeshR I am not solving the halting problem running only x steps -- that's impossible. Can you point me to the line(s) in the answer above which makes you think so? $\endgroup$
    – chi
    Jan 9, 2018 at 19:47
  • $\begingroup$ I think that you are trying to prove by contradiction that " if there exists a recognizer for completeness problem, then non halting problem could be solved. But as non halting problem is known to be non R.E, completness problem is also non R.E" . This is what I could infer from your second paragraph. Maybe I am wrong. $\endgroup$
    – Ramesh
    Jan 9, 2018 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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