Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top