TURING, Alan Mathison (1912–1954)

‘The Word problem in Semi-groups with Cancellation’

[in:] Annals of Mathematics Vol. 2, No. 52

Princeton NJ: Princeton University Press, September 1950

Octavo (254 x 175mm); pp. 245–508, Turing at pp. 491–505; Single issue in original wraps

Turing’s last statement on the eponymous ‘Turing Machine’ – the 1936 thought experiment that launched the entire field of computing machinery.

In his 1936 paper 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’. The search for more problems that could be analysed in this way led, in 1947, to the publication of 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.

The word problem is a specific instance of a general type of problem that can be quite simply explained with an example: take a string of letters (a ‘word’), and apply rules about how different words relate (abc=ca, b=cba and so on). The problem is this: can an algorithm be found that will show whether any given word can be transformed into another word?

This was an area of mathematics in which Turing had published his first ever paper, in 1935. 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. With typical 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 – now more notable for its presentation of an updated ‘Turing Machine’ on pp. 493–495.

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.

References: The Turing Guide, pp. 394–397; Alan Turing: His Work and Impact, 343–357; Martin Davis, ‘What is a Computation?’

Near fine condition; spine slightly wrinkled as often.