# Completeness problem of TM

$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.

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.

• 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. Jan 9, 2018 at 19:11
• @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 (?)
– chi
Jan 9, 2018 at 19:17
• 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? Jan 9, 2018 at 19:32
• @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?
– chi
Jan 9, 2018 at 19:47
• 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. Jan 9, 2018 at 19:53