The Universal Turing Machine


next up previous contents
Next: Uncomputable numbers
Up: What is computation? The Turing machine
Previous: What is computation? The Turing machine
Back: to main list of student notes

The Universal Turing Machine

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.


next up previous contents
Next: Uncomputable numbers
Up: What is computation? The Turing machine
Previous: What is computation? The Turing machine
Back: to main list of student notes



Jocelyn Ireson-Paine
Wed Feb 14 23:47:23 GMT 1996