'The Word problem in Semi-groups with Cancellation,' pp. 491-505 in Annals of Mathematics, Second Series, Vol. 2, No. 52, September 1950.

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. The present paper studies a version of the halting problem in a traditional area of mathematics.


First edition, journal issue in original printed wrappers, 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). “Turing constructed a finitely presented cancellation semigroup with unsolvable word problem published in 1950. It is reported that he initially thought he had proved the desired result for groups but before presenting his work had realized that it only gave the cancellation semigroup case” (Miller, p. 341). 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. 342). No other copy of this journal issue listed on ABPC/RBH.

“In the 1930s several definitions of computable functions emerged together with the formulation of the Church–Turing Thesis that these definitions captured intuitive notions of computability. Church and independently Turing showed that there is no algorithm to determine which formulas of first-order logic are valid, that is, the Entscheidungsproblem is unsolvable. So it became meaningful to consider whether more standard mathematical questions have algorithmic solutions, and it seems Church encouraged several mathematicians including Emil Post to work on such problems. Indeed Post had also described an equivalent notion of a computing machine, though not in detail, and had anticipated many of these results” (ibid., p. 329).

In 1947 Emil Post and A. A. Markov independently constructed finitely-presented semigroups with unsolvable word problem. This was perhaps the first long standing mathematical algorithmic problem shown to be recursively unsolvable. Post’s construction was based rather directly on a Turing machine with unsolvable halting problem while Markov’s was based on Post’s earlier unsolvability results on “canonical systems” (ibid., p. 336).

Turing had proved the unsolvability of the Entscheidungsproblem in 1936, but further work on unsolvability questions had been interrupted by the advent of World War II, during which he worked as a cryptanalyst at Bletchley Park. 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).

“In 1950 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 = acb = c and ba = cab = 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’ pp. 329-385 in Turing’s Legacy: Developments from Turing’s Ideas in Logic (R. Downey, ed.), 2014. D. Welch, ‘Turing’s Mathematical Work,’ European Congress of Mathematics, Krakow, 2-7 July, 2012, pp. 763-77.

Large 8vo, pp. 245-507, [1]. Original printed wrappers (former owner’s name stamp on front cover, spine sunned). A very good copy.

Item #4644

Price: $1,850.00