Reflection 3 Computer ethics

THE PATTERN ON

THE STONE

..........................................................................

A Member of the

Perseus Books Group

The Simple Ideas That Make Computers Work

W. DANIEL HILLIS

', <, I E N

r;e) s rE'- .,

CHAPTER I

NUTS AND BOLTS

When I was a child, I read a story about a boy who built a robot out of parts he found lying around a junkyard. The boy's robot could move, talk, and think, just like a person, and it became his friend. For some reason, I found the idea of build­ ing a robot very appealing, so I decided to build one myself. I remember collecting body parts-tubes for the arms and legs, motors for the muscles, lightbulbs for the eyes, and a big paint can for the head-in the full and optimistic expectation that after they were assembled and the contraption was plugged in, I would end up with a working mechanical man.

After nearly electrocuting myself a few times, I began to get my parts to move, light up, and make noises. I felt I was making progress. I began to understand how to construct movable joints for the arms and legs. But something even more important was beginning to dawn on me: I didn't have the slightest idea how to control the motors and the lights, and I realized that something was missing in my knowledge of how robots worked. I now have a name for what was miss­ ing: it's called computation. Back then, I called it "thinking," and I saw that I didn't have a clue about how to get some­ thing to think. It seems obvious to me now that computation is the hardest part of building a mechanical man, but as a child this came as a surprise.

2 THE PATTERN ON THE STONE

BOOLEAN LOGIC

.............. ········

Fortunately, the first book I ever rea d on the subject of com­

putation was a classic. My father w as an epidemiologist, and

we were living in Calcutta at the tim e. Books in English were

hard to come by, but in the library of the British consulate I

found a dusty copy of a book wri tten by the nineteenth­

century logician George Boole. The title of the book was

what attracted me: An Investigation of the Laws of Thought .

This grabbed my imagination. Could there really be laws that

governed thought? In the book, Bo ole tried to reduce the

logic of human thought to mathe matical operations. Al­

though he did not really explain human thinking, Boole

demonstrated the surprising power and generality of a few

simple types of logical operations. He invented a language

for describing and manipulating logical statements and

determining whether or not they a re true. The language is

now called Boolean algebra.

Boolean algebra is similar to the a lgebra you learned in

high school, except that the variable s in the equations repre­

sent logic statements instead of nu mbers. Boole's variables

stand for propositions that are eithe r true or false, and the

symbols ", v, and .., represent the log ical operations And, Or,

and Not. For example, the followin g is a Boolean algebraic

equation

-,(Av B) = (-,A)"( ..,B)

This particular equation, called De Morgan's theorem (after

Boole's colleague Augustus De Morgan), says that if neither

A nor B is true, then both A and B must be false. The vari­

ables A and B can represent any logical (that is, true or false)

statement. This particular equation is obviously correct, but

Boolean algebra also allows much more complex logical

statements to be written down and proved or disproved.

NUTS AND BOLTS J

Boole's work found its way into computer science

through the master's thesis of a young engineering student

at the Massachusetts Institute of Technology named Claude

Shannon. Shannon is best known for having invented a

branch of mathematics called information th eory, which

defines the measure of information we call a bit. Inventing

the bit was an impressive accomplishment, but what Shan­

non did with Boolean logic was at least as important to the

science of computation. With these two pieces of work,

Shannon laid the foundation for the developments that

were to occur in the field of computing for the next fifty

years.

Shannon was interested in building a machine that could

play chess-and more generally in building mechanisms

that imitated thought. In 1940, he published his master's

thesis, which was titled "A Symbolic Analysis of Relay

Switching Circuits." In it, he showed that it was possible to

build electrical circuits equivalent to expressions in

Boolean algebra. In Shannon's circuits, switches that were

open or closed corresponded to logical variables of Boolean

algebra that were true or false. Shannon demonstrated a way

of converting any expression in Boolean algebra into an

arrangement of switches. The circuit would establish a con­

nection if the statement was true and break the connection

if it was false. The implication of this construction is that ,'\

any function capable of being described as a precise logical

statement can be implemented by an analogous system of

switches.

Rather than presenting the detailed formalisms developed

by Boole and Shannon, I will give an example of their appli­

cation in the design of a very simple kind of computing

device, a machine that plays the game of tic-tac-toe. This

machine is much simpler than a general-purpose computer,

but it demonstrates two principles that are important in any

type of computer. It shows how a task can be reduced to logi­

cal functions and how such functions can be implemented as

4 THE PATTERN ON THE STONE

a circuit of connected switches . I actually built a tic-tac-toe

machine out of lights and sw itches shortly after I read

Boole's bo ok in Calcutta, and t his was my introduction to

computer logic. Later, when I w as an undergraduate at MIT,

Claude Shannon became a frien d and teacher, and I discov­

ered that he, too, had used lig hts and switches to build a

machine that could play tic-tac- toe.

As most readers know, the gam e is played on a 3 x 3

square grid. Players take turns marking the squares, one

player using an X, the other an 0. The first player to place

three symbols in a row (horiz ontally, vertically, or diago­

nally) wins the game. Young children enjoy tic-tac-toe

because it seems to offer limitles s possible strategies for win­

ning. Eventually they realize th at only a small number of

patterns can occur, and the ga me consequently loses its

charm: once both players lea rn the patterns, each game

invariably ends in a tie. Tic-tac -toe is a good example of a

computation precisely becaus e it wavers on this line

between the complex and the s imple. Crossing that line is

what computation is all about . Computation is about per­

forming tasks that seem to be co mplex (like winning a game

of tic-tac-toe) by breaking them down into simple operations

(like closing a switch).

In tic-tac-toe, the situations that occur are few en ough so

that it's practical to write them all down, and therefore to

build the correct response in eve ry case into the machine. We

can use a simple two-step proce ss for designing the machine:

first, reduce the play to a series of cases defining the correct

response to each pattern of move s; second, convert those cases

into electrical circuits by wiring the switches to recognize the

pattern and indicate the appropri ate response.

One way to proceed would be to write down every con­

ceivable arrangment of X's and O 's which could be placed on

the grid and then decide how t he computer would play in

each instance. Since each of the n ine squares has three possi­

ble states (X, 0, and blank), ther e are 39 (or 19,683) ways to

{,

:1+ -!,

�

l'7\ �wox*o oox 0 0)( X O X

-!- i } *fx-=OX $0 oox 0 0 )(

XO X ')( 0

O WINS O WIA/S t

� x TIE

FIGURE I

NUTS AND BOLTS 5

)( mo�.s

o mOVl!S

)( mDV£$

o moves

x moves

Part of a game tree for tic-tac-toe

fill the grid. But most of these patterns would never occur in

the course of a game. A better method of listing the possibili­

ties is to draw up a game tree-a configuration that traces

every possible line of play. The game tree starts with a blank

grid at the root and has a branch for every possible alternative

line of play, determined by the move of the human player.

(T he tree does not need to branch when the machine plays ,

because the response of the machine to any given move is

always predetermined.) Figure 1 shows a small part of such a

tree. For every possible move made by X, the human player,

there is a predetermined O response to be made by the

6 THE PATTERN ON THE STONE

machine. (For some strange reason, computer scientists

always draw trees upside-down, with th e "root" at the top.)

The tree in Figure 1 illustrates the stra tegy that I always

use in tic-tac-toe: I play in the center whenever I can. The

machine's moves are determined by the human player's

moves, which vastly reduces the numb er of possibilities to

be considered. A full game tree, showin g what the machine

should do in every situation, has about five hundred or six

hundred branches, the exact number depending on the

details of strategy. Following the tree wil l cause the machine

to win, or at least tie, every game. The r ules of the game are

built into the responses, so by following the tree the machine

will always obey the rules. From this gam e tree, we can write

down specifications that say exactly when the machine

should play in any particular position. These specifications

constitute the Boolean logic of the machi ne.

Once we have defined the desired behavi or, we can trans­

late that behavior into electrical circuits built out of batteries,

wires, switches, and lights . The basic ci rcuit in the machine

is the same circuit used in a flashlight : when the switch is

pressed down-that is, closed-the ligh t goes on, because a

complete path has been formed between the bulb and the bat­

tery. (The connections to the battery are ind icated by the + and

- signs.) Most important, these switches c an be wired either in

series or in parallel. For instance, we c an put two switches

together in series to make a light that wo rks only when both

switches are closed. This circuit implem ents one of the basic

switching functions of the computer- the "logic block"

known as the And function, so called bec ause the bulb lights

only when the first and the second s witches are closed.

Switches connected in parallel form the O r function, which

connects the circuit (and thus lights the bulb) whenever

either or both of the switches are closed (see Figure 2).

These simple patterns of serial and parallel wiring can be

used in combinations to form connection s that follow vari­

ous logical rules. In the tic-tac-toe mach ine, chains of

(±)----...1

NUTS AND SOL TS 7

/�8

(±) J____, - PAP.ALLE/...

FIGURE 2

Switches in series and parallel

switches connected in series are used to detect patterns, and

these chains are connected in parallel to lights, so that sev­

eral patterns can light the same bulb-that is, produce the

same response from the machine.

The tic-tac-toe machine I built has four banks of nine

switches each, and each switch corresponds to one of the nine

squares on the tic-tac-toe grid. It also has nine lightbulbs,

arranged in the pattern of a tic-tac-toe board. The machine,

which always plays first, makes its moves by lighting a bulb.

The human player moves by closing a switch-using the first

bank of switches to make his first move, the second bank for

his second move, and so on. In my version, the machine

always begins by playing in the upper left corner of the board,

a scheme that reduces the number of cases considerably. The

human player responds by closing one of the switches in the

first bank (s ay, the one corresponding to the center square in

the grid), and the game proceeds. The machine's strategy is

embodied in the wiring between the switches and the lights.

The wiring that produces the machine's first response is

easy (see Figure 3). Each switch in the first bank is con­

nected to a light that corresponds to the machine's reply. For

instance, a play in the center causes a response in the lower

IO THE PATTERN ON THE STONE

at playing chess (see chapter 5), because in place of the pre­

determined game tree they use a different method-one that

involves examining patterns sequentially in time.

Another difference between the tic-tac-toe machine and a

general-purpose computer is that the tic-tac-toe machine can

perform only one function. The "program" of the machine is

built into its wiring. The tic-tac-toe machine has no software.

BITS AND LOGIC BLOCKS

.....................................

As I noted in the Introduction, there is no reason the tic-tac­

toe machine (or any other computer) has to be built out of

electrical switches. A computer can represent information

using electrical currents, fluid pressures, or even chemical

reactions. Whether you build a computer out of transistors,

hydraulic valves, or a chemistry set, the principles on which

it operates are much the same. The key idea of the tic-tac-toe

machine is that the And function is implemented by con­

necting two switches in series and the Or function is imple­

mented by connecting two switches in parallel, but there are

many other ways to implement And and Or.

Here I must pause to mention the bit. The smallest "dif­

ference that makes a difference" (to use Bateson's phrase

again) is a difference that splits all signals into two distinct

classes. In the tic-tac-toe machine, the two classes are "cur­

rent flowing" and "no current flowing." By convention, we

call the two possible classes 1 and 0. These are just names;

we could as easily call them True and False, or Alice and

Bob. Even the choice of which class is called O and which is

called 1 is arbitrary. A signal that can carry one of two differ­

ent messages (like 1 or 0) is called a binary signal, or a bit. A

computer uses combinations of bits to represent all kinds of

sets of alternatives-different moves in tic-tac-toe, say, or dif­

ferent colors to be displayed on a screen. Since the conven-

c � fr@ �

INPUT A

-"-

//,/PUT 8

FIGURE 4

NUTS AND BOLTS 11

cu.:rPu-r

Mechanical implementation of the OR function

tion is to designate the bits by l's and O's, people often think of these bit patterns as numbers, hence the old chestnut "The computer does everything with numbers." But this conven­ tion is simply a way of thinking about what's going on. If we had named the two possible messages conveyed by the bit the letters X and Y, people would be saying, "The computer does everything with letters." The more accurate statement is "The computer represents numbers, letters, and everything else with patterns of bits."

Instead of using the flow of electricity to represent a bit, we could have used mechanical motion. Figure 4 shows how the Or function is implemented using a technology that rep­ resents 1 by sliding a stick to the right. As long as both the A and the B input sticks stay to the left, representing 0, then the spring will keep the output stick pushed to the left, but if either input stick slides to the right, then the output stick will slide to the right also. The object in Figure 5 computes another useful function, that of inversion: The inverter turns every signal into its opposite: for example, it turns a push to the right into a pull to the left, and vice versa.

These And, Or, and Invert functions are logic blocks, and they can be connected in order to create other func­ tions. For instance, the output of an Or block can be con­ nected to an Invert block to create a Nor function: the Nor

12 THE PATTERN ON THE STONE

......

!NPll,

FIGURE 5

Mechanical inverter

�

ou,pur

output will be a 1 when neither of its inputs is 1. In

another example (using De Morgan's theorem), we can

make an And block by connecting two Invert blocks to the

inputs of an Or block and connecting a third Invert block

to the output (see Figure 6). These four work together to

implement the And function, so the final output is 1 only

when both the inputs are 1.

Early computing devices were made with mechanical

components. In the seventeenth century, Blaise Pascal built

a mechanical adding machine, which inspired both Gott­

fried Wilhelm Leibniz and the English polymath Robert

Hooke to build improved machines that could multiply,

divide, and even take square roots. These machines were

not programmable, but in 1833 another Englishman, the

mathematician and inventor Charles Babbage, designed and

partially constructed a programmable mechanical com­

puter. Even as late as my own childhood in the sixties,

most arithmetic calculators were mechanical. I've always

liked these mechanical machines, because you can see

what's happening, which is not the case with electronic

s,-.,1414

INl'Vr �

FIGURE 6

NUTS AND BOLTS 13

-

our,11r-

An And block constructed by connecting an Or block to inverters

computers. When I'm designing an electronic computer

chip, I imagine the operation of the circuits as moving

mechanical parts.

THE FLUID COMPUTER

The picture I have in my mind when I design a logic circuit is of hydraulic valves. A hydraulic valve is like a switch that controls and is controlled by the flow of water. Each valve has three connections: the input, the output, and the control. Pressure on the control connection pushes on a piston that turns off the water flow from input to output. Figure 7 shows a circuit for the Or function, built out of hydraulic valves.

In this circuit, water pressure is used to distinguish between the two possible signals. Notice that in a hydraulic valve the control pipe can affect the output pipe but the out­ put pipe cannot affect the control pipe. This restriction estab­ lishes a forward flow of information through the switch; in a sense, it establishes a direction in time. Also, since the valve is

14 THE PATTERN ON THE STONE

INPUT A

J.ll�H PRESSURE

WATEA: .SUPPLY

I/VPWT l,

FIGURE 7

HYl>RA«LIC /VALVE'

ourPur

.sn.JNli KFEPS VALVE SHUT t/lVLESS OPEN£/)

BY' INPUT" 1'1{ESS<JIU£

An Or block built with hydraulic valves

either open or closed, it serves an additional function of

amplification, which allows the strength of the signal to be

restored to its maximum value at every stage. Even if the input

is a little low on pressure-becaus e it goes through a long, thin

pipe, say, or because of a leak-t he output will always be at

full pressure thanks to the on/off operation of the valve. This

is the fundamental difference betw een digital and analog: A

digital valve is either on or off; a n analog valve, like your

kitchen faucet, can be anything in between. In the hydraulic

computer, all that is required of the input signal is that it be

NUTS AND BOLTS 15

strong enough to move the valve. In this case, the difference

that makes a difference is the difference in water pressure suf­

ficient to switch the valve on. And since a weakened signal

entering an input will still produce a full-strength output, we

can connect thousands of layers of logic, the output of one

layer controlling the next. without worrying about a gradual

decrease in pressure. The output of each gate will always be at

full pressure.

This type of design is called restoring logic, and the exam­

ple in hydraulic technology is particularly interesting, because

it corresponds almost exactly to the logic used in modern elec­

tronic computers. The water pressure in the pipes is analo­

gous to the voltage on the wires, and the hydraulic valve is

analogous to the metal-oxide transistor. The control, input,

and output connections on the valve correspond closely to the

three connections (called gate, source, and drain) on a transis­

tor. The analogy between water valves and transistors is so

exact that you could translate the design for a modern micro­

processor directly into a design for a hydraulic computer. To

do so, you would need to look at the pattern of wires on the

silicon chip under a microscope and then bend a set of pipes

into the same shapes as the wires on the chip and connect

them in exactly the same pattern. In place of each transistor,

you would use a hydraulic valve. The pipe that corresponds to

the power-supply voltage on your chip would be connected to

a pressurized water supply, and the pipe that corresponds to

the ground connection could empty down a drain.

To use the hydraulic computer, you would have to connect

hydraulic equivalents of its inputs and outputs-you would

need to build a hydraulic keyboard, a hydraulic display,

hydraulic memory chips, and so on-but if you did all this, it

would go through exactly the same switching events as the

electronic chip. Of course, the hydraulic computer would be

much slower than your latest microprocessor (to say nothing

of larger), because water pressure travels down pipes much

more slowly than electricity travels down wires. As to the

16 THE PATTERN ON THE STONE

size: Since the modern microchip has several million transis· tors, its hydraulic equivalent would require several million valves. A transistor in a chip is about a millionth of a meter across; a hydraulic valve is about 10 centimeters on a side. If the pipes scale proportionally, then the hydraulic computer would cover about a square kilometer with pipes and valves. From an airplane, it would look roughly the same as the elec· tronic chip does under a microscope.

When I design a computer chip, I draw lines on a com· puter screen, and the pattern is reduced (in a process analo· gous to photographic reduction) and etched onto a chip of silicon. The lines on the screen are my pipes and valves. Actually, most computer designers don't even bother draw· ing lines; instead, they specify the connections between Ands and Ors and let a computer work out the details of placement and geometry of the switches. Most of time, they forget about the technology and concentrate on the function. I do this, too, sometimes, but I still prefer to draw my own shapes. Whenever I design a chip, the first thing I want to do is look at it under a microscope-not because I think I can learn something new by looking at it but because I am always fascinated by how a pattern can create reality.

TINKER TOYS

..................

FIGURE 8

Tinker Toy computer

NUTS AND BOLTS 17

input signal will not result in a degraded output. The second element, the connector, is the wire or pipe that carries a sig­ nal between switches. This connecting element must have the ability to branch, so that a single output can feed many inputs. These are the only two elements necessary to build a computer. Later we will introduce one more element-a reg­ ister, for storing information-but this can be constructed of the same steering and connecting components.

Except for the miracle of reduction, there is no special rea· I have never built a hydraulic computer, but once, withson to build computers with silicon technology. Building 8 some friends, I did construct a computer out of sticks andcomputer out of any technology requires a large supply of strings. The pieces came from a children's construction setonly two kinds of elements: switches and connectors. The called Tinker Toys. Readers may remember this as a set ofswitch is a steering element (the hydraulic valve, or the tran- cylindrical wooden sticks that fit into fat little wooden hubssistor), which can combine multiple signals into a single sig· with holes in them. The logic of my Tinker Toy computernal. Ideally, the switch should be asymmetrical, so that the worked much like that shown in Figure 8. Like the switches­ input signal affects the output signal but not vice versa, and and-lights computer, the Tinker Toy computer played tic-tac­it should have a restoring quality, so that a weak or degraded toe. It never lost. The computer was a lot of trouble to make,

18 THE PATTERN ON THE STONE

requiring tens of thousands of pieces from more than a hun­

dred Tinker Toy "Giant Engineer" construction sets, and the

finished product (now sitting in the Computer Museum in

Boston, Massachusetts) looks incomprehensibly complex.

Yet the principles on which it operates are just the simple

combination of And and Or functions described above.

The big mistake I made in designing the Tinker Toy com­

puter is that I did not use restoring logic-that is, there was

no amplification from one stage of logic to the next. The

implementation of the logic was based on sticks pressing

against sticks, in a design similar to the one illustrated in fig­

ure 4. Because of this design choice, all the force required to

move the hundreds of elements in the machine had to be

supplied by the press of the input switch. The accumulated

force tended to stretch the strings that transmitted the

motion, and because there was no restoration at each stage,

the errors caused by the stretching accumulated from one

logic element to the next. Unless the strings were constantly

tuned, the machine would make mistakes.

I constructed a later version of the Tinker Toy computer

which fixed the problem, but I never forgot the lesson of that

first machine: the implementation technology must produce

perfect outputs from imperfect inputs, nipping small errors

in the bud. This is the essence of digital technology, which

restores signals to near perfection at every stage. It is the

only way we know-at least, so far-for keeping a compli-

cated system under control.

FREE TO WORRY ABOUT THE DIFFERENCE

THAT MAKES A DIFFERENCE

........................................

Naming the two signals in computer logic O and 1 is an

example of functional abstraction. It lets us manipulate

information without worrying about the details of its under·

NUTS AND SOL TS 19

lying representation. Once we figure out how to accomplish a given function, we can put the mechanism inside a "black box," or a "building block" and stop thinking about it. The function embodied by the building block can be used over and over, without reference to the details of what's inside. This process of functional abstraction is a fundamental in computer design-not the only way to design complicated systems but the most common way (later, I'll describe an alternate method). Computers are built up of a hierarchy of such functional abstractions, each one embodied in a build­ ing block. The blocks that perform functions are hooked together to implement more complex functions, and these collections of blocks in turn become the new building blocks for the next level.

This hierarchical structure of abstraction is our most powerful tool in understanding complex systems, because it lets us focus on a single aspect of a problem at a time. For instance, we can talk about Boolean functions like And and Or in the abstract, without worrying about whether they are built o ut of electrical switches or sticks and strings or water­ operated valves. For most purposes, we can forget about technology. This is wonderful, because it means that almost everything we say about computers will be true even when transistors and silicon chips become obsolete.

CHAPTER 2

..........................................................................

U NIVERSAL BU ILDING BL O CKS

From now on, we can forget about wires and switches and work with the abstraction of logic blocks operating on l's and O's, a simple step that allows us to pass from the realm

of engineering into the realm of mathematics. This is the most abstract chapter in the book; it will show you how the methods used to construct a tic-tac-toe machine can be used to construct almost any function. In it, we'll define a power­ ful set of building blocks: logical functions and finite-state machines. With these elements, it's easy to build a com­ puter.

LOGICAL FUNCTIONS

In constructing the tic-tac-toe machine, we began by writing

the game tree, whch gave us a set of rules for generating the outputs from the inputs. This turns out to be a generally use­ ful method of attack. Once we write down the rules that specify what outputs we want for each combination of inputs, we can build a device that implements these rules

using And, Or, and Invert functions. The logic blocks And,

21

22 THE PATTERN ON THE STONE

Or, and Invert form a universal construction set, which

can be used to implement any set of rules. (These primi­

tive types of logic blocks are sometimes also called logic

gates.)

This idea of a universal set of blocks is important: it

means that the set is general enough to build anything. My

favorite toy when I was a child was a set of interlocking plas­

tic bricks called Lego blocks, with which I built all kinds of

toys: cars, houses, spaceships, dinosaurs. I loved to play

with these blocks, but they were not quite universal, since

the only objects you could build with them had a certain

squarish, stair-steppy look. Building something with a differ­

ent shape-a cylinder or a sphere, for example-would

require a new type of block. Eventually, I had to switch to

another medium in order to build the things I wanted. But

the And, Or, and Invert blocks of Boolean logic are a univer­

sal construction set for converting inputs to outputs. The

best way to see how they form a universal set is to under­

stand a general method for using them to implement rules.

To start, we will consider binary rules-rules that specify

inputs and outputs that are either 1 or 0. The tic-tac-toe

machine is a good example of a function specified by binary

rules, because the input switches and the output lights are

either on or off-that is, either 1 or 0. (Later, we will discuss

rules for handling letters, numbers, or even pictures and

sounds as inputs and outputs.) Any set of binary rules can be

completely specified by showing a table of the outputs for

each possible combination of l's and O's on the inputs. For

example, the rules for the Or function are specified by the

following table:

Input A Input B Output

0 0 0

OR Function 0 1 1

1 0 1

1 1 1

UNIVERSAL BUILDING BLOCKS 23

The Invert function is specified by an even simpler table:

Invert Function

Input

0

1

Output

1

0

For a binary function with n inputs, there are zn possiblecombinations of input signals. Sometimes we won't bother tospecify all of them, because we don't care about certain com­binations of inputs. For example, in specifying the functionperformed by the tic-tac-toe machine, we don't care whathappens if the human player plays in all squares simultane­ously. This move would be disallowed, and we don't need tospecify the function's output for this combination of inputs. Complex logic blocks are constructed by connecting And,Or, and Invert blocks. In drawings of the connection pattern,the three blocks are conventionally represented by boxes ofdifferent shape (see Figure 9); the lines connecting on the leftside represent inputs to the blocks, and the lines connectingon the right represent the output. Figure 10 shows how apair of two-input Or blocks can be connected to form a three­input Or function; the output of this function will be 1 if any

one of its three inputs is 1. It's also possible to string severalAnd blocks together in a similar manner to make an Andblock with any number of inputs.

INPt,ir A=&- INPUT A-j}- IINI> OUTPUT 01( 0UTPtl1' /NPllT B INPUT a--

INPur� ourrur

I A/VE 1?.r

FIGURE 9

And, Or, and Invert Blocks

24 THE PATTER N ON THE STON

E

FIGURE 10

==}, A three-input Or block

made from a pair of two-in put Or blocks

Figure 11 shows how an And bl ock can be constructed by

connecting an Inverter to the i nputs and output of an Or

block. (Here is De Morgan's theo rem again.) The best way to

get a feeling for how this works i s to trace through the 1 's and

O's for every combination of inpu ts. Notice that this illustra­

tion is essentially the same as Fi gure 6 in the previous chap­

ter. It points up an interesting fa ct: we don't really need And

blocks in our universal building set, because we can always

construct them out of Or blocks and Inverters.

l>- FIGURE 11

Making And out of Or

UNIVERSAL BUILDING BLOCKS 25

block, majority wins-that is, the output will be 1 only if two or more of the inputs are 1.

Majority Inputs Output ABC

0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

Figure 12A shows how this function is implemented.An And block with the appropriate Invert blocks as input is used to recognize each combination of inputs for which the output is 1; these blocks are connected by an Or block, which produces the output. This strategy can be used to cre­ ate any transformation of inputs to outputs:

Of course, this particular method of using a separate And gate to recognize each combination of inputs is not the only way to implement the function, and it is often not the sim­ plest way. Figure 12B shows a simpler way to produce the majority function. The great thing about the method de­ scribed is not that it produces the best implementation but that it always produces an implementation that works . The important conclusion to draw is that it is possible to com-

As in the tic-tac-toe playing machine, And blocks :ire bine And, Or, and Invert blocks to implement any binary

used to detect each possible com bination of inputs for which function-that is, any function that can be specified by an

th t . 1 whi'le Or blocks provide a r

oster of these input/output table of O's and l's. e outpu 1s ,

b. 1. For example let's start with a simple functwn Restricting the inputs and output to binary numbers is

com ma 10ns. ' th f thr . t Imagine that we wa

nt to build a block at not really much of a restriction, because the combinations of o ee mpu s. . allows the three inputs to vote

on the output. In this new l's and O's can be used to represent other things-letters,

16 THE PAT TERN ON TH

E STONE

@A �-� -, --.-l--+\----!t

- Of{ -

� ?

MJIIT"�/f'(

@ A • r

6

c

..,___ __ /M:IO!l.rfY

FIGURE 12

How the voting function is implemented by

And, Or, and Invert Blocks

larger numbers, any ent ity that can be encoded

. As an exam­

ple of a nonbinary fun ction, suppose we wan

t to build a

machine to act as a ju dge of the children's g

ame of Scis­

sors/Paper/Rock. This i s a game for two playe

rs in which

each chooses, in secret, one of three "weapons"

-scissors,

UNIVERSAL BUILDING BLOCKS

paper, or rock. The rules are simple: scissors cuts paper, paper

covers rock, rock crushes scissors. If the two children choose

the same weapon, they tie. Rather than building a machine

that plays the game (which would involve guessing which

weapon the opponent is going to choose), we will build a

machine that judges who wins. Here's the input/output table

for the function that takes the choices as inputs and declares

the winner as output. The table encodes the rules of the game:

Input A InputB Output

Scissors Scissors Tie

Scissors Paper A wins

Scissors Rock B wins

Paper Scissors B wins

Paper Paper Tie

Paper Rock A wins

Rock Scissors A wins

Rock P aper B wins

Rock Rock Tie

The Scissors-Paper-Rock judging function is a combinational

function, but it is not a binary function, since its inputs and

output have more than two possible values. To implement this

function as a combinational logic block, we must convert it to

a function of l's and O's. This requires us to establish some

convention for representing the inputs and outputs. A simple

way to do this would be to use a separate bit for each of the

possibilities. There would be three input signals for each

weapon: a 1 on the first input represents Scissors, a 1 on the

second input represents Rock, and a 1 on the third input rep­

resents Paper. Similarly, we could use separate output lines to

represent a win for player A, a win for player B, or a tie. So the

box would have six inputs and three outputs.

Using three input signals for each weapon is a perfectly

good way to build the function, but if we were doing it

inside a computer we would probably use some kind of

27

18 THE PAT TERN ON TH

E STONE

encoding that required a smaller number of inputs and out·

puts. For example, we could use two bits for each i nput and

use the combination 01 to represent Scissors, 10 to rep resent

Paper, and 11 to represent Rock. We could similarly encode

each of the possible outputs using two bits. This encoding

would result in the simpler three-input/two-out put table

shown below:

Scissors ::: 01 Paper= 10 Rock= 11 A wins :::10 B wins= 01 Tie= oo

A Inputs 01 01 01 10 10 10 11 11 11

B Inputs 01 10 11

01 10 11 01 10 11

Outputs 00 10 01 01 00 10 10 01 00

UNIVERSAL BUILDING BLOCKS 29

represents zero, the sequence 0000001 represents the num­ ber 1, the sequence 0000010 represents 2, and so on. The description of computers as "64-bit " or "32-bit " indicates the number of bit positions in the representation used by the computer's circuits: a 32-bit computer uses a combination of thirty-two bits to represent a base-2 number. The base-2 number system is a common convention, but there is nothing that requires its use. Some computers don't use it at all, and most computers that do also represent numbers in other ways for various purposes. For instance, many computers use a slightly different convention for representing negative numbers and also have a convention called a floating point to represent numbers that have decimal points. (The position of the decimal point "floats " relative to the digits, so that a fixed number of digits can be used to represent a wide range of numbers.) The particular representation schemes are often chosen in such a way as to simplify the logic of the circuits that perform arithmetical operations, or to make it easy to convert from one representation to another.

b. t" s of bits to represent any- Because any logical function can be implemented as a t an use com ma ion Compu ers c d d n the number of messages Boolean logic block, it is possible to build blocks that per-th. g· the number of bits epen s O 1 " "th · l · l"k dd" · l · 1· · in • . h d 1 gi· ne for examp e, a com- 1orm ar1 met1ca operat10ns 1 e a 1hon or mu hp 1cation d b d"stingms e . ma that nee to e i . letters of the alphabet. Five-bit by using numbers with any sort of representation. For puter that works with the thirt -two different possibilities instance, imagine that we want to build a functional blockinput signals can repr.es�ntth y ter that work on letters that will add numbers on an eight-bit computer. An eight-bit ) F f s within e compu (25 ::: 32 · unc ion lth h they more often use an adder block must have sixteen input signals (eight for each. se such a code ' a oug . f b b d . . sometimes u . b" t llow representation o of the num ers to e a ded), and eight output signals for the. "th ven or eight its, o a encodmg wi se 1 and so on. Most mod· sum. Since each number is represented by eight bits, there t f n marks numera s, capitals, punc ua 10 ' d d esentation of alphabet are 256 possible combinations, and each can represent a dif-the stan ar repr

em computers use f American Standard Code ferent number. For example, we could use these combina-letters called ASCII (an aero;� A;CII the sequence 1000001 tions to represent the numbers between O and 255, orfor Information lnt�rchange · : and �000010 represents the between -100 and +154. Defining the function of the blockrepresents the capital letter ' . f course is arbitrary. would be just a matter of writing down the addition table . d n The convention . o • capital B, an so O • conventions for repre· and then converting it to l's and O's, using the chosen repre-t s have one or more Most compu er th t mmon is the base 2 rep· sentation. The table of l's and O's could then be converted to. b One of e mos co senting num ers. . hich the bit sequence 0000000 And and Or blocks by the methods described above.resentation of numbers, m w

30 THE PA TTERN ON T

HE STONE

By adding two more inputs to the bloc k, we could use

similar techniques to build a block th at not only adds but

also subtracts , multiplies, and divides. The two extra control

inputs would specify which of these op erations was to take

place . For instance , on every line of th e table where the con­

trol inputs were 01, we would specify the output to be the

sum of the input numbers, whereas i n every combination

where the control inputs were 10 , we w ould specify the out­

puts to be the product, and so on. Most computers have logi­

cal blocks of this type inside them calle d arithmetic units.

Combining Ands and Ors according to this strategy is one

way to build any logical function , but it is not always the

most efficient way. Often, by clever d esign, you can imple­

ment a circuit using far fewer building blocks than the pre­

ceding strategy requires. It may also be desirable to use other

types of building blocks or to desig n circuits that min­

imize the delay from input to output. Here are some typical

puzzles in logic design: How do you use And blocks and

Inverters to construct Or blocks? (Easy.) How do you use a

collection of And and Or blocks, plus only two Inverters, to

construct the function of three Inverte rs? (Hard, but possi­

ble.) Puzzles like this come up in the course of designing a

computer, which is part of what makes the process fun.

FINITE-STA TE MACHIN

ES

..... .....

....... ...........

.......

UNIVERSAL BUILDING BLOCKS

them everywhere-in combination locks, ballpoint pens, even legal contracts. The basic idea of a finite-state machine is to combine a look-up table, constructed using Boolean logic, with a memory device. The memory is used to store a sum­ mary of the past, which is the state of the finite-state machine.

A combination lock is a simple example of a fi nite-state machine. The state of a combination lock is a summary of the sequence of numbers dialed into the lock. The lock doesn't remember all the numbers that have ever been dialed into it, but it does remember enough about the most recent numbers to know when they form the sequence that will open the lock. An even simpler example of a finite-state machi ne is the retractable ballpoint pen. This finite-state machine has two possible states-extended and retracted­ and the pen remembers whether its button has been pressed an odd or an even number of times. All finite-state machines have a fixed set of possible states, a set of allowable inputs that change the state (clicking a pen's button, or dialing a number into a combination lock), and a set of possible out­ puts (retracting or extending the ballpoint, opening the lock). The outputs depend only on the state, which in turn depends only on the history of the sequence of inputs.

Another simple example of a finite-state machine is a counter, such as the tally counter on a turnstile indicatingthe number of people who have passed through. Each time a new person goes through, the counter's state is advanced by one . The counter is a finite state because it can only count up to a certain number of digits. When it reaches its maximum count-say, 999-the next advance will cause it to return to zero. Odometers on automobiles work like this. I once drove an old Checker cab with an odometer that read 70 ,000, but I

The methods I've described can be use d to implement any

function that stays constant in time, but a more interesting

class of functions are those that involve s equences in time. To

handle such functions, we use a devic e called a finite-state never kne 'f th

macfone. fm\te-state maclrines can be u sed to Ullplemenl miles, °' ;7

� , 00

; ca·� bad traveled 7 0,000 miles, 1 70 ,000

time-varying functions-functions that de pend not just on the 100 000 stat . ll th

ml es, �ecause the odometer had only ' es, a ose h1sto ·

current input but also on the previous his tory of inputs. Once the odomete

nes were equivalent as far as r was concerned Th · ·

you learn to recognize a finite-state mach ine , you'll notic< often define a t ,,

· IS is why mathematicians s ate as a set of equivalent histories ."

31

3l THE P ATTERN O

N THE STO NE

Other familiar e xamples of finite-s

tate machines inclu de

traffic lights and elevator-button p

anels. In these m achines,

the sequence of s tates is controlled

by some combin ation of

an internal clock and input buttons

such as the "Wal k" but­

ton at the crosswal k and the elevator

call and floor-selecti on

buttons. The next state of the mach

ine depends not only on

the previous state but also on the si

gnals that come fro m the

input button. Th e transition from

one state to anoth er is

determined by a fix ed set of rules, whi

ch can be summari zed

by a simple state diagram showing

the transition betw een

states. Figure 13 shows a state d

iagram for a traf fic-light

A

! 13 P..pC"&

� �\0!•1���01

0 0

/ 0 0 ·"",...¢ I

e

FIGURE 13

UNIVERSAL BUILDING BLOCKS

• IN'UT�.�------�

FIGURE 14

�

-/;WR)�

Finite-state machine, with logic block feeding register

controller at an intersection where the light turns red in both

directions after the Walk button is pressed. Each drawing of

light represents a state and each arrow represents a transition

between states. The transition depends on whether or not the

"walk" button is pressed.

To store the state of the finite-state machine, we need to

introduce one last building block-a device called a register,

which can be used to store bits. An n-bit register has n inputs

and n outputs, plus an additional timing input that tells th e

register when to change state. Storing new information is

called "writing" the state of the register. When the timing

signal tells the register to write a new state, the register

changes its state to match the inputs . The outputs of the reg­

ister always indicate its current state. Registers can be imple­

mented in many ways, one of which is to use a Boolean logic

block to steer the state information around in a circle. This

type of register is often used in electronic computers, which

is why they lose track of what they're doing if their power is

interrupted.

A finite-state machine consists of a Boolean logic block

connected to a register, as shown in Figure 14. The finite-

D d. __ fior a traffic-

light controller state machine advances its state by writing the output of the State 1agr .....

JJ

34 THE PA TTERN ON

THE STONE

Boolean logic blo ck into the regis

ter; the logic blo ck then

computes the next state, based on the

input and the cur rent

state. This next sta te is then written

into the register on the

next cycle. The pro cess repeats in eve

ry cycle.

The function of a finite-state machi

ne can be specified by

a table that sho ws, for every state

and every input, the state

that follows. For e xample, we can s

ummarize the ope ration

of the traffic-light controller by the

following table:

Outputs:

Inputs:

Walk Cu rrent Main

Cross Next

Button St ate Road

Road State

Not Pressed A Red Green

B

Not Pressed B Red Yello

w D

Not Pressed c Yellow Red

A

Not Pressed D Green Red

c

Not Pressed W alk Walk

Walk D

Pressed A Red Green

B

Pressed B Red Yellow

Walk

Pressed c Yellow Red

Walk

Pressed D Green Red

c

Pressed W alk Walk

Walk Walk

The first step in im plementing a finit

e-state machine is to

generate such a t able. The second s

tep is to assign a di fferent

pattern of bits to e ach state. The five

states of the traffi c-light

controller will req uire three bits. (Si

nce each bit doubl es the

number of possibl e patterns, it is p

ossible to store up to 2"

states using n bits.) By consistently re

placing each word i n the

preceding table wit h a binary pattern, w

e can convert the table

to a function that can be implemented

with Boolean logic.

In the traffic-light system, a timer co

ntrols the writing of

the register, which ca uses the state to ch

ange at regular inte r·

vals. Another exampl e of a finite-state

machine that advanc es

its state at regular intervals is a digital

clock. A digital clo ck

with a seconds indica tor can be in one of 2

4 x 60 x 60 = 86,400

UNIVERSAL BUILDING BLOCKS 35

possible display states-one for each second of the day. The

timing mechanism within the clock causes it to advance

its state exactly once per second. Many other types of digital

computing devices, including most general-purpose comput­

ers, also advance their state at regular intervals, and the rate at

which they advance is called the clock rate of the machine.

Within a computer, time is not a continuous flow but a fixed

sequence of transitions between states. The clock rate of the

computer determines the rate of these transitions, hence the

correspondence between physical and computational time.

For instance, the laptop computer on which I am writing this

book has a clock rate of 33 megahertz, which means that it

advances its state at a rate of 33 million times per second. The

computer would be faster if the clock rate were higher, but its

speed is limited by the time required for information to propa­

gate through the logic blocks to compute the next state. As

technology improves, the logic tends to become faster and the

clock rate increases. As I write these words, my computer is

state-of-the-art, but by the time you read this book computers

with 33 megahertz clock rates will probably be considered

slow. This is one of the wonders of silicon technology: as we

learn to make computers smaller and smaller, the logic

becomes faster and faster.

One reason finite-state machines are so useful is that they

can recognize sequences. Consider a combination lock that

opens only when it is given the sequence 0 -5-2. Such a

lock, whether it is mechanical or electronic, is a finite-state

machine with the state diagram shown in Figure 15.

A similar machine can be constructed to recognize any

finite sequence. Finite-state machines can also be made to rec­

ognize sequences that match certain patterns. Figure 16 shows

one that recognizes any sequence starting with a 1, followed by

a sequence of any number of Os, followed by a 3. Such a com­

bination will unlock the door with the combination 1-0-3, or

a combination such as 1-o--0-0-3, but not with the combina­

tion 1-0-2-3, which doesn't fit the pattern. A more complex

36 THE PATT ERN ON THE

STONE

8 FIGURE 15

State diagram for a lo ck

with combination 0·5·2

finite-state machine c ould recognize a mor

e complicated pat­

tern, such as a misspel led word within a stre

am of text.

As powerful as they are , finite-state mac

hines are not

capable of recognizing all types of patterns i

n a sequence. For

instance, it is imposs ible to build a finite-

state machine that

will unlock a lock w henever you enter an

y palindrome-a

sequence that is th e same forward an

d b ackward , like

3-2-1-1-2-3. This is because palin

dromes can be of an y

length, and to recogn ize the second half of

a palindrome you

need to remember e very character in the

first half. Since

there are infinitely m any possible first h a

lves, this would

require a machine wit h an infinite number

of states.

A similar argument demonstrates the im

possibility of

building a finite-state m ach ine that recognize

s whether a given

English sentence is gra mmatically correct. Co

nsider the sim·

FIGURE 16

State diagram to recognize sequences like 1,0,3 and 1,0,0,0,,

UNIVERSAL BUILDING BLOCKS 37

A'T:lre

A 1. lOGKEl> )

0

j ..fl'l'trll/K6

l" 1 e,ur A i�A&

/.ooK/lo/ft \ Ft:11(.

i3

8 ple sentence "Dogs bite." The meaning of this sentence can be

changed by putting a qualifier between the noun and the verb;

for instance, "Dogs that people annoy bite." This sentence can

in turn be modified by putting another phrase in the middle:

"Dogs that people with dogs annoy bite." Although the mean­

ing of such sentences might be expressed more clearly, and

although they become increasingly difficult to understand,

they are grammatically correct. In principle, this process of

nesting phrases inside of one another can go on forever, pro­

ducing absurd sentences like "Dogs that dogs that dogs that

dogs annoy ate bit bite." Recognizing such a sentence as gram­

matically correct is impossible for a finite-state machine, and

for exactly the same reason it's difficult for a person: you need

a lot of memory to keep track of all those dogs. The fact that

human beings seem to have trouble with the same kinds of

sentences that stump finite-state machines has caused some

people to speculate that we may have something like a finite­

state machine inside our head for understanding language. As

you will see in the next chapter, there are other types of com­

puting devices that seem to fit even more naturally with the

recursive structure of human grammar.

38 THE PATTERN ON THE STONE

I was introduced to finite-state machines by my mentor Marvin Minsky. He presented me with the following famous puzzle, called the firing squad problem: You are a general in charge of an extremely long line of soldiers in a firing squad. The line is too long for you to shout the order to "fire," and so you must give your order to the first soldier in the line, and ask him to repeat to the next soldier and so on. The hard part is that all the soldiers in the line are supposed to fire at the same time. There is a constant drumbeat in the background; however, you can't even specify that the men should all fire after a certain number of beats, because you don't know how many soldiers are in the line. The problem is to get the entire line to fire simultaneously; you can solve it by issuing a com­ plex set of orders which tells each soldier what to say to the soldiers on either side of him. In this problem, the soldiers are equivalent to a line of finite-state machines with each machine advancing its state by the same clock (the drumbeat), and each receiving input from the output of its immediate neighbors. The problem is therefore to design a line of identi­ cal finite-state machines that will produce the "fire" output at the same time in response to a command supplied at one end. (The finite-state machines at either end of the line are allowed to be different from the others.) I won't spoil the puzzle by giv­ ing away the solution, but it can be solved using finite-state machines that have only a few states.

Before showing you how Boolean logic and finite-state machines are combined to produce a computer, I'll skip ahead in this bottom-up description and tell you where we're going. The next chapter starts by setting out one of the highest levels of abstraction in the function of a computer, which is also the level at which most programmers interact with the machine.

CHAPTER 4

HOW UNIVERSAL ARE

TURING MACHINES?

What are the limits to what a computer can do? Must all computers be composed of Boolean logic and registers, or might there be other kinds, even more powerful? These ques­ tions take us to the most philosophically interesting topics in this book: Turing machines, computability, chaotic systems, Goedel's incompleteness theorem, and quantum comput­ ing-topics at the center of most discussions about what computers can and cannot do.

Because computers can do some things that seem very much like human thinking, people often worry that they threaten our unique position as rational beings, and there are some who seek reassurance in mathematical proofs of the limits of computers. There have been analogous controver­ sies in human history. It was once considered important that the Earth be at the center of the universe, and our imagined position at the center was emblematic of our worth. The dis­ covery that we occupied no central position-that our planet was just one of a number of planets in orbit around the Sun-was deeply disturbing to many people at the time, and the philosophical implications of astronomy became a topic of heated debate. A similar controversy arose over evolution­ ary theory, which also appeared as a threat to humankind's

61

62 THE PATTERN ON THE STONE

uniqueness. At the root of these earlier philosophical crises

was a misplaced judgment of the source of human worth. I

am convinced that most of the current philosophical discus­

sions about the limits of computers are based on a similar

misjudgment.

TURING MACHINES

The central idea in the theory of computation is that of a uni­

versal computer-that is, a computer powerful enough to sim­

ulate any other computing device. The general-purpose

computer described in the preceding chapters is an ex­

ample of a universal computer; in fact most computers we

encounter in everyday life are universal computers. With the

right software and enough time and memory, any universal

computer can simulate any other type of computer, or (as far as

we know) any other device at all that processes information.

One consequence of this principle of universality is that

the only important difference in power between two comput­

ers is their speed and the size of their memory. Computers

may differ in the kinds of input and output devices connected

to them, but these so-called peripherals are not essential char­

acteristics of a computer, any more than its size or its cost or

the color of its case. In terms of what they are able to do, all

computers (and all other types of universal computing

devices) are fundamentally identical.

The idea of a universal computer was recognized and

described in 1937 by the British mathematician Alan Turing.

Turing, like so many other computing pioneers, was interested

in the problem of making a machine that could think, and he

invented a scheme for a general-purpose computing machine.

Turing referred to his imaginary construct as a "universal

machine," since at that time the word "computer" still meant

"a person who performs computations."

-,_

-'Ei C

'-.

HOW UNIVERSAL ARE TURING MACHINES!

To picture a Turing machine, imagine a mathematician

performing calculations on a scroll of paper. Imagine further

that the scroll is infinitely long, so that we don't need to

worry about running out of places to write things down. The

mathematician will be able to solve any solvable computa­

tional problem no matter how many operations are involved,

although it may take him an inordinate amount of time. Tur­

ing showed that any calculation that can be performed by a

smart mathematician can also be performed by a stupid but

meticulous clerk who follows a simple set of rules for read­

ing and writing the information on the scroll. In fact, he

showed that the human clerk can be replaced by a finite­

state machine. The finite-state machine looks at only one

symbol on the scroll at a time, so the scroll is best thought of

as a narrow paper tape, with a single symbol on each line.

Today, we call the combination of a finite-state machine

with an infinitely long tape a Turing machine. The tape of a

Turing machine is analogous to, and serves much the same

function as, the memory of a modern computer. All that the

finite-state machine does is read or write a symbol on the

tape and move back and forth according to a fixed and sim­

ple set of rules. Turing showed that any computable problem

could be solved by writing symbols on the tape of a Turing

machine-symbols that would specify not just the problem

but also the method of solving it. The Turing machine com­

putes the answer by moving back and forth across the tape,

reading and writing symbols, until the solution is written on

the tape.

I find Turing's particular construction difficult to think

about. To me, the conventional computer, which has a mem­

ory instead of a tape, is a more comprehensible example of a

universal machine. For instance, it is easier for me to see how

a conventional computer can be programmed to simulate a

Turing machine than vice versa. What is amazing to me is not

so much Turing's imaginary construct but his hypothesis that

there is only one type of universal computing machine. As far

63

64 THE PATTERN ON THE STONE

as we know, no device built in the physical universe can have

any more computational power than a Turing machine. To

put it more precisely, any computation that can be performed

by any physical computing device can be performed by any

universal computer, as long as the latter has sufficient time

and memory. This is a remarkable statement, suggesting as it

does that a universal computer with the proper programming

should be able to simulate the function of a human brain.

LEVELS OF POWER

How can Turing's hypothesis be true? Surely some other

kind of computer could be more powerful than the ones we

have described. For one thing, the computers we have

discussed so far have been binary, that is, they represent

everything in terms of 1 and 0. Wouldn't a computer be more

powerful if it could represent things in terms of a three-state

logic, like Yes, No, and Maybe? No, it would not. We know

that a three-state computer would be able to do no more than

a two-state computer, because you can simulate the one

using the other. With a two-state computer, you can dupli­

cate any operation that can be performed on a three-state

computer, by encoding each of the three states as a pair of

bits-00 for Yes, say, and 11 for No, and 01 for Maybe. For

every possible function in three-state logic, there is a corre­

sponding function in two-state logic which operates on this

representation. This is not to say that three-state computers

might not have some practical advantage over two-state com­

puters: for instance, they might use fewer wires and there­

fore might be smaller, or cheaper to produce. But we can say

for certain that they would not be able to do anything new.

They would just be one more version of a universal machine.

A similar argument holds for four-state computers, or

five-state computers, or computers with any finite number of

HOW UNIVERSAL ARE TURING MACHINES!

states. But what about computers that compute with analog

signals-that is, signals with an infinite number of possible

values? For example, imagine a computer that uses a contin­

uous range of voltages to indicate numbers. Instead of just

two or three or five possible messages, each signal could

carry an infinite number of possible messages, correspond­

ing to the continuous range of voltages. For instance, an ana­

log computer might represent a number between O and 1 by a

voltage between zero and one volt. The fraction could be rep­

resented to any level of precision, no matter the number of

decimal places, by using the exact corresponding voltage.

Computers that represent quantities by such analog sig­

nals do exist, and in fact the earliest computers worked this

way. They are called analog computers, to distinguish them

from the digital computers we have been discussing, which

have a discrete number of possible messages in each signal.

One might suppose that analog computers would be more

powerful, since they can represent a continuum of values,

whereas digital computers can represent data only as dis­

crete numbers. However, this apparent advantage disappears

if we take a closer look. A true continuum is unrealizable in

the physical world.

The problem with analog computers is that their signals

can achieve only a limited degree of accuracy. Any type of

analog signal-electrical, mechanical, chemical-will con­

tain a certain amount of noise; that is, at a certain level of

resolution, the signal will be essentially random. Any analog

signal is bound to be affected by numerous irrelevant and

unknown sources of noise: for example, an electrical signal

can be disturbed by the random motion of molecules inside a

wire, or by the magnetic field created when a light is turned

on in the next room. In a very good electrical circuit, this

noise can be made very small-say, a millionth the size of

the signal itself-but it will always exist. While there are an

infinite number of possible signal levels, only a finite num­

ber of levels represent meaningful distinctions-that is, rep-

65

66 THE PATTERN ON THE STONE

resent information. If one part in a million in a signal is

noise, then there are only about a million meaningful dis­

tinctions in the signal; therefore, information in the signal

can be represented by a digital signal that uses twenty bits

(zzo = 1,048,578). Doubling the number of meaningful dis­

tinctions in an analog computer would require making

everything twice as accurate, whereas in a digital computer

you could double the number of meaningful distinctions by

adding a single bit. The very best analog computers have

fewer than thirty bits of accuracy. Since digital computers

often represent numbers using thirty-two or sixty-four bits,

they can in practice generate a much larger number of mean­

ingful distinctions than analog computers can.

Some people might argue that while the noise of an ana­

log computer may not be meaningful. it is not necessarily

useless. One can certainly imagine computations that are

helped by the presence of noise. Later, for example, we will

describe computations requiring random numbers. But a dig­

ital computer, too, can generate random noise if randomness

is called for in a computation.

RANDOM NUMBERS

How can a digital computer generate randomness? Can a

deterministic system like a computer produce a truly ran­

dom sequence of numbers? In a formal sense, the answer is

No, since everything a digital computer does is determined

by its design and its inputs. But the same could be said of a

roulette wheel-after all, the ball's final landing place is

determined by the physics of the ball (its mass, its velocity)

and the spinning wheel. If we knew the exact design of the

apparatus and the exact "inputs" governing the spin of the

wheel and the throw of the ball, we could predict the num­

ber on which the ball would land. The outcome appears ran-

HOW UNIVERSAL ARE TURING MACHINES/

dom because it exhibits no obvious pattern and is difficult,

in practice, to predict.

Like the roulette wheel, a computer can produce a

sequence of numbers that is random in the same sense. In

fact, using a mathematical model, the computer could simu­

late the physics of the roulette wheel and throw a simulated

ball at a slightly different angle each time in order to pro­

duce each number in the sequence. Even if the angles at

which the computer throws the simulated ball follow a con­

sistent pattern, the simulated dynamics of the wheel would

transform these tiny differences into what amounts to an

unpredictable sequence of numbers. Such a sequence of

numbers is called a pseudorandom sequence, because it only

appears random to an observer who does not know how it

was computed. The sequence produced by a pseudorandom

number generator can pass all normal statistical tests of ran­

domness.

A roulette wheel is an example of what physicists call a

chaotic system-a system in which a small change in the ini­

tial conditions (the throw, the mass of the ball, the diameter

of the wheel, and so forth) can produce a large change in the

state to which the system evolves (the resulting number).

This notion of a chaotic system helps explain how a deter­

ministic set of interactions can produce unpredictable

results. In a computer, there are simpler ways to produce a

pseudorandom sequence than simulating a roulette wheel,

but they are all conceptually similar to this model.

Digital computers are predictable and unpredictable in

exactly the same senses as the rest of the physical world.

They follow deterministic laws, but these laws have compli­

cated consequences that are extremely difficult to predict. It

is often impractical to guess what computers are going to do

before they do it. As is true of physical systems, it does not

take much to make a computation complex. In computers,

chaotic systems-systems whose outcomes depend sensi­

tively on the initial conditions-are the norm.

67

68 THE PATTERN ON THE STONE

COMPUTABILITY

While a universal computer can compute anything that can

be computed by any other computing device, there are some

things that are just impossible to compute. Of course, it is

not possible to compute answers to vaguely defined ques­

tions, like "What is the meaning of life?" or questions for

which we lack data, like "What is the winning number in

tomorrow's lottery?" But there are also flawlessly defined

computational problems that are impossible to solve. Such

problems are called noncomputable.

I should warn you that noncomputable problems hardly

ever come up in practice. In fact, it is difficult to find exam­

ples of a well-defined noncomputable problem that anybody

wants to compute. A rare example of a well-defined, useful,

but noncomputable problem is the halting problem. Imagine

that I want to write a computer program that will examine

another computer program and determine whether or not

that program will eventually stop. If the program being

examined has no loops or recursive subroutine calls, it is

bound to finish eventually, but if it does have such con­

structs the program may well go on forever. It turns out that

there is no algorithm for examining a program and determin­

ing whether or not it is fatally infected with an endless loop.

Moreover, it's not that no one has yet discovered such an

algorithm; rather, no such algorithm is possible. The halting

problem is noncomputable.

To understand why, imagine for a moment that I do have

such a program, called Test-for-Halt, and that it takes the pro­

gram to be tested as an input. (Treating a program as data may

seem strange, but it's perfectly possible, because a program,

just like anything else, can be represented as bits.) I could

insert the Test-for-Halt program as a subroutine in another pro­

gram, called Paradox, which will perform Test-for-Halt on

Paradox itself. Imagine that I have written the Paradox pro-

HOW UNIVERSAL ARE TURING MACHINES!

gram so that whatever Test-for-Halt determines, Paradox will

do the opposite. If Test-for-Halt determines that Paradox is

eventually going to halt, then Paradox is programmed to go

into an infinite loop. If Test-for-Halt determines that Paradox

is going to go on forever, then Paradox is programmed to

halt. Since Paradox contradicts Test-for-Halt, Test-for-Halt

doesn't work on Paradox; therefore, it doesn't work on all

programs. And therefore a program that computes the halting

function cannot exist.

T he halting problem, which was dreamed up by Alan

Turing, is chiefly important as an example of a noncom­

putable problem, and most noncomputable problems that do

come up in practice are similar to or equivalent to it. But a

computer's inability to solve the halting problem is not a

weakness of the computer, because the halting problem is

inherently unsolvable. T here is no machine that can be con­

structed that can solve the halting problem. And as far as we

know, there is nothing that can perform any other computa­

tion that cannot be performed by a universal machine. T he

class of problems that are computable by a digital computer

apparently includes every problem that is computable by

any kind of device. (This last statement is sometimes called

the Church thesis, after one of Turing's contemporaries,

Alonzo Church. Mathematicians had been thinking about

computation and logic for centuries but-in one of the more

dazzling examples of synchrony in science-Turing, Church,

and another British mathematician named Emil Post all

independently invented the idea of universal computation at

roughly the same time. They had very different ways of

describing it, but they all published their results in 1937, set­

ting the stage for the computer revolution soon to follow.)

Another noncomputable function, closely related to the

halting problem, is the problem of deciding whether any

given mathematical statement is true or false. T here is no

algorithm that can solve this problem, either-a conclusion

of Goedel's incompleteness theorem, which was proved by

69

70 THE PATTERN ON THE STONE

Kurt Goede} in 1931, just before Turing described the halting

problem. Goedel's theorem came as a shock to many mathe­

maticians, who until then had generally assumed that any

mathematical statement could be proved true or false.

Goedel's theorem states that within any self-consistent math­

ematical system powerful enough to express arithmetic,

there exist statements that can neither be proved true nor

false. Mathematicians saw their job as proving or disproving

statements, and Goedel's theorem proved that their "job" was

in certain instances impossible.

Some mathematicians and philosophers have ascribed

almost mystical properties to Goedel's incompleteness theo­

rem. A few believe that the theorem proves that human intu­

ition somehow surpasses the power of a computer-that

human beings may be able to "intuit" truths that are impossible

for machines to prove or disprove. This is an emotionally

appealing argument, and it is sometimes seized upon by

philosophers who don't like being compared to computers. But

the argument is fallacious. Whether or not people can success­

fully make intuitive leaps that cannot be made by computers,

Goedel's incompleteness theorem provides no reason to

believe that there are mathematical statements that can be

proved by a mathematician but can't be proved by a computer.

As far as we know, any theorem that can be proved by a human

being can also be proved by a computer. Humans cannot com­

pute noncomputable problems any more than computers can.

Although one is hard pressed to come up with specific

examples of noncomputable problems, one can easily prove

that most of the possible mathematical functions are non­

computable. This is because any program can be specified in

a finite number of bits, whereas specifying a function usually

requires an infinite number of bits, so there are a lot more

functions than programs. Consider the kind of mathematical

function that converts one number into another-the cosine,

say, or the logarithm. Mathematicians can define all kinds of

bizarre functions of this type: for example the function that

HOW UNIVERSAL ARE TURING MACHINES?

converts every decimal number into the sum of its digits. As

far as I know, this function is a useless one, but a mathemati­

cian would regard it as a legitimate function simply because

it converts every number into exactly one other number. It

can be proved mathematically that there are infinitely more

functions than programs. Therefore, for most functions there

is no corresponding program that can compute them. The

actual counting involves all kinds of difficulties (including

counting infinite things and distinguishing between various

degrees of infinity!), but the conclusion is correct: statisti­

cally speaking, most mathematical functions are noncom­

putable. Fortunately, almost all these noncomputable func­

tions are useless, and virtually all the functions we might

want to compute are computable.

QUANTUM COMPUTING

As noted earlier, the pseudorandom number sequences pro­

duced by computers look random, but there is an underlying

algorithm that generates them. If you know how a sequence

is generated, it is necessarily predictable and not random. If

ever we needed an inherently unpredictable random-number

sequence, we would have to augment our universal machine

with a nondeterministic device for generating randomness.

One might imagine such a randomness-generating device

as being a kind of electronic roulette wheel, but, as we have

seen, such a device is not truly random because of the laws

of physics. The only way we know how to achieve genuinely

unpredictable effects is to rely on quantum mechanics.

Unlike the classical physics of the roulette wheel, in which

effects are determined by causes, quantum mechanics pro­

duces effects that are purely probabilistic. There is no way of

predicting, for example, when a given uranium atom will

decay into lead. Therefore one could use a Geiger counter to

71

72 THE PATTERN ON THE STONE

generate truly random data sequences-something impossi­

ble in principle for a universal computer to do.

The laws of quantum mechanics raise a number of ques­

tions about universal computers that no one has yet

answered. At first glance, it would seem that quantum

mechanics fits nicely with digital computers, since the word

"quantum" conveys essentially the same notion as the word

"digital." Like digital phenomena, quantum phenomena

exist only in discrete states. From the quantum point of view,

the (apparently) continuous, analog nature of the physical

world-the flow of electricity, for example-is an illusion

caused by our seeing things on a large scale rather than an

atomic scale. The good news of quantum mechanics is that at

the atomic scale everything is discrete, everything is digital.

An electric charge contains a certain number of electrons,

and there is no such thing as half an electron. The bad news

is that the rules governing how objects interact at this scale

are counterintuitive.

For instance, our commonsense notions tell us that one

thing cannot be in two places at the same time. In the quan­

tum mechanical world this is not exactly true, because in

quantum mechanics nothing can be exactly in any place at

all. A single subatomic particle exists everywhere at once,

and we are just more likely to observe such a particle at one

place than at another. For most purposes, we can think of a

particle as being where we observe it to be, but to explain all

observed effects we have to acknowledge that the particle is

in more than one place. Almost everyone, including many

physicists, find this concept difficult to comprehend.

Might we take advantage of quantum effects to build a

more powerful type of computer? As of now, this question

remains unanswered, but there are suggestions that such a

thing is possible. Atoms seem able to compute certain prob­

lems easily, such as how they stick together-problems that

are very difficult to compute on a conventional computer.

For instance, when two hydrogen atoms bind to an oxygen

HOW UNIVERSAL ARE TURING MACHINES?

atom to form a water molecule, these atoms somehow "com­

pute" that the angle between the two bonds should be 107

degrees. It is possible to approximately calculate this angle

from quantum mechanical principles using a digital com­

puter, but it takes a long time, and the more accurate the cal­

culation the longer it takes. Yet every molecule in a glass of

water is able to perform this calculation almost instantly.

How can a single molecule be so much faster than a digital

computer?

The reason it takes the computer so long to calculate this

quantum mechanical problem is that the computer would

have to take into account an infinite number of possible con­

figurations of the water molecule to produce an exact

answer. The calculation must allow for the fact that the

atoms comprising the molecule can be in all configurations

at once. This is why the computer can only approximate the

answer in a finite amount of time. One way of explaining

how the water molecule can make the same calculation is to

imagine it trying out every possible configuration simultane­

ously-in other words, using parallel processing. Could we

harness this simultaneous computing capability of quantum

mechanical objects to produce a more powerful computer?

Nobody knows for sure.

Recently there have been some intriguing hints that we

may be able to build a quantum computer that takes advan­

tage of a phenomenon known as entanglement. In a quantum

mechanical system, when two particles interact, their fates

can become linked in a way utterly unlike anything we see

in the classical physical world: when we measure some char­

acteristic of one of them, it affects what we measure in the

other, even if the particles are physically separated. Einstein

called this effect, which involves no time delay, "spooky

action at a distance," and he was famously unhappy with the

notion that the world could work that way.

A quantum computer would take advantage of entangle­

ment: a one-bit quantum mechanical memory register would

73

74 THE PATTERN ON THE STONE

store not just a 1 or a 0; it would store a superposition of many

l's and many O's. This is analagous to an atom being in many

places at once: a bit that it is in many states (1 or 0) at once.

This is different from being in an intermediate state between a

1 and a O, because each of the superposed 1 's and O's can be

entangled with other bits within the quantum computer.

When two such quantum bits are combined in a quantum

logic block, each of their superposed states can interact in dif­

ferent ways, producing an even richer set of entanglements.

The amount of computation that can be accomplished by a

single quantum logic block is very large, perhaps even infinite.

The theory behind quantum computing is well estab­

lished, but there are still problems in putting it to use. For

one thing, how can we use all this computation to compute

anything useful? The physicist Peter Shor recently discov­

ered a way to use these quantum effects-at least, in princi­

ple-to do certain important and difficult calculations like

factoring large numbers, and his work has renewed interest

in quantum computers. But many difficulties are still there.

One problem is that the bits in a quantum computer must

remain entangled in order for the computation to work, but

the smallest of disturbances-a passing cosmic ray, say, or

possibly even the inherent noisiness of the vacuum itself­

can destroy the entanglement. {Yes, in quantum mechanics

even a vacuum does strange things.) This loss of entangle­

ment, called decoherence, could turn out to be the Achilles

heel of quantum mechanical computers. Moreover, Shor's

methods seem to work only on a specific class of computa­

tions which can take advantage of a fast operation called a

generalized Fourier transform. The problems that fit into this

category may well turn out to be easy to compute on a classi­

cal Turing machine; if so, Shor's quantum ideas would be

equivalent to some program on a conventional computer.

If it does become possible for quautum computers to search

an infinite number of possibilities at once, then they would be

qualitatively, fundamentally more powerful than conven-

HOW UNIVERSAL ARE TURING MACHINES?

tional computing machines. Most scientists would be sur­

prised if quantum mechanics succeeds in providing a kind of

computer more powerful than a Turing machine, but science

makes progress through a series of surprises. If you're hoping

to be surprised by a new sort of computer, quantum mechan­

ics is a good area to keep an eye on.

This leads us back to the philosophical issues touched on at

the beginning of the chapter-that is, the relationship between

the computer and the human brain. It is certainly conceivable,

as at least one well-known physicist has speculated (to hoots

from most of his colleagues), that the human brain takes advan­

tage of quantum mechanical effects. Yet there is no evidence

whatsoever that this is the case. Certainly, the physics of a neu­

ron depends on quantum mechanics, just as the physics of a

transistor does, but there is no evidence that neural processing

takes place at the quantum mechanical level as opposed to the

classical level; that is, there is no evidence that quantum

mechanics is necessary to explain human thought. As far as we

know, all the relevant computational properties of a neuron

can be simulated on a conventional computer. If this is indeed

the case, then it is also possible to simulate a network of tens of

billions of such neurons, which means, in turn, that the brain

can be simulated on a universal machine. Even if it turns out

that the brain takes advantage of quantum computation, we

will probably learn how to build devices that take advantage of

the same effects-in which case it will still be possible to simu­

late the human brain with a machine.

The theoretical limitations of computers provide no use­

ful dividing line between human beings and machines. As

far as we know, the brain is a kind of computer, and thought

is just a complex computation. Perhaps this conclusion

sounds harsh to you, but in my view it takes nothing away

from the wonder or value of human thought. The statement

that thought is a complex computation is like the statement

sometimes made by biologists that life is a complex chemical

reaction: both statements are true, and yet they still may be

75

76 THE PATTERN ON THE STONE

seen as incomplete. They identify the correct components, but they ignore the mystery. To me, life and thought are both made all the more wonderful by the realization that they emerge from simple, understandable parts. I do not feel diminished by my kinship to Turing's machine.