22, he was elected a fellow at King ' s on the strength of a dissertation in which he proved the central limit theorem, despite the fact that he had failed to find out that it had already been proved in 1922 by Jarl Waldemar Lindeberg.
In 1928, German mathematician David Hilbert had called attention to the Entscheidungsproblem( decision problem). In his momentous paper " On Computable Numbers, with an Application to the Entscheidungsproblem "( submitted on 28 May 1936 and delivered 12 November), Turing reformulated Kurt Godel ' s 1931 results on the limits of proof and computation, replacing Godel ' s universal arithmetic-based formal language with the formal and simple hypothetical devices that became known as Turing machines. He proved that some such machine would be capable of performing any conceivable mathematical computation if it were representable as an algorithm. He went on to prove that there was no solution to the Entscheidungsproblem by first showing that the halting problem for Turing machines is undecidable: in general, it is not possible to decide algorithmically whether a given Turing machine will ever halt.
Turing machine
An artistic representation of a Turing machine( Rules table not represented)
A Turing machine, was invented in 1936 by Alan Turing who called it an " a-machine "( automatic machine). Happens to be a hypothetical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.
The " Turing " machine The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.
Turing gave a succinct definition of the experiment in his 1948 essay, " Intelligent Machinery ". Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of:... an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part
( 60)