1
$\begingroup$

$L_1$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on some string$\}$

$L_2$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on all strings $\}$

a) Is $L_2$ a superset of $L_1$ ?

b) Is $L_2$ not co-recognizable and not recognizable ?

(without formally proving)


my attempt

$a)$ $L_2$ is a superset of $L_1$ since all strings are in $L_2$ whereas $L_1$ is some string

$(b)$ $L_2$ is not recognizable because, out of the infinite enumerations of strings, a single one could not halt disproving it from being recognizable.

For not co-recognizable: It can be written like this

$\bar{L_2} = \{ \langle M \rangle \mid M$ is a turing machine and $M$ loops on some string $\}$.

It's not possible to make a recognizer for loops so its instantly not co-recognizable. This is because looping means it never stops so to come up with a recognizer for anything to prove it loops is impossible since we are working with infinite combinations.

Not sure about it being a superset or not and my explanation for co-recognizable

$\endgroup$

1 Answer 1

0
$\begingroup$

If a machine halts on all strings then it halts on some string. Therefore $L_2 \subseteq L_1$.

If a machine halts on some string but not on all strings then it is in $L_1 \setminus L_2$. Since there are such machines, $L_1 \subsetneq L_2$.


The language $L_2$, usual known as TOT, is well known to be $\Pi_2$-complete. In particular, it is neither r.e. nor co-r.e. This can also be proved directly by reducing both the halting problem and its negation to $L_2$:

  • Given a Turing machine $M$ and an input $x$, construct a Turing machine $M'$ which erases its input and then runs $M$ on input $x$. Then $M$ halts on $x$ iff $M' \in L_2$.
  • Given a Turing machine $M$ and an input $x$, construct a Turing machine $M'$ which on input $n$ simulates $M$ on $x$ for $n$ steps, and loops if $M$ halted within $n$ steps. Then $M$ doesn't halt on $x$ iff $M' \in L_2$.
$\endgroup$
2
  • $\begingroup$ $L_2 \subseteq L_1$. Wouldn't $L_1$ be the smaller set as only some strings can get halted on whereas all strings can halted on $L_2$? So I don't understand this statement since it implies $L_2$ subsets $L_1$ $\endgroup$
    – bob
    Jun 16, 2019 at 8:31
  • $\begingroup$ If $\langle M \rangle \in L_2$ then $\langle M \rangle \in L_1$. I'm afraid your intuition is misleading you. $\endgroup$ Jun 16, 2019 at 10:38

Your Answer

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

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