50th anniversary of Turing machines

[je...@utai.uucp]

On 12 November 1936, Alan Turing's seminal paper "On Computable Problems, with
an Application to the Entscheidungsproblem" was publically presented for the
first time, at a meeting of the London Mathematical Society. It was later
published in their Proceedings, Volume 42 (Second Series), with several minor
corrections later appearing in Volume 43. In this 36 page paper, Turing first
defined the class of computing machines that now bear his name, put forth the
notion of a universal Turing machine that could compute anything that could be
computed with any Turing machine, exhibited a particular universal Turing
machine, and then used it to demonstrate the existence of an unsolvable
problem, viz. the Halting Problem. This led up to the main result of the
paper (at that time, at least), the solving of a well-known problem in the
foundations of mathematics; he showed that deciding whether a formula
was provable from the axioms of first-order logic was unsolvable.

Thus, the publication of this paper laid the foundations of both theoretical
and practical computer science: many theoreticians are still "running" on
Turing's "hardware", and it's fair to say that Turing's universal machine was
the first virtual machine + interpreter. If ever there was a date that should
be commemorated as the birth of computer science as we now know it,
November 12th, 1936 would seem to be an appropriate choice.

Which means that today (Wednesday, November 12th, 1986) marks our fields's 50th
anniversary.

---Jim des Rivieres

(Another public service announcement brought to you by
the Knights of the Lambda Calculus.)
--

Jim des Rivieres CSNet: je...@ai.toronto.edu
Department of Computer Science ARPA: jeem%ai.toronto.edu@csnet-relay
University of Toronto UUCP: je...@utai.uucp
Toronto, Ontario, Canada, M5S 1A4 {ihnp4,decvax,decwrl}!utcsri!utai!jeem