A friend of mine recently mentioned this question to me as something she had thought of. For Turing machine let be its encoding. It is relatively well-known that the language
is Turing recognizable but not decidable. The question was whether the language
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 is recognizable, and a Turing machine recognizes it. This means for any Turing machine that accepts all strings, will halt eventually in an ACCEPT state.
Conversely, if either does not halt, or halts in a REJECT state, it means does not accept all strings.
Let be an enumeration of all strings for the alphabet we're working with.
Let's build a Turing machine as follows. takes as input two strings, first , the encoding of a Turing machine, and then , 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 does on input and is to find such (this is know as a "ranking" algorithm, and is rather simple in this case.) After that, simulate and executes at most steps of it. (Run until it halts or steps are executed.)
Three things can happen:
- halts within its first steps and ACCEPTS: then REJECTS ;
- halts within its first steps and REJECTS: then ACCEPTS ;
- does not halt within its first steps : then ACCEPTS ;
Now let's construct a Turing machine , which takes as input any string . simply runs . The fact that can use 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 in ? Let's look at the two possibilities:
is in : then must accept all strings. That means for any string , we must have halt and return ACCEPT. There are two possibilities for to halt in an ACCEPT state:
First is if halts and and REJECTS within steps. This would mean that does not accept all strings, which is an immediate contradiction of our assumption for this case.
Second is if does not halt within i steps. Since Q' is assumed in this case to accept all , this means can not halt within i steps for any . In other words, does not halt at all. However, since T was supposed to recognize and is assumed to be in in this case, this is a contradiction, because must halt on . So can not be in .
Now, assume is not in . This means does NOT accept all strings. So there exists some string for which either never halts, or halts in a REJECT state. Let's look at both cases:
The first one, never halting, is impossible, given that for any input, executes a finite number of steps ( steps of plus the overhead of simulating , ranking algorithm, etc...). So we can rule this one out.
The second one, halting in a REJECT state, means that halted within i steps in an ACCEPTING state, because that's the only way halts in a REJECT state. But if halts in an ACCEPT state it implies accepts all strings! So yet again, a contradiction.
The logical conclusion is that can not exist.
Is there a simpler proof?