Turing machine

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 universal 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.

Bibliography

Category:Introductory Tutorials

Last modified: 
Monday, October 26, 2015 - 17:56