Universal Turing machines

If you’ve ever used a computer you may find the sorts of idealised machines we’ve been considering odd. We have a separate machine for each computational task. We can, for example, “build” a pushdown automaton recogniser for any context free language but what we’d obviously prefer is a machine which takes a grammar and a list of tokens and tells you whether the list belongs to the language, so that we can use the same machine on any language.

Turing’s work predates physical computers so at the time he was writing it really was necessary to have separate machines for each computational task. Turing was aware that this was undesirable though, and so also considered the notion of a universal machine. He had in some sense been anticipated in this regard by Babbage and Lovelace. In Turing’s formulation the universal machine was a Turing machine which took as input a description of a Turing machine and of an input to that machine and told you what the output of that machine would be on that input. He described, in some detail, how to construct such a machine. In this picture there are two Turing machines, the simulator and the simulated. The simulator corresponds roughly to modern computer hardware and the simulated to modern computer software. Because the simulator is universal you only need one computer, not a separate one for each computational task.