It Began with Babbage (12 page)

He began with the concept of
computable numbers
. What are these? They are “real numbers whose expressions as a decimal are calculable by finite means.”
¹⁷
More simply, “a number is computable if its decimal can be written down by a machine.”
¹⁸
A real number is a quantity that has a decimal expansion, such as 0.25 and 3.14159. Notice, in Turing's definition, the clause “by finite means.” The calculation of a computable number must eventually come to a stop; it cannot go on forever. In the case of a number such as π = 3.141592653 …, although it is an infinite decimal, it is a computable number in that one can compute the first
n
decimal digits in a finite number of steps. At the heart of the matter, for Turing, was to determine how a machine could perform the task that we—intuitively and naturally—call
computing
.

In 1936, the year his paper “On Computable Numbers” was published, the word
computer
still meant a human being who computes. And Turing began by sketching out how a (human) “computer” goes about the task of computing.

It entails reading and writing symbols on paper. But, rather than a two-dimensional paper, imagine a long tape, a “one-dimensional” affair divided into squares (much as a child's arithmetic book in Turing's time was divided into squares). Each square can hold a single symbol.

The computer, being human, has certain obvious perceptual and cognitive traits that affect her behavior. How she behaves at any particular time is dependent on the symbols
she is observing and her “state of mind.” Let us suppose that there is a limit to the number of symbols the computer can observe at any moment—there is a bound, in other words, to her perceptual range. If she wants to observe more symbols, she must take successive observations. We also suppose that, although the number of “states of mind” can be large, there is a finite limit to that number.

We also imagine (Turing wrote) that the computer can only perform very simple or “atomic” operations, and that a computational task is decomposable into a sequence of these atomic operations.

So what are these atomic operations? They must include operations that (a) change a symbol on an observed square on the tape; (b) move the computer's “eye” from an observed square to another, within a certain window of squares bounding the observed square; and (c) change the computer's state of mind. The change of state of mind can accompany either change of symbol on the observed square or change of the observed square.

Turing then drew an analogy between his human computer and a machine that does the work of the person. To each state of the human's mind there is a machine state (so the number of machine states is finite). The machine can scan the tape and “read” its squares. In any one move, the machine can change a symbol on the square being read, or move from one square to another on its left or right, and undergo a change of state.
¹⁹

Turing then claimed that the atomic operations—scanning a symbol in a square, moving to the right or left of the scanned square, writing a symbol or erasing it, changing the state—are all those that are involved in performing a computation.
²⁰
He also stipulated that, at any point in time, the motion of this machine is determined
completely
by the machine state along with the symbol then being scanned.

This is what Turing named a
computing machine
. Suppose, now, that such a machine is given a tape with some “input” set of symbols (or no symbols at all, a blank tape) and, placed in an “initial” configuration, is set into motion. Then, any sequence of symbols printed by the machine onto the tape is said to be
computed by the machine
.

It might be convenient to translate Turing's description into present-centered language:

A computing machine consists of a
tape
that is unbounded in length. Each
square
of the tape can hold one of a vocabulary of
symbols, S
i,
S
j,…. At any point in time, a
read/write head
is positioned on one square of the tape; call it the
current square
. The corresponding symbol is the
current input symbol
. The machine can be in one of a finite number of
states, Q
k,
Q
l, …. The state of the machine at any given time is its
present state
. Depending on the current input symbol and the present state, the read/write head can
print
a symbol on the current square (possibly overwriting the prior symbol) or
erase
the current symbol, move one square to the right or to the left, and place the machine into the
next state
. This next state then becomes the present state of the machine.

Turing called his machine, simply, a computing machine. In present-centered language, it is called, in his honor, a
Turing machine
.

Consider, as an example, a very simple Turing machine (
Figure 4.1
). Its task is to “read” an input string of 0s and 1s written on the tape, and print a 1 on the tape if the number of 1s in the string is odd—0, otherwise—and come to a
halt
(in mathematical jargon, this machine is a parity detector). A special symbol
X
on the tape indicates the end of the input string. The machine replaces the input string with 0s and replaces the
X
with a 1 or 0, depending on the parity.

This machine needs three states.
Qo
corresponds to an odd number of 1s detected in the input string at any point of the machine's operation.
Qe
corresponds to an even number of 1s detected up to any point of the machine's operation. The third state is
H
, the halting state. The machine begins its operation with the read/write head positioned on the square holding the first binary digit of the input string.

Consider, for instance, that the tape has the following input string. The initial position of the read/write head is indicated by the digit in bold type.

… 00 …
1
011011X00 … 0…

The behavior of this Turing machine is defined by what, in present-centered language, is called a
state table
, which looks like
Table 4.1
.

The first row of this table can be read as follows: Given current state
Qe
and input symbol 0, the next state will be
Qe
, an output symbol 0 is written onto that square, and the read/write head moves one square to the right. The last row tells us that given the current state
Qo
and input symbol
X
, the next state will be the halt state
H
, output 1 will be written on the tape, and there will be no further motion of the read/write head. The other rows of the state table can be interpreted similarly.

Tracing the machine's operation on the example input string, we see that it goes through the following sequence of states and tape configurations. Again, the position of the read/write head at the start of each step in the sequence of operations is indicated by the digit in bold type.

Qe
:
1
011011
X

Qo
: 0 0 11011
X

Qo
: 00
1
1011
X

Qe
: 000
1
011
X

Qo
: 0000 0 11
X

Qo
: 00000
1
1
X

Qe
: 000000
1
X

Qo
: 0000000
X

H
: 0000000
1

Figure 4.2
shows the state of the tape and the position of the read/write head after the leftmost symbol on the tape has been read. The 1 is overwritten by a 0, and the read/write head moves one square to the right.

There is, then, a distinct Turing machine for each distinct computational task. Each Turing machine so constructed is a special-purpose machine. Each such special-purpose machine specifies the initial contents of the tape, the desired content of the tape, the initial position of the read/write head, and a state table that defines the possible behavior of the machine. A Turing machine can be constructed to add two integers
n, m
represented by
n
1s followed by a blank followed by
m
1s, leaving the result of
n + m
1s on the tape. Another machine can be constructed to perform the multiplication of two numbers
n, m
leaving the result on the tape. Yet another machine could be built that, say, given an input string of
a
's
b
's,
c
's would produce its mirror image (a palindrome). For example, from input string
aaabbaacc
the output would be
ccaabbaaa
, and so on.

The parity detection machine described here is not a device for performing arithmetic. It is, rather, a pattern recognition machine. Indeed, the parity detector is a
decision
machine, for it can decide whether the number of 1s in an input string has odd or even parity. Turing's computing machine, then, is not just a calculating engine
à la
Babbage or Ludgate. It is a
symbol processing
machine. More precisely, it is a “squiggle” processing machine in that, for an input string of squiggles on the tape, it will generate an output string of squiggles. That the squiggles represent something else—that they are actually symbols—is determined by the designer of the machine. Sometimes, the strings of squiggles do not represent anything, as in the palindrome producer.

In more mathematical terms, a Turing machine's output will be a
function
of its input. It's value is, say,
F
(
X
),
where X
is the input or “argument” to the function
F
. The state table determines how
F
is to be computed. Indeed, we might say that a Turing machine's state table
is
that function.
²¹
If a Turing machine can be constructed to compute
F
(
X
), then that function is said to be
Turing computable
.
²²

A particular Turing machine is (to use another present-centered term)
programmed
to do what it does. The state table describes this program. As already noted, each Turing machine is a special-purpose computing device in the sense that the Difference Engine was a special-purpose device; it computes a
particular
function
F
(
X
). It does not have the universality dreamed of by Babbage when he was designing the Analytical Engine, but Turing quickly rectified the situation. As he tells us, one can invent a single machine
U
that can compute
any
computable function. If
U
is provided with a tape that begins with a symbolic description of some
other
computing machine
M
, then
U
will perform the same computation as
M
.
²³
He called this machine
U
a “universal computing machine.” Later, it came to be known as a
universal Turing machine
.
²⁴
From a present-centered point of view, it can be described in the following way.