Turing Recognizability of Turing Machines That Accept All Strings

A friend of mine recently mentioned this question to me as something she had thought of. For Turing machine MM let M\langle M\rangle be its encoding. It is relatively well-known that the language

L={M:M is a Turing machine that accepts some string} \mathcal{L}_\exists = \{\langle M\rangle : M \text{ is a Turing machine that accepts some string} \}

is Turing recognizable but not decidable. The question was whether the language

L={M: M is a Turing machine that accepts all strings} \mathcal{L}_\forall = \{ \langle M\rangle : \text{ M is a Turing machine that accepts all strings}\}

is recognizable or not. Here is the proof that it is not recognizable that I wrote to my friend in response.

Let's assume that L\mathcal{L}_\forall is recognizable, and a Turing machine TT recognizes it. This means for any Turing machine MM that accepts all strings, T(M)T(\langle M\rangle ) will halt eventually in an ACCEPT state.

Conversely, if T(M)T(\langle M\rangle ) either does not halt, or halts in a REJECT state, it means MM does not accept all strings.

Let s0,s1,s2,s_0, s_1, s_2, \ldots be an enumeration of all strings for the alphabet we're working with.

Let's build a Turing machine QQ as follows. QQ takes as input two strings, first M\langle M\rangle , the encoding of a Turing machine, and then xx , any string. (It's easy to show that "multi-input" Turing machines are equivalent to Turing machines, so using them here just allows simplicity in our notation without weakening the result.)

The first thing QQ does on input M\langle M\rangle and xx is to find ii such x=six = s_i (this is know as a "ranking" algorithm, and is rather simple in this case.) After that, QQ simulate T(M)T(\langle M\rangle ) and executes at most ii steps of it. (Run until it halts or ii steps are executed.)

Three things can happen:

Now let's construct a Turing machine QQ' , which takes as input any string xx . Q(x)Q'(x) simply runs Q(Q,x)Q(\langle Q'\rangle , x) . The fact that QQ' can use Q\langle Q'\rangle is related to Kleene's recursion theorems, and is the fundamental idea behind most results like this one (Godel's incompleteness theorems, the halting problem, etc...) In other words, Turing machines can reference their own encoding. (On a related note, look up "quines", programs that generate their own source code without reading any input. There are some really clever ones out there!)

Is Q\langle Q'\rangle in L\mathcal{L}_\forall ? Let's look at the two possibilities:

Q\langle Q'\rangle is in L\mathcal{L}_\forall : then QQ' must accept all strings. That means for any string sis_i , we must have Q(Q,si)Q(\langle Q'\rangle , s_i) halt and return ACCEPT. There are two possibilities for Q(Q,si)Q(\langle Q'\rangle , s_i) to halt in an ACCEPT state:

First is if T(Q)T(\langle Q'\rangle ) halts and and REJECTS Q\langle Q'\rangle within ii steps. This would mean that QQ' does not accept all strings, which is an immediate contradiction of our assumption for this case.

Second is if T(Q)T(\langle Q'\rangle ) does not halt within i steps. Since Q' is assumed in this case to accept all sis_i , this means T(Q)T(\langle Q'\rangle ) can not halt within i steps for any i0i \ge 0 . In other words, T(Q)T(\langle Q'\rangle ) does not halt at all. However, since T was supposed to recognize L\mathcal{L}_\forall and Q\langle Q'\rangle is assumed to be in L\mathcal{L}_\forall in this case, this is a contradiction, because TT must halt on Q\langle Q'\rangle . So Q\langle Q' \rangle can not be in L\mathcal{L}_\forall .

Now, assume Q\langle Q'\rangle is not in L\mathcal{L}_\forall . This means QQ' does NOT accept all strings. So there exists some string sis_i for which Q(xi)=Q(Q,si)Q'(x_i) = Q(\langle Q'\rangle , s_i) either never halts, or halts in a REJECT state. Let's look at both cases:

The first one, Q(Q,si)Q(\langle Q'\rangle , s_i) never halting, is impossible, given that for any input, QQ executes a finite number of steps (ii steps of TT plus the overhead of simulating TT , ranking algorithm, etc...). So we can rule this one out.

The second one, Q(Q,si)Q(\langle Q'\rangle , s_i) halting in a REJECT state, means that T(Q)T(\langle Q'\rangle ) halted within i steps in an ACCEPTING state, because that's the only way QQ halts in a REJECT state. But if T(Q)T(\langle Q'\rangle ) halts in an ACCEPT state it implies QQ' accepts all strings! So yet again, a contradiction.

The logical conclusion is that TT can not exist.

Is there a simpler proof?