Superset of another language and recognizability of turing machines

Question

$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

Answer 1

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