Mr. Turing’s amazing machines - The Computing Universe: A Journey through a Revolution - page 106

clarify the foundations of mathematics. Newman's 1935 lectures finished with
an account of Gödel's theorem and made clear that the third of Hilbert's ques-
tions - the Entscheidungsproblem - remained unanswered. In his biography of
Turing, Hodges highlights the question asked by Newman that started Turing
on his journey to Turing machines in the following way:

Was there a definite method, or as Newman put it, a mechanical process which
could be applied to a mathematical statement, and which would come up
with the answer as to whether it was provable? 6

Fig. 6.2. Turing designed his machine
to mimic the behavior of a human
computer.

By using the phrase “mechanical process,” Newman probably meant nothing
more than an algorithm - a set of detailed instructions that leads to the solution
of a problem. However, the phrase must have struck a chord with Turing. He
decided to work on Hilbert's problem that summer but characteristically did not
ask Newman for advice or even tell him about his intentions, nor did he read up
on all the available research literature. This isolation from any of the accepted
modes of thinking about the problem was undoubtedly one of the reasons that
Turing followed such a strikingly unconventional approach to Hilbert's problem.
Turing equated the concept of “computability” with the ability of a very
simple machine to perform a computation. His idea was to imagine a machine
that worked like a human “computer” who just had to follow a set of rules
( Fig. 6.2 ). Instead of a standard sheet of paper, Turing idealized his computer -
who we shall take as female - as using a long strip of paper or “tape” on which
to do her calculations. The tape is broken up into square “boxes,” in each of
which she can read or write a symbol. Using a tape with only one row of sym-
bols to do the calculations - rather than a piece of paper that could accom-
modate multiple rows - would undoubtedly be a very tedious restriction for
a real human computer but it is perfectly possible to arrange to perform the
calculation in this way. Turing imagined that his human calculator would have
a number of different “states of mind” that tell her how she should use the
information that she reads in each box of the tape. Thus our female computer
starts off in one specific state of mind and examines the content of one of the
boxes on the tape. After reading the symbol in the box, she can overwrite the
symbol in the box, change to a new state of mind, and move to consider the
symbol in the next square - to the left or the right. It is her state of mind that
tells her what to do with the symbol she has read - whether it should be used as
part of the process of addition or of multiplication, for example. Turing envis-
aged that a human computer would need only a finite number of states of mind
to complete any given calculation. Having broken down how a human would
actually go about performing the calculation into these simple steps, Turing
then proposed a very simple machine that could mimic all the actions of the
human computer and so work through the algorithmic steps to complete the
same calculation ( Fig. 6.3 ).

Fig. 6.3. This figure illustrates the con-
cept of a Turing machine as “a human
in a box.” The box has no bottom so
the human can read the symbol under
the box.