Alan Turing

Alan Turing

Alan Mathison Turing (1912–1954) was an extremely gifted man, who was influential in the development of computer science and providing a formalization of the concept of the algorithm and computation with his famous Turing machine, playing a significant role in the creation of the modern computer. Turing discovered something that would have delighted Leibniz—he found that it was possible, in principle, to devise one single universal machine that, all by itself, could carry out any possible computation.

Turing first described the Turing machine in his 1936 article On Computable Numbers, with an Application to the Entscheidungsproblem.

The Turing machine is an idealized computing device, consisting of a read/write head (or scanner) with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol (0 or 1, for example). This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation. In the original article of 1936, Turing actually imagines not a mechanical machine, but a person whom he calls the computer, who executes these deterministic mechanical rules in a desultory manner.

The input that is inscribed on the tape before the computation starts must consist of a finite number of symbols. However, the tape is of unbounded length, for Turing's aim was to show that there are tasks that these machines are unable to perform, even given unlimited working memory and unlimited time. The read/write head is programmable. To compute with the device, you program it, inscribe the input on the tape, place the head over the square containing the left most input symbol, and set the machine in motion. Once the computation is completed, the machine will come to a halt with the head positioned over the square containing the left most symbol of the output (or elsewhere if so programmed).

The Turing machine can perform six types of fundamental operations—read, write, move left, move right, change state and halt. A complicated computation may consist of hundreds of thousands, or even millions such operations. Despite the Turing machine's simplicity, it is capable of computing anything that any modern computer can compute.

A short definition of the thought experiment was given by Turing in his 1948 essay, Intelligent Machinery. Referring back to his 1936 publication, he writes that the Turing machine, here called a Logical Computing Machine, consisted of:
...an infinite 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 determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.

Alan TuringAlan Turing played an important role in the creation of first english electronic computers. During the WWII, he worked for the Britain's codebreaking centre (Government Code and Cypher School at Bletchley Park). He devised a number of techniques for breaking German ciphers, and together with Gordon Welchman developed an improved version of the Bomb—an electromechanical machine, that could find settings for the german Enigma coding machine. Later Turing devised a technique for use against the Lorenz cipher, used in the Germans' new Geheimschreiber machine.

Turing's greatest contribution to the development of the digital computer are:
   1. The idea of controlling the function of a computing machine by storing a program of symbolically, or numerically, encoded instructions in the machine's memory.
   2. His proof that, by this means, a single machine (a universal machine), is able to carry out every computation that can be carried out by any other Turing machine whatsoever. He stated: Electronic computers are intended to carry out any definite rule of thumb process which could have been done by a human operator working in a disciplined but unintelligent manner.

Turing was a homosexual, and this resulted in a criminal prosecution in 1952 (homosexual acts were illegal in the UK at that time), and he accepted treatment with female hormones (chemical castration), as an alternative to prison. He died in 1954, several weeks before his 42nd birthday, from an apparently self-administered cyanide poisoning. On 10 September 2009, following an Internet campaign, British Prime Minister Gordon Brown made an official public apology on behalf of the British government for the way in which Turing was treated after the war.