## Turing Machine, the Universal Computer

The 'Turing' machine was developed by the British Mathematician, Alan Turing in 1936. Turing showed that it was possible to construct a *u**n**i**v**e**r**s**a**l* computer which can simulate the action of any other machine.

Let $\ T(x) \$ be the output of a Turing Machine *T* acting on a tape input *x*. The Turing machine can thus be completely specified by writing down how it responds to 0 and 1 on the input tape, for every possible internal configration of the machine. This specification can be written as a binary number *d*[*T*]. Turing showed that there exists a machine *U*, called a universal Turing machine, with the properties

**$\ U \$ ( d[T], $x ) \$ = T (x)**

and the number of steps taken by *U* to simulate each step of *T* is only a polynomial rather than exponential, function of the length of $\ d[T] \$. In short, if $\ U \$ is provided with an input tape containing both a description of *T* and the input *x*, then *U* will compute the same function as *T* would have done, for any machine *T*, without an exponential slow-down.