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

To summarize, Turing machines were to be provided with paper in the form
of a tape. The tape is marked off into boxes and each box can contain at most one
symbol ( Fig. 6.4 ). At each step of the algorithm, the head of this “super-typewriter”
machine can move one space, to the adjacent box on the left or on the right. The
paper tape is assumed to be unlimited in length so that although the machine
has a finite number of symbols and states, it is allowed an unlimited space for
its calculations. This is not to say that the amount of paper attached to such a
machine actually is infinite. At any given stage in any calculation the length of
tape will be finite but we have the option of adding more tape when we need to.
Turing's machine is therefore able to read and write, move left or right along the
tape, as specified by its set of states. The action of the machine is simple: it starts
off in a certain state and looks at the contents of the first box. Depending on the
state and the box contents, it will either erase the contents of the box and write
something new, or leave the box as it is. Whatever it does, it next moves one box
to the left or the right and changes to a new internal state. A simple example of a
“Parity Counter” Turing Machine - which determines if the number of 1s or 0s in
a binary string is even or odd - is described in detail at the end of this chapter.
Computable numbers and computability
With this simple machine, Turing was able to define what was meant by
“computability.” To illustrate this we shall look at the question of “computable
numbers.” We begin by defining what we mean by the term real numbers .
The natural numbers are the whole numbers (no fractions or decimal points)
starting from zero:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 . . .
Natural numbers can be added or multiplied together to produce new natural
numbers. If we want to allow for subtraction, however, we need to include neg-
ative numbers as well. We define the integers as:
. . . , -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7 . . .
Fig. 6.4. The photograph shows a
working model of a Turing machine.