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

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

$\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 $\mathcal{L}_\forall$ is recognizable, and a Turing machine $T$ recognizes it. This means for any Turing machine $M$ that accepts all strings, $T(\langle M\rangle )$ will halt eventually in an ACCEPT state.

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

Let $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 $Q$ as follows. $Q$ takes as input two strings, first $\langle M\rangle$ , the encoding of a Turing machine, and then $x$ , 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 $Q$ does on input $\langle M\rangle$ and $x$ is to find $i$ such $x = s_i$ (this is know as a "ranking" algorithm, and is rather simple in this case.) After that, $Q$ simulate $T(\langle M\rangle )$ and executes at most $i$ steps of it. (Run until it halts or $i$ steps are executed.)

Three things can happen:

• $T(\langle M\rangle )$ halts within its first $i$ steps and ACCEPTS: then $Q$ REJECTS $x$ ;
• $T(\langle M\rangle )$ halts within its first $i$ steps and REJECTS: then $Q$ ACCEPTS $x$ ;
• $T(\langle M\rangle )$ does not halt within its first $i$ steps : then $Q$ ACCEPTS $x$ ;

Now let's construct a Turing machine $Q'$ , which takes as input any string $x$ . $Q'(x)$ simply runs $Q(\langle Q'\rangle , x)$ . The fact that $Q'$ can use $\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 $\langle Q'\rangle$ in $\mathcal{L}_\forall$ ? Let's look at the two possibilities:

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

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

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

Now, assume $\langle Q'\rangle$ is not in $\mathcal{L}_\forall$ . This means $Q'$ does NOT accept all strings. So there exists some string $s_i$ for which $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(\langle Q'\rangle , s_i)$ never halting, is impossible, given that for any input, $Q$ executes a finite number of steps ($i$ steps of $T$ plus the overhead of simulating $T$ , ranking algorithm, etc...). So we can rule this one out.

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

The logical conclusion is that $T$ can not exist.

Is there a simpler proof?