Turing's Tape

1936 · Universal Machine · Work 510 of 1,871

Turing's Tape, 1936, Universal Machine

A page of a mathematical journal of 1936, typeset paragraphs reading as grey texture, a printed table of machine configurations ruled into columns in the middle of the page, cream paper laid flat on a grey studio table, even flat light from directly above.

What it was used for
Alan Turing's paper "On Computable Numbers, with an Application to the Entscheidungsproblem" appeared in the Proceedings of the London Mathematical Society, second series, volume 42, pages 230 to 265. The head of the printing gives two dates of different kinds: received 28 May 1936, read 12 November 1936. At the end it gives the address of the Graduate College in Princeton. He states the task himself: it is shown that the Hilbertian Entscheidungsproblem can have no solution. The tape is a means, not the end. Turing compares a man in the process of computing to a machine capable of only a finite number of conditions, which he calls m-configurations. Through it runs a tape, the analogue of paper, divided into sections called squares, each able to bear one symbol. Only one square at a time is in the machine, and only its symbol is the one the machine is directly aware of.
What was new
The centrepiece of the paper is the universal machine: it is possible, Turing writes, to invent a single machine which can be used to compute any computable sequence, if it is supplied on its tape with the description of another machine. Turing was not alone in his result on the Entscheidungsproblem, and says so himself on the second page: Alonzo Church had recently introduced an idea of effective calculability, equivalent to his computability but very differently defined, and reached similar conclusions about the Entscheidungsproblem. Turing therefore added an appendix dated 28 August 1936 outlining the equivalence. Church wrote in his 1937 review that his own result had anticipated Turing's, but that Turing's work was done independently, being nearly complete and known in substance to a number of persons when Church's paper appeared — and it was there that he coined the name "Turing machine".

Further reading