396 | 36 INTRODUCING TURING’S mATHEmATICS
What happens if we move to variables and ask about a corresponding multiplication in which
2 is replaced by p and 3 by q:
pp−−^11 ×××pp××qp×q×××ppp−−−^111?The answer is still ‘yes’, provided that multiplication commutes: p × q−1 = q−1 × p. While com-
mutativity holds for ordinary multiplication of fractions, it is not assumed for abstract groups.
In the word problem we are given a list of variables, such as p, q, and r, and we can assume that
multiplication by 1 leaves any variable unchanged, that inverses cancel (p × p−1 = p−1 × p = 1),
and that associativity holds: (p × q) × r = p × (q × r). Anything else is given specifically as a rule,
(technically called a ‘relator’).
If we declare that q−1 × p × q × p−1 = 1 is a rule of our game, then the ‘word’ displayed above
will reduce to 1. But what happens if we declare instead that there are two rules, as follows:
rule 1: p × q × p−1 × p−1 = 1 and rule 2: q−1 × p = 1.This is a little more tricky—we have to apply rule 2 before we apply rule 1—but the answer is
still ‘yes’. This leads to an abstract general question: given a finite set of variables and a finite set
of rules, and a ‘word’ obtained by multiplying variables and their inverses, does the word reduce
to 1? The word problem itself is about computability: can we specify an algorithm for answering
the question? In other words, given a set of variables and a set of rules, together specifying a
group G, can we write a computer program depending on G whose input is a word w composed
of copies of the given variables and their inverses, and whose output is ‘yes’ or ‘no’, according to
whether w = 1 in G?
Wilhelm Magnus’s 1932 breakthrough was to demonstrate that there is indeed such an algo-
rithm for solving word problems if there is just one rule. In 1952, Pyotr Sergeyevich Novikov,
working at the Moscow State Teachers Training Institute, achieved a much bigger breakthrough,
proving that no algorithm can exist for the word problem in general. This work owed a dou-
ble debt to Turing. First, non-existence was proved by showing that existence of an algorithm
would in turn imply an algorithmic solution for a problem already known to be algorithmically
unsolvable. It was thanks to Turing’s 1936 paper on computability that such unsolvable prob-
lems were known, and that methods were available for converting between one problem and
another (via Turing machines). Secondly, in 1950 Turing had published his own ‘small-scale’
breakthrough, proving that the word problem cannot be solved for objects called ‘semigroups
with cancellation’. Both pieces of work are cited in Novikov’s landmark publication.^7
As is often the case with first-rate mathematicians, Turing rescued his result from a defective
proof of a stronger one: he thought he had proved unsolvability for general groups (Novikov’s
achievement); his proof contained a flaw but it also contained substantial insights. With semi-
groups, inverses are removed from the picture, and we do not even necessarily have a unit value
(1). So we are left only with associativity [recall: (p × q) × r = p × (q × r)]. In this case we cannot
ask whether a word reduces to 1; instead we ask about whether two words are reducible to each
other. With much less structure to deal with in a semigroup, the solvability of its word problem
is consequently easier to determine: it is unsolvable. This was proved in 1947 by Emil Post and
independently by Andrei Andreyevich Markov. It has been suggested that it was around this
time that Turing first heard about the word problem,^8 although this would seem odd given
his close and long-standing general association with group theory. Be that as it may, he was