Turing also showed that he could define a *Universal Turing
Machine*. By writing suitable symbols on its tape, you could program
this to emulate the behaviour (the state table) of any other Turing
machine. In the same way, we can program a computer to simulate coffee
machines, washing machines, and any other system.

Turing then proved the halting problem by considering a UTM program which was to test whether every other Turing machine would eventually halt. By applying this program to itself, he arrived at a contradiction, similar to the one I demonstrated earlier.

Wed Feb 14 23:47:23 GMT 1996