Error message
- Deprecated function: TYPO3\PharStreamWrapper\Manager::initialize(): Implicitly marking parameter $resolver as nullable is deprecated, the explicit nullable type must be used instead in include_once() (line 19 of includes/file.phar.inc).
- Deprecated function: TYPO3\PharStreamWrapper\Manager::initialize(): Implicitly marking parameter $collection as nullable is deprecated, the explicit nullable type must be used instead in include_once() (line 19 of includes/file.phar.inc).
- Deprecated function: TYPO3\PharStreamWrapper\Manager::__construct(): Implicitly marking parameter $resolver as nullable is deprecated, the explicit nullable type must be used instead in include_once() (line 19 of includes/file.phar.inc).
- Deprecated function: TYPO3\PharStreamWrapper\Manager::__construct(): Implicitly marking parameter $collection as nullable is deprecated, the explicit nullable type must be used instead in include_once() (line 19 of includes/file.phar.inc).
= 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
