The Word problem in Semi-groups with Cancellation.

Princeton: Princeton University Press, 1950.

First edition of Turing’s last paper in pure mathematics, a return to his great work ‘On computable numbers’ in which he had proved that the halting problem – the problem of deciding whether a given Turing machine ever reaches the halting state when provided with a given tape – was undecidable. “Following Turing’s 1936 discovery of the halting problem and how to derive incompleteness from it in On computable numbers, a great deal of work was done by many mathematicians finding ‘natural’ versions of the halting problem in many traditional areas of mathematics…. Turing’s word problem paper is a complicated piece of such work that was carried out by Turing himself; obviously he wanted to reassure himself that the halting problem was ubiquitous in real mathematics, which is the current consensus” (Chaitlin, p. 343).

After the war Turing worked at the National Physical Laboratory before moving in 1948 to Max Newman’s Computing Laboratory at Manchester University. A discussion with his colleague Peter Hilton in the Mathematics Department there in 1949 “touched upon subjects in Alan’s remoter past, the two fields of group theory and mathematical logic which had set his professional career in motion.

“The discussion concerned the ‘word problem’ for groups. This was like the Hilbert Entscheidungsproblem that Computable numbers had settled, but instead of asking for a ‘definite method’ for deciding whether or not a given theorem was provable, it asked for a definite method for determining whether or not some given product of group elements was equal to some other given product; that is, whether some given sequence of operations would have the same effect as some other sequence. Emil Post had given the first new result in this direction in 1943, by showing that the word problem for ‘semi-groups’ was insoluble. The question for groups remained open. Peter Hilton was amazed because:

‘Turing claimed he had never heard of this problem, and found it a very interesting problem, and so, though at the time his principal work was in machines, he went away and about ten days later announced that he had proved that the word problem was unsolvable. And so a seminar was arranged at which Turing would give his proof. And a few days before the seminar he said: ‘No, there was something a little wrong in the argument, but the argument would work for cancellation semigroups.’ And so he in fact gave his proof for cancellation semigroups.’

“The proof required quite new methods, technically more difficult than those of Computable numbers, in order to relate the ideas of doing and undoing operations to the action of a Turing machine. It showed that at any time, even though he was so out of touch, he could revert to being ‘a logician’. It was a great comeback, and yet for him it would not have been coming back, but going back. He spent some more time on the original problem for groups, but he did not dedicate himself to it” (Hodges, pp. 412-3).

Although it failed to settle the word problem for groups, “Turing’s paper played a very important role in developments. Novikov’s 1955 paper containing the first published proof of the unsolvability of the word problem for groups is based on Turing’s result for cancellation semigroups. Moreover Boone’s independent 1957 proof of the result for groups, while based only on Post’s construction, used a new “phase change” idea which was suggested by Turing’s work” (Miller, p. 14).

“In 1953 Turing wrote his last academic research paper in pure mathematics: “The word problem in semi-groups with cancellation”. Given a set with an associative multiplication operation (a semi-group), obeying additionally the cancellation laws ab = ac ➝ b = c and ba = ca ➝ b = c, can there be such, which has a presentation in terms of two finite sets of symbols and of equations, but so that the problem of deciding whether two ‘words’ each made up of a string of symbol multiplicands are in fact equal, is unsolvable? In 1947 such a problem had been shown unsolvable by Post and Markov independently for pure semi-groups. In this paper Turing shows that here too the general problem is unsolvable. As Boone states, this argument was to be the basis of both Boone’s and Novikov’s (independent) proofs of the unsolvability of the word problem for groups” (Welch, p. 776).

W. W. Boone, ‘An analysis of Turing’s “The word problem in semi-groups with cancellation”,’ Annals of Mathematics, 67 (1956), 195–202; G. Chaitlin, ‘Finding the halting problem and the halting probability in traditional mathematics,’ in S. B. Cooper & J. van Leeuwen (eds.), Alan Turing, his work and impact, 2013; A. Hodges, Alan Turing: the Enigma, 1983; C. F. Miller III, ‘Turing machines to word problems’ (ms.unimelb.edu.au/~cfm/papers/paperpdfs/tmtwp-lnl-v41-2013.pdf); P. D. Welch, ‘Turing’s Mathematical Work,’ European Congress of Mathematics, Krakow, 2-7 July, 2012, 763-77.

8vo (253 x 173 mm) pp. 491-505 in Annals of Mathematics, Second Series, Vol. 2, No. 52, September 1950. The entire issue offered here in original printed wrappers, tiny nick to bottom left corner of front wrapper, otherwise very fine and unmarked.

Item #3490

Price: $2,850.00