Mind and Computation
What does it mean to tell someone exactly what to do?
Sixty years ago no one could give this query a plausible response. Now, however, we have a
generally accepted definition: a set of instructions is exact if some computer can follow them.
We have a word, algorithm, which is intended to refer to a completely exact set of instructions.
This is impressively elegant. But there’s a catch — this approach is meaningful only in the context
of a theory explaining exactly what a computer is. And it turns out that this problem is not so
straightforward as it might seem.
Note that one cannot say "a set of instructions is exact if every computer can follow them."
Obviously, computers come in different sizes and forms. Some are very small, with little
memory or processing power. Some, like the computer chips installed in certain televisions and
cars, are dedicated to one or two specific purposes. If there were little or nothing in common
between the various types of computers, computer science would not deserve the label "science."
But it seems that many computers are so powerful that they can simulate any other computer.
This is what makes theoretical computer science possible. Computers of this sort are called
"universal computers," and were first discussed by Alan Turing.
What is now called the Turing machine is the simple device consisting of:
1) a processing unit which computes according to some formula of Boolean algebra
2) a very long tape divided into squares, each square of which is marked either zero or one
3) a tape head which can move, read from and write to the tape
For instance, the processing unit might contain instructions like:
If the tape reads D and -A+(B-C)(D+E)=(R-J), then move tape to the left, call what is read
C, move the tape two to the right, and write (D-B)C on the tape.
The Boolean formula in the processing unit is the "program" of the Turing machine: it tells it
what to do. Different programs lead to different behaviors.
Assuming that the tape head cannot move arbitrarily fast, it is clear that any specific program,
running for a finite time, can only deal with a finite section of the two tapes. But theoretically, the tapes must be allowed to be as long as any program will require. Thus one often refers to an "infinitely long" tape, even though no particular program will ever require an infinitely long tape in any particular situation.
At first, Turing’s colleagues were highly skeptical of his contention that this simple machine was capable of executing any exact sequence of instructions. But they were soon convinced that
the behavior of any conceivable computer could be simulated by some Turing machine, and
furthermore that any precise mathematical procedure could be carried out by some Turing
machine. To remove all doubt, Turing proved that a certain type of Turing machine, now called a
"universal Turing machine", was capable of simulating any other Turing machine. One merely
had to feed the universal Turing machine a number encoding the properties of Turing machine X,
and then it would act indistinguishably from Turing machine X.
PUT THE CUP ON THE TABLE
Most people who have studied the literature would concur: no one has been able to come up
with a set of instructions which is obviously precise and yet cannot be programmed on a Turing
machine. However, agreement is not quite universal. For instance, the philosopher Hubert
Dreyfus (1978) has written extensively about the inability of existing computers to see, move
around, or make practical decisions in the real world. From his point of view, it is revealing to observe that, say, no Turing machine can follow the instruction: put the cup on the table.
The problem is not, of course, that a Turing machine doesn’t have any way to pick up a cup.
One could easily connect a robot arm to a computer in such a way that the output of the
computer determined the motions of the robot. This is the state of the art in Japanese factory
design. And even if current technology were not up to the task, the fact that it could be done
would be enough to vindicate Turing’s claim.
But could it, actually, be done? What is really involved here? When I tell someone to "put the
cup on the table," I am really telling them "figure out what I am talking about when I say ‘the
cup’ and ‘the table’ and ‘on’, and then put the cup on the table." Even if we give a computer a
robot eye, it is not easy to tell it how to locate a cup lying in the middle of a messy floor. And it is evenharder to tell a computer how to distinguish a cup from a bowl. In fact, it is hard to tell a person how to distinguish a cup from a bowl. This is a matter of culture and language. We simply learn it from experience.
One might take all this as proof that "put the cup on the table" is not actually a precise
instruction. Or, on the other hand, one might maintain that a Turing machine, provided with the
proper program, could indeed follow the instruction. But there is an element of circular
reasoning in the first alternative. "Put the cup on the table" is very precise to many people in
many situations. To say that it is not precise because a Turing machine cannot understand it is to define precision in terms of the Turing machine, in contradiction to common sense. And the
second alternative presupposes a great deal of faith in the future of artificial intelligence. The hypothesis that the Turing machine can simulate any computer and execute any set of precise
mathematical instructions is very well established. But the hypothesis that the Turing machine
can execute any set of precise instructions is a little shakier, since it is not quite clear what "precision" is supposed to mean.
In sum: there is still plenty of room for philosophical debate about the meaning of the Turing
machine. In the Introduction I mentioned Deutsch’s result that according to quantum theory any
finite physical system can be simulated by a quantum computer. Coupled with the fact that a
quantum computer cannot compute any functions besides those which a Turing machine can
compute, this would seem to provide a fairly strong argument in favor of Turing’s hypothesis.
But, of course, physics can never truly settle a philosophical question.
BRAIN AS TURING MACHINE
In a paper of legendary difficulty, McCulloch and Pitts (1943) attempted to demonstrate that
the human brain is a universal Turing machine. Toward this end, they adopted a greatly
oversimplified model of the brain, ignoring the intricacies of neurochemistry, perception,
localization, and the like. The McCulloch-Pitts brain is a network of dots and lines, each dot
standing for a neuron and each line standing for a connection between neurons. It changes in
discrete jumps: time 0, then time 1, then time 2, and so on. Each neuron operates according to
"threshold logic": when the amount of charge contained in it exceeds a certain threshold T, it
sends all its charge out to the neurons it is connected to. What McCulloch and Pitts proved is that a universal Turing machine can be constructed using a neural network of this sort instead of a program.
Some neuroscientists have protested that this sort of "neural network" has nothing to do with the brain. However, this is simply not the case. It is clear that the network captures one of the most prominent structures of the brain. Precisely what role this structure plays in the brain’s activity remains to be seen. But it is interesting to see how tremendously powerful this one structure is, all by itself.
As mentioned above, there have been numerous efforts to form biologically realistic neural
network models. One approach which has been taken is to introduce random errors into various
types of simulated neural networks. This idea has led to a valuable optimization technique called "simulated annealing" (Aarts et al 1987), to be considered below.