A ‘late’ Turing paper in which the scientist refines the conceptual framework around his ground-breaking and eponymous creation, the ‘Turing Machine’
It was in 1936 that Alan Turing famously proposed an imaginary device which would manipulate symbols on an infinite strip of tape. With the simple set of rules by which this device operated, Turing was able not only to show that the ‘entscheidungsproblem’ (decision problem) set by David Hilbert was unsolvable, but also to give a formal definition of computability, and to construct a ‘machine’ that could carry out any possible computation. This was a landmark in the history of mathematics – and also stands as the founding moment in the history of modern computing. But it was far from the last word on what came to be called ‘Turing Machines’ - and in his paper published in Annals of Mathematics, Vol 52, No 2, September, 1950, pp 491-505 Turing returns to this problem. The paper shows how their originator had followed developments in ‘Turing Machines’, and offers here his own mature statement on this transformative notion.
In spite of the monumental contributions still to come from Turing – in artificial intelligence, computer programming and morphogenesis – he remained committed to work in pure mathematics, and particular to the refinement of his theory of computing machines. ‘The Word problem in Semi-groups with Cancellation’ constitutes his last substantial discussion of the topic.
This is a fine copy of Annals of Mathematics in its original printed wrappers, very slight browning to paper edges; Strand price ticket on the first leaf of text.
CONTEXT: Turing’s paper responds to Emil Post’s ‘Recursive Unsolvability of a Problem of Thue’, which proposed several improvements on Turing’s original concept and applied it to what is known as the ‘word problem’ in algebraic Group Theory, showing that for a special case the so-called ‘word problem’ is unsolvable. Post’s 1947 contribution was therefore of the greatest interest to Turing, who at this time was back at Cambridge and looking for new problems, following his departure from the project to build the ‘Pilot ACE’ computer. Not only had Post made a major contribution to Group Theory – he had done it by adapting Turing’s own invention. With typical brilliance and bravado Turing quickly believed he had shown that the word problem in general is unsolvable. In fact, Turing’s proof was incomplete, and so he published only this partial result – an improvement on Post’s work, to be sure, but not the full solution that was to be found shortly afterwards by Petr Sergeevich Novikov and William Boone, working in isolation from one another.
