# Superset of another language and recognizability of turing machines

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

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$$.
• $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$
– bob
Jun 16 '19 at 8:31
• If $\langle M \rangle \in L_2$ then $\langle M \rangle \in L_1$. I'm afraid your intuition is misleading you. Jun 16 '19 at 10:38