wHITTy & wIlSON | 395
any technical mathematics. Over the course of these letters the salutation progressed from
‘Dear Mr Hall’ to ‘Dear Hall’ to ‘Dear Philip’.
So Turing was active and well connected in the field of group theory. He would surely have
been aware of developments in a branch that has come to be known as combinatorial group
theory, which revolves around a collection of deep questions asked by Max Dehn around 1912,
known as ‘word problems’. Indeed, the first real breakthrough was achieved by Dehn’s student,
Wilhelm Magnus, in 1932—and Magnus visited Princeton in 1934–35, just a year before Turing
arrived there.
Although Dehn asked several related questions, what is known as the word problem is
roughly as follows. We are given, first, a collection of objects that can be ‘multiplied’ together,
and, second, a collection of rules that say when the result of a multiplication simplifies (an
example of such a rule in ordinary arithmetic is the one saying that ‘x × 1 = x’). The problem
is then to find a method for answering ‘yes’ or ‘no’ to the question: does a given multiplication
simplify down to ‘nothing’?
A rough analogy may be drawn with the computer game Tetris. A collection of shapes simpli-
fies if it can be arranged to contain a single continuous row. In the sketch in Fig. 36.3 the bottom
row does not simplify, but the second row does if the descending block column is rotated and
inserted into the obvious gap. A Tetris word problem might be: given a sequence of descending
shapes, can they be ‘multiplied’ (that is, moved into position) so that the whole sequence sim-
plifies to nothing by the time that the last shape has descended?
To get a little closer to actual group theory, suppose we are asked about multiplying together
the following sequence of numbers^12 , 2, 4,^13 , 6,^18 , whose product might be written as
2 −1 × 2 × 4 × 3−1 × 6 × 8−1,with the superscript −1 denoting a reciprocal (or inverse). Does this product reduce to a single
1? This is a word problem, but not a very difficult one! The answer is easily seen to be ‘yes’, and
there is obviously a method or ‘algorithm’ for obtaining this answer because your electronic
calculator will find it.
figure 36.3 A sketch of a Tetris configuration: the second row potentially simplifies.