This is a basic description of the proof…

Every Turing Machine ** T** given input

⎧ | Answer | |

T(n) | ⎨ | |

⎩ | ⊗ |

We begin with the assumption that we can define a Turing Machine ** Decider** that takes another Turing machine

⎧ | [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

Now we create a new Turing Machine ** Liar** that contains a

⎧ | [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

If T(n) would loop forever, the ** Decider** returns False and this causes the

Essentially, the ** Liar** inverts the behavior of

What we are setting up here is The Liar Paradox.

Finally, consider what happens when we apply ** Liar** to

⎧ | [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

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

Therefore a ** Decider** is impossible.

more info…

- Halting Problem (Wikipedia)
- Turing Machine (Wikipedia)
- Proof That Computers Can't Do Everything (The Halting Problem) (YouTube video)
- Turing's Machine (Logos Con Carne blog)