# The machine could write a symbol on the tape, or delete a symbol from the tape

## Alan Mathison Turing

He graduated in 1934 then, in the spring of 1935, he attended Max Newman's advanced course on the foundations of mathematics. This course studied Gödel's incompleteness results and Hilbert's question on decidability. In one sense 'decidability' was a simple question, namely given a mathematical proposition could one find an algorithm which would decide if the proposition was true of false. For many propositions it was easy to find such an algorithm. The real difficulty arose in proving that for certain propositions no such algorithm existed. When given an algorithm to solve a problem it was clear that it was indeed an algorithm, yet there was no definition of an algorithm which was rigorous enough to allow one to prove that none existed. Turing began to work on these ideas.

Turing was elected a fellow of King's College, Cambridge, in 1935 for a dissertation On the Gaussian error function which proved fundamental results on probability theory, namely the central limit theorem. Although the central limit theorem had recently been discovered, Turing was not aware of this and discovered it independently. In 1936 Turing was a Smith's Prizeman.

Turing's achievements at Cambridge had been on account of his work in probability theory. However, he had been working on the decidability questions since attending Newman's course. In 1936 he published On Computable Numbers, with an application to the Entscheidungsproblem. It is in this paper that Turing introduced an abstract machine, now called a "Turing machine", which moved from one state to another using a precise finite set of rules (given by a finite table) and depending on a single symbol it read from a tape.

Consultar la fuente de esta información