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 $\backslash \; T(x)\; \backslash$ 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 $\backslash \; d[T]$. Turing showed that there exists a machine $U$, called a universal Turing machine, with the properties '''$\backslash \; U\; \backslash$ $\backslash \; (\; d\; [T\; ]$, $x\; )\; \backslash$ = $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 $\backslash \; d[T]\; \backslash$. In short, if $\backslash \; U\; \backslash$ 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]]