This is a basic description of the proof…
Every Turing Machine T given input n returns either an Answer or does not halt (enters an infinte loop).
| ⎧ | Answer | |
| T(n) | ⎨ | |
| ⎩ | ⊗ |
We begin with the assumption that we can define a Turing Machine Decider that takes another Turing machine T and n as input.
| ⎧ | [T(n) = Answer] ⇨ True | |
| Decider(T, n) | ⎨ | |
| ⎩ | [T(n) = ⊗] ⇨ False |
If T(n) would return an Answer, the Decider returns True.
If T(n) would loop forever, the Decider returns False.
Note that the Decider does not run T.
Now we create a new Turing Machine Liar that contains a Decider.
| ⎧ | [Decider(T,n) = True] ⇨ ⊗ | |
| Liar(T, n) | ⎨ | |
| ⎩ | [Decider(T,n) = False] ⇨ "Done!" |
If T(n) would return an Answer, the Decider returns True and this causes the Liar to enter an infinite loop.
If T(n) would loop forever, the Decider returns False and this causes the Liar to halt return "Done!"
Essentially, the Liar inverts the behavior of T. If T would return an answer, the Liar loops forever. If T would loop forever, the Liar returns an answer ("Done!").
What we are setting up here is The Liar Paradox.
Finally, consider what happens when we apply Liar to Liar.
| ⎧ | [Decider(Liar[T],Liar[n]) = True] ⇨ ⊗ | |
| Liar[A](Liar[T], Liar[n]) | ⎨ | |
| ⎩ | [Decider(Liar[T],Liar[n]) = False] ⇨ "Done!" |
Remember that Decider is presumed to be perfectly correct.
In the first case, Decider returns True which means that it says Liar[T] halts. That means Liar[A] should enter an infinite loop and never halt. But Liar[A] is the same as Liar[T], and Decider says Liar halts. That is a contradiction!
In the second case, Decider returns False which means that it says Liar[T] loops forever. That means Liar[A] should halt and return "Done!" But Liar[A] is the same as Liar[T], and Decider says Liar runs forever. That is a contradiction!
Therefore a Decider is impossible.