The Tinkertoy Computer and Other Machinations
The Tinkertoy Computer and Other Machinations
The Tinkertoy Computer and Other Machinations
95
book.
https://archive.org/details/tinkertoycomputerOOdewd
Tie taw Computer
AND OTHER MACHINATIONS
L
rrm
1
\ I
11 NKERTDY 1 L I
AND OTHER MACHINATIONS
A. K. DEWDNEY
IS
w. h. freeman and company
New York
Library of Congress Cataloging-in-Publication Data
Dewdney, A. K.
The Tinkertoy computer and other machinations.
[A.K. Dewdney].
p. cm.
Includes index.
ISBN 0-7167-2489-8. — ISBN 0-7167-2491-X (pbk.)
1. Computers. I. Scientific American. II. Algorithm.
III. Title.
QA76.5.D458 1993
004— dc20 93-10478
CIP
1234567890 VB 99876543
Prologue: The Hidden Agenda 1
5 Building a Brain 46
9 Weather in a Jar 93
Index 233
I
!i
J TER
AND OTHER MACHINATIONS
PROLOGUE
TJ
JL JL ow many of us remember Tinkertoys, those down-home kits of
colored wooden sticks and spools with holes in them? Amid our child-
hood constructions of towers or cranes, how many of us pondered the
outer limits of the Tinkertoy world? Did we conceive of contraptions
that reached the ceiling? Perhaps, butwe lacked the kits or the time to
make it happen. Such a Tinkertoy fantasy took place in 1980 when a stu-
dent group from the Massachusetts Institute of Technology constructed
a computer entirely (well, almost entirely) out of Tinkertoys!
From a distance the Tinkertoy computer resembles a childhood fan-
tasy gone wild or, as one of the groupmembers remarked, a spool-and-
stick version of the"space slab" from the movie 2001: A Space Odyssey.
Unlike the alien monolith, the computer plays a mean game of tic-tac-
toe. A Tinkertoy framework called the read head clicks and clacks its
way down the front of the monolith. At some point the clicking myster-
iously stops; a "core piece" within the framework spins and then with a
satisfying"kathunk" indirectly kicks an "output duck," a bird-shaped
construction. The output duck swings down from its perch so that its
beak points at a number —
which identifies the computer's next move in
a game of tic-tac-toe.
What precisely doesthe read head scan as it feels its way down the
monolith? Nothing less than 48 rows of Tinkertoy "memory spindles"
7
8 Theme One Matter Computes
encoding all the combinations of X's and O's that might arise dur-
critical
memory that matches the current state of the game, the core piece spins,
and the computer indicates its move.
The best way to understand how the machine works in detail is to re-
count the story of its creation at the hands of the M.I.T. students: Erlyne
Gee, Edward Hardebeck, Daniel Hillis, Margaret Minsky, and brothers
Barry and Brian Silverman. Most of the group has long since graduated
and entered various computer professions. Perhaps the best-known
team member is Hillis. He was the moving force behind Thinking Ma-
chines, Inc., which produces the well-known parallel super-computer
called the Connection Machine. (Perhaps Tinkertoys have something to
teach us.)
In 1975, when and Brian Silverman were in their sophomore
Hillis
year, they participated in a class project to build something digital from
Tinkertoys. The students sat down to play. One made an inverter —
logic device that converts a binary 1 signal to a 0 signal and conversely.
Another made an OR gate; if either of the device's two input signals hap-
pened to be a 1, then its output would also be a 1. It quickly became clear
to the students that Tinkertoys were "computation universal," the theo-
retical term for a set of components from which a fully programmable
computer can be constructed. Theoretical possibility was one thing, the
practical demands of money and time another.
The demands were met in a rather roundabout manner through
Hillis 's interest in robots. From time to time he had mused openly about
building a robot. Word of his idea somehow reached the ear of Harry
Loucks, then director of the Mid-America Center in Hot Springs, Ark.
Would the students like to construct a robot as a display in the center's
museum? The students agreed in principle, but the project seemed too
Figure 1.1 The Tinkertoy computer: ready for a game of tic-tac-toe.
9
10 Theme One Matter Computes
complicated. Just then the old Tinkertoy dream resurfaced. Would the
center like a computer made out of Tinkertoys instead?
Hillis and company assemble the first Tinkertoy computer
set out to
in a laboratory at M.I.T. The first model, unlike its successor, was a
bulky cube with sides about one meter long. It was impressively compli-
cated. Packed with logic devices made entirely of wooden sticks and
spools, the machine signaled its moves by waving nine flags from the top
of the framework. The prototype Tinkertoy computer had to be taken
apart for the trip to Hot Springs, and once it was reassembled on site, the
machine never quite worked properly again. On the other hand, it did
make an intriguing exhibit. It has been displayed at the Computer Mu-
seum in Boston.
In1979 Loucks contacted the group again. Could they make a new
Tinkertoy computer, one that worked? By this time Silverman was in
Ottawa and Hillis in Boston, each pursuing a new career. Over the tele-
phone Hillis and Silverman worked out an improved design. It was to be
reliable, and that meant simple. They decided to lay out all the possible
tic-tac-toe boards in a row and devise some kind of reading mechanism
that would move from row to row until it found a pattern matching the
current board. The very act of recognition could trigger a pre-set re-
sponse.
While contemplated ways to represent tic-tac-toe boards with
Hillis
digital Tinkertoy components, Silverman analyzed the game. To appre-
ciate the complexities involved even in this childhood pastime, readers
might consult the game tree shown in Figure 1.2. In the middle of the
tree sits the initial board, a three-by-three grid empty of X's and O's.
From this initial board nine new ones can arise, depending on which of
the nine squares X plays. The figure shows just three possibilities; the re-
maining Each of the three boards at the second
six are rotated versions.
level gives rise to other cases.For example, the board in which X plays
the center square and then O plays another square results in two differ-
ent boards. The remaining two boards at the second level each generate
five new boards at the third level.
I pruned many branches from the tic-tac-toe tree by appealing to a
XO o
x X
X
o oX
X
X o X
o o
X X
o o
Figure 1 .2 First three levels of the tic-tac-toe game tree.
Silverman was dealing with a tree, therefore, that was many times
larger than the fragment shown in Figure 1.2. But perseverance paid off,
especially when Silverman employed a computer program that analyzed
the game of tic-tac-toe and discovered that a great many boards could be
collapsed into oneby a forced move. Suppose, for example, that two
row contain O's and the third is blank. The contents of the
squares in a
remaining two rows are irrelevant since an opponent must fill the third
square with an X or lose the game.
Silverman was delighted when he tallied up the final total of relevant
boards: only 48. For each of them he noted the appropriate move by the
machine. The surprisingly short list of possible board positions hear-
tened Hillis. The group converged on Hot Springs, Silverman says,
"with the list of 48 patterns and only a vague idea of how to interpret
them mechanically."
(Readers who have a fanatical bent —
or are stranded in airline
terminals —
may enjoy working out the game tree on a few sheets of
paper. How long does it take, after all, to draw 48 tic-tac-toe patterns?
Four symbols should help sort things out: X, O, blank and a dash for
"don't care.")
12 Theme One Matter Computes
Once settled in Hot Springs, the team assembled the raw material for
their spool-and-stick odyssey: 30 boxes of Tinkertoys, each containing
250 pieces. Some team members put together the supporting frame-
work that would hold all 48 memory spindles. To explain precisely how
the spindles were made, I must digress for a moment and describe the
conventions employed by the team to encode tic-tac-toe positions.
First, the squares of a tic-tac-toe board were numbered as follows:
1 2 3
4 5 6
7 8 9
MEMORY SPINDLE
x !
Figure 1 .3 A memory spindle, which encodes the X's and O's of a tic-
tac-toe board, prevents the core piece from turning.
1 The Tinkertoy Computer 13
The core piece consisted of nine equal sections. Each had its own
finger, a short stick protruding from the rim of a sliding spool. Within
each section the finger could be moved
along the axis of the core piece
into any of three possible positions: one for X, one for O and one for
blank. The core piece could therefore store any possible tic-tac-toe
board by virtue of the positions of its nine fingers as moved by the opera-
tor for each play by human or machine. In Figure 1.3, fingers in the con-
secutive positions 2, 1, 2, 3, 1, 2, 2, 2, 2 would represent the board
shown.
If the current situation of play is stored in the core piece, does the
them fast.
into the limelight. It may yet click its way to victory after victory, a mon-
ument to the Tinkertoy dreams of childhood.
Further Reading
Charles Babbage et al. Charles Babbage: On the Principles and Development of
the Calculator and Other Seminal Writings. Philip Morrison and Emily Mor-
rison, eds. Dover Publications, 1961.
Sing H. Lee and Ravindra A. Athale, eds. Optical Computing. Special issue of
Optical Engineering, Vol. 28, No. 4 (April 1989).
The Apraphulian excursion fooled few people when it
16
2 The Rope-and-Pulley Wonder 17
reader holds a taut rope that passes through the hole. This position of the
rope represents the digit 0. If the reader now pulls on the rope, a creak
and squeal inside the box is heard as a foot or so of rope comes out. The
new position of the rope represents the digit 1.
One can represent numbers with such boxes. Any number from 0
through can be represented by three boxes (Figure 2.1).
7, for instance,
By employing more boxes, larger numbers can be represented. Ten
boxes suffice to represent all numbers from 0 through 1023.
My example of the black box is not arbitrary. The Apraphulians ap-
parently loved to enclose their mechanisms in black wood boxes, small
and large. It may be that the construction of computers was the preroga-
tive of a special technological priesthood. The sight of great assemblages
of black boxes may have kept the masses trembling in awe.
One of the key devices used by the Apraphulians converted a 0 into a
1 and a 1 into a 0. (It is occasionally convenient to speak of 0 and 1 in-
stead of "in" and "out." ) Akin to what modern computer engineers call
an inverter, this interesting mechanism consisted of a box with a hole
drilled in its front and another in its back (Figure 2.2). When someone
(or something) pulled the input rope at the front of the box, an equal
amount of output rope would be played out of the hole in the back. On
IN IN OUT 1
IN OUT IN 2
IN OUT OUT 3
OUT IN IN 4
OUT IN OUT 5
OUT OUT IN 6
^SPRING
PULLEY
H
&
1 1
peering into the box, the reason is obvious: The ropes entering the box
from front and back pass over two fixed pulleys toward one side of the
box, where they attach to a single spring.
As some readers may have surmised already, the digits 0 and 1 were
not encoded so much by "out" and "in" as they were by the direction in
which the rope moved. The point is best illustrated by a box that has no
mechanism in it whatever. A piece of rope enters a single hole in the
front of the box and leaves by a single hole in the back. If one pulls the
rope from the 0 position to the 1 position at the front of the box, the rope
moves from "in" to "out." The direction of movement is toward the
puller. The rope simultaneously moves from "out" to "in" at the back of
the box, but since the direction of movement is still toward the puller,
the rope at the back of the box also moves from 0 to 1.
Two additional mechanisms almost complete the ancient Apraphu-
lian repertoire of computing components. The first mechanism had two
input ropes entering a box. If either rope was in the 1 position, the single
of the box was 1 if one input or the other was 1, today's engineers would
call this an OR gate.
The ancient Apraphulians what we would call an AND
fabricated
gate from four pulleys and a spring (Figure 2.4). The two input ropes, in
reality the same rope, passed over three of the pulleys, two of which
acted as guides. The third pulley acted as a numerical divider; if one
pulled one input rope by the amount x, the third pulley would move
toward the front of the box by the amount Vi x. If x should happen to be
one unit, indicating an input of 1, nothing would happen at the output
end owing to a curious linkage between the third pulley and a fourth one
situated in the back of the box. The third pulley was attached to the
fourth by means of two rods (ropes would do equally well) joined by a
weak spring. When the third pulley moved Vi unit toward the front of the
box, the spring would extend and a parallel rope of Vi unit length would
tighten to take up the slack. If the other input rope were now pulled into
the 1 position, the third and fourth pulleys would move in unison V2 unit
toward the front of the box. Since the fourth pulley acted as a two-multi-
plier, multiplying any forward motion by 2 in terms of its associated out-
put rope, the ensemble would convert the second 1 input into an output
of 1.
20 Theme One Matter Computes
The name AND gate is derived from the fact that the output of this
device is and only if one input rope and the other are in position 1.
1 if
With these components one can build all the control circuits of a digi-
tal computer. These include circuits that compute arithmetic functions,
interpret program code, and direct the flow of information among the
parts of the computer.
Did the Apraphulians construct their computer along such lines?
The evidence is too fragmentary to reach a definitive conclusion, but ar-
chaeo-computologists working with Ripley maintain they have discov-
ered a simple multiplexer within the half-buried complex. In electronic
computers a multiplexer is essentially an electrical switch that directs
the passage of many signals through a single wire. For example, the sim-
plest multiplexer would have two input wires we might label a and b. At
any given moment each wire could carry a 0 or 1 signal. Which of the two
signals, a or b, will be allowed to pass through the device and out a single
output wire d? The answer to that question is the business of a control
wire, c; if it carries a 1 signal, the signal from wire a will be transmitted
along the output wire. If the control wire carries a 0, on the other hand,
the signal in wire b will be transmitted (Figure 2.5).
This reconstructed double-input Apraphulian multiplexer consists
of two AND gates, an OR gate and an inverter. The whole thing is so sim-
2 The Rope-and-Pulley Wonder 21
pie that one dares to believe computer recreationists might build their
own Apraphulian multiplexer at home. Hardware stores might suffer a
puzzling run on rope and pulleys. In any event, one can follow opera-
tions of the multiplexer by referring to Figure 2.5. Ropes a and b enter
the multiplexer from the top left, each going to its own AND gate. Rope c
is split. One branch runs directly to the other input port of the AND gate
to which rope a goes. The second branch of rope c passes through an in-
verter and then runs to the AND gate to which rope b goes. If rope c is
pulled to a value of 1 and held, any sequence of O's and l's sent along
22 Theme One Matter Computes
rope a will be faithfully transmitted through the upper AND gate and on
to the OR gate. At the same time any signal sent along rope b will be
stopped at the lower AND gate. If rope c is relaxed to its 0 position, the
inverter creates a 1 at the lower AND gate. In this case any signal sent
along rope b will now be transmitted through the lower AND gate and
signals on rope a will be ignored.
The OR gate merely ties the two output signals together, so to speak.
If the signal from rope a is currently being transmitted, one can easily vi-
sualize exactly what happens directly from the diagram: If rope a is re-
laxed to the 0 position, the rear pulley in the AND box moves toward the
rear of the box. A 0 is thus transmitted along the output rope and into the
OR box. The other input rope to this box is already in the 0 position
(slack). The natural tension on the output rope d immediately pulls it
into the new position, namely 0. If one pulls on rope a again, the pull is
transmitted along the path that has just been described, with the result
that rope d is retracted.
The matter of slack ropes compels me to take up the question of ten-
sion in the Apraphulian computer. Sometimes, as in the OR gate of the
example, a rope will become slack. There is naturally a danger that such
ropes will slip right off their pulleys. Ripley tells me that in such cases the
Apraphulians used a specially modified inverter with an extremely weak
spring to remedy the problem. Wherever a rope was likely to develop
slack, a "weak inverter" was installed to maintain the minimum tension
associated with the signal 0.
No general-purpose computer is complete without a memory. The
memory of the Apraphulian computer consisted of hundreds of special
storage elements we would call flip-flops. Here again the remarkable
simplicity of the Apraphulian mind is immediately evident. In line with
modern terminology, the two ropes entering the mechanical flip-flop are
labeled set and reset (Figure 2.6). The two ropes were connected over a
series of three pulleys in such a way that when the set rope was pulled
away from the box into the 1 position, the reset rope would be pulled
toward the box into the 0 position. The common rope was connected to
a sliding bar at the back of the flip-flop box. The output rope, physically a
continuation of the set rope, had a large bead attached to it that engaged
a slot in the sliding bar. As the set rope was pulled, the bead rode over the
end of the bar, popping into the slot when the set rope reached the end of
In this position, 1 was "remembered."
its travel.
As a consequence the output rope was held in position until the enor-
mous rope computer changed things by pulling on the reset rope. That
2 The Rope-and-Pulley Wonder 23
SET
RESET
had the effect of pulling the sliding bar away from the bead, releasing it
and playing the output rope into the 0 position. In this case the flip-flop
would henceforth "remember" 0. How were such memory elements
used in the Apraphulian computer?
Ripley and his team were puzzled to discover in the midst of the vast
Apraphulian computer complex a large overgrown field nearly a kilome-
ter wide. Buried just below the surface of the field were several thousand
rotting flip-flop boxes arranged in rows of eight. Ripley, with the aid of
the archaeocomputologists, eventually surmised that the field repre-
sented the Apraphulian computer's main memory. Each row of eight
boxes would have constituted a single, eight-bit "word" in the same
sense that the three boxes of my earlier example would have constituted
a three-bit word. In that vein, imagine a row of three flip-flops that had
been set to the values 1, 0, and 1. They would have stored the number 5.
The content of this particular memory word would have been ac-
cessed by the rope-and-pulley computer as follows. Each flip-flop in the
row would send an output rope to an associated AND box. The other
input to each AND box would come from a special rope used to retrieve
the contents of the word in question. When the ropes were pulled, the
outputs of the AND boxes would be identical with the outputs of the
flip-flops. The AND box ropes would lead to a large assemblage of OR
boxes and thence into a special array of flip-flops we would call a regis-
24 Theme One Matter Computes
ter. A single tug on the rope associated with the word under examination
would place the same binary pattern of rope positions in the register.
The computer's main logic unit undoubtedly would have directed
the flow of information not just from memory to registers but between
registers as well. In particular, by the use of multiplexers and demulti-
plexers (which perform the opposite function of multiplexers), the com-
puter would have sent patterns from register to register. At a specific reg-
ister that we would call the arithmetic register, patterns would have been
combined according to the rules of addition and multiplication.
The Apraphulian computer is believed to have been programmable.
If it was, part of its vast memory would have been used to store the pro-
gram. Program instructions would also have been merely patterns of O's
and 1's retrieved by the same mechanism outlined earlier. Those pat-
terns would in due course have been sent to an instruction register for
interpretation by the computer's logic unit.
It is a pity I can do little more in these pages than to hint at the mar-
61-
A+ B
Further Reading
A. K. Dewdney, "Atomic Computers," in The Magic Machine, W. H. Freeman,
1990.
3-
mil
\
j u RAIN
T_T
JL JL uman intelligence outstrips artificial intelligence because it ex-
ploits physics at the quantum-mechanical level. That is a provocative
position, but one that Roger Penrose, the noted mathematical physicist,
leans toward in his book, The Emperor's New Mind. Although (as
Penrose readily admits) the proposition cannot be rigorously proved at
present, the intriguing arguments in The Emperor's New Mind have pro-
duced some healthy doubts about the philosophical foundations of arti-
ficial intelligence.
stand what they are doing. Next, a brief tour of the Platonic pool hall will
bring us face to face with a billiards table that exploits the classical phys-
ics of elastic collisions to compute practically anything. Moving along to
Erwin Schrodinger's laboratory, we shall inquire after the health of his
cat in order to investigate the relation between classical physics and
26
3 The Infinite Brain 27
be tedious and boring but, once the rules of execution were learned,
rather straightforward. To guarantee the ignorance of the human hard-
ware, he or she has no knowledge whatsoever of Chinese. Yet the Chi-
28 Theme One Matter Computes
nese room seems to understand the story and responds to the questions
intelligently.
The upshot of the exercise, as far as Penrose is concerned, is that
"the mere carrying out of a successful algorithm does not in itself imply
that any understanding has taken place." His conclusion certainly holds
if it is directed at the executing apparatus, whether flesh or hardware.
After all, whether the program happens to be executed by a human or by
a computer makes no difference, in principle, to the outcome of the pro-
gram's interaction with the outside world.
But for this very reason the human in the Chinese room is something
of a straw man: no one would fault a program because the hardware fails
to understand what the program is all about. To put the point even more
strongly, no one would be critical of a neuron for not understanding the
significance of the pulse patterns that come and go. This would be true
whether or not the neuron happened to be executing part of an algorithm
or doing something far more sophisticated. Any strength in claims for
artificial intelligence must surely lie in the algorithm itself. And that is
question emerges. How long does one have to wait to decide whether
the sequence of values remains bounded? The answer is, essentially, for-
ever (Figure 3.1)!
In practice one interposes a cutoff to the computation. In doing so
one inevitably includes a few points that do not belong in the set because
it takes longer for the sequence based on such points to diverge. Difficul-
ties in computing the Mandelbrot set pale in comparison with other limi-
tations on the algorithmic adventure. For example, mathematics itself is
formally considered to be built of axiom systems. Set forth a modest col-
lection of axioms, a rule of inference or two —
and one is in business. A
conceptual algorithm called the British Museum Algorithm generates all
the theorems that are provable within the formal systems of axioms and
inference rules. Unfortunately, the theorems thus produced do not nec-
essarily include all truths of the system.
This discovery, by the mathematician Kurt Godel, dashed hopes of
mechanizing all of mathematics. Penrose takes GodePs famous theorem
as evidence that human intelligence can transcend the algorithmic
method: "... a clear consequence of the Godel argument [is] that the
hole will pass through! The phenomenon is called a state vector col-
it
the photon is reflected in the mirror, it hits the detector, which activates
the hammer, which smashes the vial, which contains the gas, which
kills the cat. From outside the room one cannot know whether the cat
lives or dies.
In the quantum-mechanical world, the two possible events coexist
as superposed realities. But in the classical world,only one event or the
other may occur. The state vector (and possibly the cat) must collapse.
Penrose suggests that current theory lacks a way of treating the middle
ground between classical physics and quantum mechanics. The theory is
split in two but should be seamless on a grand scale. Perhaps the synthe-
verse. For one our minds might turn out to be much more power-
thing,
ful than if the structure went only so far.
Computers are constructed to rule out the influence of any physical
process below a certain scale of size. The algorithm must be protected
from "errors." Our brains may or may not be so structured, as Penrose
points out. Physical events at the atomic level might well have an impor-
tant role to play in thought formation. Processes at the molecular level
certainly do. One has only to think of the influence of neurotransmitter
molecules on the behavior of a neuron. Furthermore, it is a well-known
characteristic of nature to take advantage of physical possibilities in the
deployment of biological operations. If physical structures extend to a
certain level, is there some a priori reason to believe that the brain must
automatically be excluded from exploiting it?
PI
Hi
1st
101
-PUT
III
ill
t».r
and so the substitution and message modules operate twice as fast as the
corresponding modules one level up.
The infinite computer solves the famous "word problem" invented
by the mathematician Axel Thue. In this problem, one is given two
words and a dictionary of allowed substitutions. Can one, by substitu-
tions alone, get from the first word to the second one? Here is an exam-
ple of the problem: suppose the first "word" is 100101110 and the sec-
ond is 01011101110. Can one change the first word into the second by
substituting 010 for 110, 10 for 111, and 100 for 001? The example is
chosen at random. I deliberately refrain from attempting to solve it.
It might happen that no sequence of substitutions will transform the
first word into the second. On the other hand, there might be a sequence
intermediate words might develop that are very long. Therein lies the
problem. As with certain points in the Mandelbrot set, one cannot effec-
tively decide the answer. There is no algorithm for the problem, because
an algorithm must terminate, by definition. The danger is that the algo-
rithm might terminate before the question is decided. Thue's word
problem is called undecidable for this reason. No computer program,
even in principle, can solve all instances of this problem.
Enter the infinite computer. The target word is given to the com-
puter through the main input wire. It enters the first substitution module
Further Reading
Roger Penrose. The Emperor's New Mind: Concerning Computers, Minds, and
the Laws of Physics. Oxford University Press, 1989.
Robert A. Wilson. Schrbdinger's Cat Trilogy. Dell, 1988.
J IP
H
III IF \\ mm
As Gregor Samsa awoke one morning from uneasy
dreams he found himself transformed in his bed into a
gigantic insect.
W T ill the next major advance in robotics spring forth from inex-
pensive machines that crawl, think, and act like bugs? Researchers in the
"insect lab" at the Massachusetts Institute of Technology hope so. They
have spawned a swarm of small robots that behave like your average
arthropod. These insectoids, as I call them, are based on new principles
of robot design and threaten a paradigm shift in the field of robotics.
Until recently, engineers bent on designing a robotic "brain" have
taken a determinedly analytic approach. In this traditional view, they
first decide what the robot will be able to sense; they then consider how
it will analyze sensory inputs and finally how it will plan and take action.
Each step is fraught with complexities that are likely to bog down intri-
cate projects.
Abandoning the traditional approach, Rodney Brooks, director of
the insect lab, has adopted a design philosophy that he calls subsumption
architecture. To apply this philosophy, he starts by designing a network
of processors and hardware that can produce a simple behavior. No be-
havior is added to the system until the behavior it subsumes is up and
running (or walking, as the case may be).
For instance, to design an artificial creature that wanders and avoids
obstacles, Brooks would first assemble a creature that moved randomly
and then add the detectors and processors that would sense objects and
instruct the creature to change direction. In subsumption architecture,
complex behaviors evolve from a variety of simple features.
37
38 Theme One Matter Computes
surprisingly, legs that point straight out from the body are represented
by zero. Alpha Balance adds these numbers together, the sum being a
kind of average. If the sum is positive, it means that on average the legs
are pointing forward. If the sum is negative, the average leg projects
rearward.
The whole trick to walking revolves around the fact that if five of the
legs touch the ground and a sixth is raised, then the insectoid may glide
forward by a small amount merely by swinging all its ground legs slightly
to the rear. If the insectoid then swings the upraised leg forward and
places it gingerly back on the ground, it is one small step for an insectoid
but one giant leap for robotics.
When Ghengis swings a leg to the front, Alpha Balance generates a
sum that is positive and then sends a negative signal to all legs that are
currently down. Their motors whine briefly, the insectoid moves for-
ward a bit and the signal is rebalanced. That is all the Alpha-Balance
Module cares about.
The manner in which the various modules interact to create the act
of walking amounts to an electronic ballet among the modules of the six
leg networks. The action begins for a particular leg when its Up-Leg
Module is activated. The activation sets off a chain of coordinated
40 Theme One Matter Computes
BETAPOS ALPHAPOS
BETA MOTOR
^ ROBOT CHASSIS
ALPHA MOTOR
ALPHA
ADVANCE
ALPHA
BALANCE
Figure 4.2 Basic circuitry that allows Genghis to stand (top) and walk
(bottom).
events among the modules; the Up-Leg Module then signals the Betapos
Module, sending it a number that reflects an upraised leg position. The
Betapos Module, which controls the Beta Motor, normally receives a
positive number (that keeps the leg firmly planted) from another module
called Down Leg. The new, negative signal from the Up-Leg Module
suppresses the positive signal from Down Leg. Consequently, the Beta
Motor raises the leg to a point where its reported position matches the
new signal.
This event triggers a completion state in the Betapos Module, and it
signals this state to three other modules: Alpha Advance, Up Leg and
Down Leg. The Alpha-Advance Module, which controls the back-and-
4 Invasion of the Insectoids 41
forth motion of the leg, sends a strongly positive signal to the Alphapos
Module. The Alpha Motor whirs gently, and the leg waves forward, al-
most as if it were probing the air. When the Up-Leg Module receives the
completion signal, its action is suppressed. When the Down-Leg Module
gets the completion signal, it is activated, and the Beta Motor powers the
leg down to terra firma.
A
master module, called Walk, controls the entire movement by
sending a sequence of signals to the six Up-Leg Modules. But what se-
quence should it use? The triggering pattern most commonly used by in-
sects is called the alternating tripod gait. If the legs are labeled R for right
and L for left, as well as numbered 1,2,3 from front to back, the alternat-
ing tripods are the sets R1,L2,R3 and LI, R2, L3. In normal situations,
an insect like a cockroach will lift the first set, R1,L2, R3, leaving the
other set on the ground. This triangular stance gives stability to the cock-
roach as the first set new positions. Then
of three legs swings forward to
the other set can be raised and swung forward in the same way while the
first set provides stability.
The Walk Module may send out a sequential version of this set of
signals to the six Up-Leg Modules. Or it could send out the pattern some-
times used by stick insects: R3, LI, R2, L3, Rl, L2. There are numerous
possibilities for stable gait patterns.
Perhaps readers can figure out the gait of a millipede machine. If
there are 1,000 legs on each side of an insectoid, devise a gait that will
carry the creature forward without any leg getting dragged along by the
body.
Using the primitive network just described, Genghis could walk but
not very smoothly and not in the manner that Brooks describes as "ro-
bust." For one thing, Genghis wobbled excessively and could not clear
obstacles of even moderate height. The addition of a few more kinds of
AFSM provided a new level of subsumption architecture and a new de-
gree of behavioral competence.
A Beta-Force Module monitors the high strain that develops in a
Beta Motor when its leg has been set down in a position that supports too
much of the creature's total weight. Genghis may have stepped on a
five-centimeter rock, for example. The Beta-Balance Module for that leg
senses the unusually high force and sends a zero message that sup-
presses the leg-down message and makes the offending leg "compliant."
The leg, in other words, gives way a bit, and Genghis compensates for
the high terrain under one of its legs.
42 Theme One Matter Computes
son, it has been programmed with several layers of behavior that were
computer to its single microchip. Squirt
transferred electronically from a
hides in the dark while listening for sounds.If it hears nothing for a few
Graduate student Anita Flynn, who was part of the team that built
Squirt, sees the future of robotics blossoming in even smaller insectoids
she calls gnats. These creatures would be the size of real insects, not to
mention gnats themselves. Their body parts would be fabricated by the
same techniques currently used to etch microcircuits on silicon surfaces.
The biggest bottleneck is the ultratiny motors that gnats will require.
The field of microengineering has already produced gears that would
scatter at a sneeze. In the meantime, Brooks and company have built
Attila, a more sophistocated version of Genghis (Figure 4.3).
Will the insectoids rule some day? Brooks is cautious about making
claims about the future of subsumption architecture, but he plans to
push the idea to its limits. Will we find that as we add ever more complex
layers of behavior that the subsumption approach will continue to work?
44 Theme One Matter Computes
Further Reading
Ivan Amato. "Gearing Down." Science News, Vol. 139, no. 2 (January 12,
1991), pp. 26-27.
A. K. Dewdney. "Braitenberg Memoirs: Vehicles for Probing Behavior Roam a
Dark Plain Marked by Lights." Scientific American Computer Recreations,
March 1987.
A. K. Dewdney. The Magic Machine: A Handbook of Computer Sorcery. W. H.
Freeman, 1990.
Michael C. Smit and Mark W. Tilden. "Beam Robotics." Algorithm, Vol. 2, No.
2 (March 1991), pp. 15-19.
Dill I Bill
In man's brain the impressions from outside are
the imprint of the external world . . .
N
JL ^ eural networks, assemblies of artificial neurons that
ble of learning an
seem capa-
enormous variety of different tasks, have captured the
imagination of researchers in recent years. But they have also intrigued
recreational programmers to the point of despair. Where were the
neural net programs you could write and run on a personal computer?
One now exists. Developed by Edward A. Rietman and Robert C.
Frye of AT&T Bell Laboratories at Murray Hill, N. J. in the late 1980s,
the program I call POLARNET converts polar coordinates to cartesian
coordinates by trial and error. More than this, POLARNET learns the art
of conversion by training on actual coordinates. The underlying algo-
rithm is reasonably simple and the network's learning process is fasci-
nating to watch. I have altered the algorithm slightly to make it easier for
readers to program.
Special, parallel hardware demonstrates the parallel prowess of
neurons best. But even an old-fashioned serial computer can simulate a
neural net with reasonable electronic elan —
if there are not too many
46
5 Building a Brain 47
1/(1 -e~x )
When the network embodied in POLARNET has been trained and is
ready to run, the user of the program merely types in the polar coordi-
nates to be converted. The program then gives the numbers to the two
input neurons and the network does the rest, in a manner of speaking.
With one layer of 30 medial neurons, for example, the input signals
would automatically divide into 60 separate signals, 30 from each of the
two input neurons to the medial neurons, via their synaptic connections.
The medial neurons would then add together the two signals that each
receives, apply its sigmoidal function, then send the signal to both out-
put neurons through other synaptic connections. The output neurons
simply add up the signals they receive. These are the two cartesian coor-
dinates desired.
Some readers may be puzzled by the appearance in Figure 5.1 of
three input neurons instead of two. The third neuron contains no coordi-
nate information but provides, instead, a constant value that interme-
diate neurons may add to their other two inputs. The extra number gives
the network an additional degree of freedom to shift signals by a con-
stant or to avoid the unpleasant effects of zero inputs.
How do you educate a neural net? By giving it a lot of examples.
it is not the neurons that you educate, but the synaptic con-
In truth,
nections between them. Two arrays, called synone and syntzvo, contain
all the synaptic weights. The first array consists of the synapses between
the input neurons and the medial ones. The second array consists of the
second layer of synapses, those connecting the medial neurons to the
output neurons. The net 'learns'
' 9
when it changes the synaptic weights
in these arrays as a result of its experience with the coordinate pairs that
it encounters.
Suppose that one of the training examples involves the conversion
of the polar coordinates (15.7, 110°) to their cartesian equivalents,
5 Building a Brain 49
(—5.37, 14.75). Normally, one would apply the standard sine and cosine
formulas to transform the first set of coordinates into the second. But the
network will split, multiply, sum, and manipulate the coordinates, re-
combining all the numbers at the output end. If the result does not match
the desired cartesian coordinates, the network measures the error in
each.
For example, if the neural network produces (—2.41, 10.82) instead
of (—5.37, 14.75), it will develop two error differences, el and e2, be-
tween the target coordinates and the computed ones: The individual dif-
ferences, —2.96 and +3.93, form the basis for adjustments in the synap-
tic weights all the way through the net, from back to front. The method is
called back-propagation.
In the Rietman-Frye network, the method first calculates how the
weights in the second set of synapses must be changed to reduce the
error if same conversion were to be attempted again. To adjust
the
the synaptic connection between the ith medial neuron and the jth out-
put neuron, for example, POLARNET changes syntwo(i, j) by adding to
it the product of the jth error and the previous output of the ith medial
neuron. Thus,if the jth error is 3.93 and the previous output of the ith
medial neuron was 8.82, the back-propagation method will add the
product
3.93*8.82 = 34.66
to the value of syntwo(i, j), revising it upward by this amount. If the same
coordinate pair were re-submitted to the network revised only in this
one synapse, the new contribution by the synapse to the final sum for
the jth neuron would be 34.66 higher than it was before. If the earlier
sum was 10.82, it would now become 45.48, considerably higher, even,
than the target sum of 14.75.
To avoid problems of overshoot, an additional multiplier must enter
the adjustment formula. A parameter called rate, usually with a value
somewhere in the neighborhood of 0.1, modifies the adjustment to a
kinder and gentler level, say 3.47. Thus, the new value of the jth output
neuron would, in the case of this single adjustment, come to 14.29, very
close (accidentally) to the target value.
Back propagation next alters the values of the first set of weights,
contained in the array synone, by essentially the same method. First,
however, the derivative of the sigmoid function must be applied to the
50 Theme One Matter Computes
for i «- 1 to 2
for j <— 1 to n
syntwo(j, i) <— syntwo(j, i) + rate*medout(j)*error(i)
for i «— 1 to n
sigma(i) <— 0
for j +- 1 to 2
sigma(i) <— sigma(i) 4- error(j)*syntwo(i, j)
sigmoid(i) «— medin(i)*(l-medin(i)) / add error check
for i «- 1 to 2
for j
<— 1 to n
delta <— rate*sigmoid(j)*sigma(j)*input(i)
synone(i, j) <— synone(i, j) + delta
5 Building a Brain 51
t rr" 1 1
I
1 1 i 1
I
i 1 1 ————————
I
i i i i I i i
* m *
J 1 1 1 1 1 I I I I I I I I I I I I I I I I L__L
2 3 4 5
4
Number of learning trials x 10
each medial layer from 15 to 150, the network barely managed a 2 per-
cent error rate!
The foregoing description of the conversion network is just com-
plete enough that readers with a modicum of programming experience
will be able to write POLARNET without the benefit of further advice.
To confirm one detail or another, they only need to consult the two algo-
rithm boxes (Figures 5.2 and 5.4). Others will want to know what the
symbols and variables in these algorithms mean. As usual, the for-loop
stands for the standard iteration loop of which every programming lan-
guage has some version. The left-pointing arrow means the assignment
statement indicated by a " = " or ":=" in most languages.
The algorithm
in Figure 5.4 represents the normal operation of PO-
LARNET. Before the program is run on a single example, however, all
the synapses must be initialized by setting them to a random number be-
tween 0 and 0.1.
The first double for-loop achieves this by running through all possi-
ble combinations of one of the n medial neurons with one of the 3 input
neurons. For each combination, it sets the corresponding value of syn-
one to the product of 0.1 and a random number. Most computer systems
produce random numbers between 0 and 1, so the product of such a ran-
dom number with 0.1 will be a random number that is only one-tenth as
large. The second double for-loop does essentially the same thing for the
array syntwo.
Such small and variable values for the synapse weights are crucial to
getting thenetwork running. If the weights were all the same to begin
with, they would stay the same throughout training and the network
would never change its behavior in a meaningful way. Variety is the
spice of learning.
"Normal operation" refers to the next two double for-loops. The
wave of computation passes through neural nets of this general type one
layer at a time. The first double loop calculates inputs to the medial layer
by adding up the inputs medin to each, as weighted by the entries in syn-
one. The second double loop does the same thing for the output neurons,
adding up the weighted medout outputs. At the end of the second double
loop, POLARNET computes the target values for the cartesian coordi-
5 Building a Brain 53
coordinate conversion
for j «- 1 to 3
(medin(i) <— medin(i) + synone(j, i)*input(j)
medout(i) <— l/(l-exp(-medin(i))) / add error check
for i<— 1 to 2
output(i) «- 0
for j <— 1 to n
output(i) <— output(i) + syntwo(j, i)*medout(j)
compute target(i) / using input(l) and input(2)
natesby using the standard sine and cosine formulas mentioned earlier.
Readers may easily expand this macro-step into the appropriate code.
Thus, target ( 1) is the cartesian x-coordinate and target(2) is the cartesian
y-coordinate of the point the user inputs at the head of the conversion
procedure. The two error terms, error( 1 ) and error(2), play a crucial role
in the next procedure.
The algorithm in Figure 5.2 is the back-propagation algorithm as ex-
plained earlier in the paragraph on educating the synapses. The explana-
tion is already complete enough that readers who compare each section
of the algorithm with the corresponding description should have no dif-
ficulty producing working code. But programmers are hereby warned of
54 Theme One Matter Computes
a special problem that may occur when POLARNET computes the sig-
moidal function during forward propagation or its derivative during
back propagation. Extremely small or extremely large numbers can pro-
duce overflow errors. Specifically, during forward propagation, the pro-
gram must test medin(i) to ensure that exponentiation does not exceed
the available precision. It must also check that the denominator of the
sigmoidal expression is not so close to zero that division will also cause
overflow. The latter test must also be made during back propagation
when the derivative of the sigmoidal function is being generated.
A version of POLARNET that simply sets up initial synaptic
weights, performs one wave of computation, then one wave of back
propagation, would be of little use. But if the blocks following the initia-
lization steps are placed inside a loop, readers may enjoy the privilege of
typing in pair after pair of co-ordinates, watching as the network be-
comes more and more accurate.
Unfortunately, it takes thousands of pairs of polar coordinates to
train the net adequately. For this reason, the same loop should be made
automatic according to the following little recipe in which all steps but
the second refer to blocks within the two main algorithms:
initialization
for cnt <— 1 to 10,000
select random point
convert coordinates
back propagation
output error E
To generate random points (r, a) from within the unit circle, first gen-
erate a standard random number (between 0 and 1) for the radius r. Then
generate a second random number and convert it to an angle a, multiply-
ing by 360 (for degrees) or 2n (for radians). The resulting points will not
be uniformly distributed in the unit circle, but will tend to cluster around
harm the experiment but purists may want
the origin. This bias will not
to remove it by applying a correction function to the first coordinate, r.
Outputting the error E could mean anything from printing the value
to plotting it on the screen. A plot of error values such as those in the
learning curve in Figure 5.3 not onlymakes the program more informa-
tive and absorbing to watch, it becomes an indispensible tool for moni-
toring the progress of the network in many experimental situations.
5 Building a Brain 55
Further Reading
E. A. Rietman. Explorations in Parallel Processing. Tab Books, 1990.
D. E. Rumelhart and J. L. McClelland, eds. Parallel Processing: Explorations in
the Microstructure of Cognition, Vol. 1. MIT Press, 1986.
m
A
JL Ajiyone who has ever seen a termite mound must have been
pressed by the complex patterns of tunnels built by the industrious but
im-
57
58 Theme One Matter Computes
Each table entry therefore has three parts: a symbol to be written on the
current cell, a direction in which to move the tape and a state to enter.
Turing machine and not its tape, it does not take much imagination to
envision a two-dimensional "tape" on which the machine may move
about freely in not one but two independent directions.
Regardless of whether it has a one- or two-dimensional tape, a Tur-
ing machine's table is what ultimately determines its behavior. It is
closely analogous to the program that controls a modern digital com-
puter. In terms of computational capability, two-dimensional Turing
machines are not more powerful than one-dimensional ones. They just
have more interesting patterns of movement over the cells. The pattern
shown in Figure 6.2, for example, was made by a single-state two-
dimensional Turing machine. Its internal table is:
BLACK RED
(RED, LEFT, A) (BLACK, RIGHT, A)
BLACK GREEN
do not know what makes a tur-mite go, since I have never turned one
over.) The apparatus enables the creature to rotate and to move exactly
one square in the direction in which it happens to be facing. Actually, a
turmite's face has no purpose except to let us know which way is for-
ward; its "eyes" do not function. When a tur-mite changes direction, it
merely swivels 90 degrees on its current square before moving to a new
one.
Initially all the squares on the plane, including the one the tur-mite
occupies, are black. Before it moves, however, a tur-mite may change
the color of the square it currently occupies. (The tur-mite's color-chang-
ing organ is locomotory apparatus.) A tur-mite that
as mysterious as its
duplicates the pattern shown in Figure 6.2, for example, must be capable
of painting the square one of two colors (in this case, red or black). To
produce the pattern shown in Figure 6.4, however, a tur-mite has to have
more colors at its disposal.
How does a tur-mite know when to move or when to change the
color of its square? Those actions are controlled by its brain, which con-
sists of a collection of "neurodes," simplified versions of the neurons in
our own brain. A neurode receives signals along fibers that originate at
sensors (which are found on a tur-mite' s underside) or at other neurodes
and sends signals along fibers to effectors (such as the tur-mite's loco-
motory apparatus or its color-changing organ) or to other neurodes.
A neurode fires (sends a signal along its output fiber) if the number of
incoming signals equals or exceeds the neurode's threshold, which is
given by the number written on the neurode. Otherwise, it does not fire.
Because time in the tur-mite' s world proceeds in discrete steps, all excit-
atory and inhibitory signals are sent or received in discrete steps as well.
To illustrate how a tur-mite actually makes a decision, I shall dissect
the brain of two specimens and middle parts of Figure 6.5), both of
(left
which produce exactly the same pattern as that generated by the single-
state two-dimensional Turing machine described earlier. The brain on
the left contains two neurodes that are not connected to each other. Each
neurode has just one input fiber and one output fiber. When the tur-
mite's color sensor detects red, it sends a single signal to the left neurode,
causing the neurode to fire. The neurode 's output two fiber splits into
parts,one going to the color effector (which then colors the entire
square) and the other going to the locomotory apparatus (which then
swivels the creature 90 degrees to the right and advances it one square in
the new direction). On the other hand, when the tur-mite's color sensor
detects black, it sends a signal to the right neurode, causing it to fire. The
62 Theme One Matter Computes
BLACK RIGHT RED LEFT RED LEFT BLACK LEFT FORWARD RIGHT GREEN
Figure 6.5 Three tur-mite brains, two of which (left and center) do the
same job.
6 Dance of the Tur-mites 63
neurode's output, in turn, causes the tur-mite to paint the square red be-
fore turning and heading to the square on its left.
In short, when the tur-mite finds itself on a red square, it colors the
square black and then moves one square to the right. And when the tur-
mite occupies a black square, it changes the color of the square to red,
then turns left and advances one square in its new direction.
The second tur-mite brain is more complicated, but it does exactly
the same job as the first. It was derived by a method I shall presently de-
scribe. The two neurodes both have threshold 2; neither will fire unless
it receives two input signals during the same time increment. Once the
brain is set in motion, one neurode will always fire at each step in time.
The simple behavior embodied in the two neurode circuits just de-
scribed results in the complicated image in Figure 6.2: a red cloud of tiny
squares from which an intricate structure extends straight to infinity.
What causes that sudden sense of purpose in the tur-mite after what
seems a great deal of pointless meandering? The answer has to do with
the pattern of colored squares in the cloud. At a certain point, part of that
J
pattern, in combination with the tur~mite s neurode-based rules, locks
the creature into a repetitive sequence of moves that weaves the struc-
ture. (I wonder any readers can discover the triggering pattern.)
if
This tur-mite also has a very simple brain. It consists of four neur-
odes that are not interconnected. Each neurode executes one of the four
behavioral rules in the manner of the first tur-mite's simplest brain. Turk
is puzzled by the fact that this particular tur-mite produces a pattern
64 Theme One Matter Computes
For example, the colors black and green can be assigned to the vari-
able c by the numbers 1 and 2, respectively. Similarly, the states A and B
can be designated respectively by the values 1 and 2 of the variable s. In
this case, a simulation of a spiraling tur-mite would require the following
arrays:
: :
1 2 1 2
2 1 1 2
2 2 1 1
COi,OR ST/
a
d
aaa a a
DO
d aaa a a
aaa a aa
a aaa a a
aaa a aa
a aaa a a
aaa a aa
a aaa a a
aaa a aa
a aaa a a
aaa a aa
a aaa a a
aaa a aa
a aaa a a
a a aa
m aaa a a
mmm a aa
m
in a
a
aaa a a aa
mmm a aa at
mma
mm a m aam m
m ma aa m m amm
mm m aaa a mm
o aa a
am a
mmm m
mm
mm m
mm
mm
m mmmt
m iiii a
The screen shown in Figure 6.6 captures just one of 1,681 behaviors
Olsen has examined. In this case the tur-mites "cooperated" to build a
"nest." Then one of them, perhaps growing restless, built a complicated
burrow, seemingly toward infinity. The second tur-mite found the bur-
row, followed it to the end, and forced the first tur-mite to follow the
burrow back to the nest. The second tur-mite also worked its way back,
slowly recoloring all the squares! The 1,681 experiments performed by
Olsen amounted to nothing more complicated than placing the first tur-
mite at the origin of the grid, then placing the second tur-mite at one of
—
6 Dance of the Tur-mites 67
Further Reading
Martin Gardner. "Mathematical Games." Scientific American, Vol. 216, No. 3
(March 1967), pp. 124-129.
Martin Gardner. "Mathematical Games." Scientific American, Vol. 229, No. 5
(November 1973), pp. 116-123.
THEME TWO
Matter Misbehaves
more advanced players. At the end of the day everyone who plays by the
rules will have made a microgolf course on a par with his or her talents.
The project is illustrated in its simplest form in Figure 7.1. Here the
program I call hole in one has displayed a single hole on a rectangular
green. A putter appears as a short line segment behind a tiny ball at one
71
72 Theme Two Matter Misbehaves
end of the green. A player angles and positions the putter to aim and
strike the ball toward its target, the cup at the other end of the green.
The simple hole in one version of microgolf is all hit or miss. If the
ballgoes past the cup, it will cross over the course's edge as though it
were not there, disappearing off the screen and rolling into the com-
puter's memory, never to reappear. Even this version of the game has a
certain pleasurable tension to it.
Figure 7.2 A
twilight zone and a demon ball make life difficult for the in-
termediate putter.
for those hesitant or beginning programmers who need just a bit of extra
information to get started. The following description of hole in one
adopts the tried-and-true method of starting with a clear description of
the computation to be performed, usually given in steps as an algorithm.
From there it moves, as fast as possible, to actual fragments of program.
A reader who puts all the pieces together is just a few keystrokes away
from the Micro-Miniature Open!
hole in one first displays the cup ready for play, and then it requests
that a player adjust the putter and putt, hole in one then draws and re-
draws the ball as it rolls across the electronic turf, perhaps into the hole.
From these specifications a crude algorithm for hole in one can be
devised: draw the layout, prompt the user to putt, move the ball many
times (to animate the direction and speed of the putt) and decide each
time whether the ball has fallen into the cup. The algorithm can then be
refined to create the program hole in one. To begin with, the initial
74 Theme Two Matter Misbehaves
layout can be displayed in a few steps that draw the green, cup, ball, and
putter. These steps can be programmed easily.
In order to be helpfully explicit, I shall assume that the reader is writ-
ing a program in the basic language on an IBM PC or a PC-compatible
computer. (Do not be discouraged if you lack the hardware. The pro-
gram is easily adapted to other computer systems.) To be even more ex-
plicit, I shall pretend that all readers have a screen at least 300 pixels
(screen dots) wide and 200 pixels high. All distances on the screen must
be measured from the origin, which is the top left corner of the IBM
screen.
On a 300-by-200 pixel screen it is quite reasonable to draw a rectan-
gular green 240 pixels long and 160 pixels high. To center the layout
more or less on the screen, hole in one places the green 30 pixels from
the left side of the screen and 20 pixels from the top. In short, the hori-
zontal coordinates of the green run from 30 to 270 and its vertical coor-
dinates run from 20 to 180. The green takes shape from the following in-
structions:
7 Micro-Miniature Golf 75
10 SCREEN 1
60 CIRCLE (240,100),5,1
70 XBALL = 60
80 YBALL = 160*RND + 20
90 CIRCLE (XBALL, YBALL),4,1
This vertical line is tangent to the left side of the ball and is 16 pixels long.
The next step of the hole in one algorithm — to 'prompt the user to
'
The variable called SPEED stores the distance in pixels that the ball
moves every time HOLE IN ONE updates its position in the course of a
putt.
The variable AIM stores the ball's direction of motion. Many players
will finddegrees to be the natural unit for entering an angle for AIM.
hole in one therefore accepts an angle between + 90 and — 90 de-
grees as measured from a horizontal line. The extremes represent
strokes that send the ball straight up or down.
Unfortunately, most versions of basic handle angular measure-
ments in units called radians rather than in degrees. Therefore, hole in
one requires a small calculation that converts degrees into radians.
The conversion is based on the fact that 180 degrees equals n radians.
The values of RADAIM and SPEED can be inserted into a formula
that determines the position and orientation of the putter, hole in one
requires the formula to draw the putter poised either to stroke the ball
into the cup or to whack it off the green.
The formula positions the center of the putter behind the ball along
the stroke line and at a distance proportional to the value of SPEED. The
putter should just touch the ball's surfacewhen SPEED equals zero, that
should be at least three pixels to the left of the ball's center. The x
is, it
It might appear at this point that the program is ready to enter the
third phase of its operation, to produce the animation of the ball heading
toward the cup. Has anything been left out? What if a player decides that
the angle of the putter looks wrong. Surely the fallible human being
should be given a second chance. This is done by branching back to line
10 at the player's option.
Here, if the player types any number but zero, the program will branch
back to line 10, where it will clear the screen, redraw the green and
prompt the player again for new values of AIM and SPEED. If the player
types zero, hole in one will proceed to the final phase of its operation,
the one specified much earlier by the phrase "move the ball many times
to animate the direction and speed of the putt."
To move the ball, however, hole in one must increase the x and y
coordinates of the ball independently. To this end, the variable SPEED is
decomposed into two new variables, one called XSPEED in the x direc-
tionand one called YSPEED in the y direction.
78 Theme Two Matter Misbehaves
The instruction on line 280 sets up the simplest kind of loop. A variable
K counts from one to 300 to ensure enough move-and-draw cycles for
the ball to make it to the cup even at a speed of one. Within the loop the
new ball coordinates are updated, and at line 310 the ball is drawn.
Lines 320 and 330 test the ball's coordinates separately to find out
whether the ball is in the cup. If it is not, the program skips down to line
360. If it is, the ball's two speed coordinates are reset to zero, effectively
freezing the ball.
Professionalsmay object to this "for" loop because the program
continues to run even when the ball drops into the cup. hole in one tests
the ball's coordinates until the count X reaches 300. To remedy this, the
amateur golf programmer might add three instructions to the end of the
program. One would test whether the speed of the ball is zero. If the test
is affirmative, a second instruction could print a pat-on-the-back mes-
is not difficult to set up for the six segments of border, which may be
called walll through wall6 without worrying too much about which wall
is which. Each time the main display loop calculates a new position for
the birdie will check to see whether any of the walls has been
ball,
crossed. For example, if walll has been crossed, birdie should reflect
the ball.
When the test and its(possibly) resulting reflection have been exe-
cuted, theprogram checks walll and then wall3 and so on. An interest-
ing problem surfaces at this point. What if the ball, in "striking" one wall
and then receiving its subsequent reflection, now finds itself outside an-
other wall? Is there not a possibility that if the ball is destined to hit a wall
near a comer, it will bounce only from one wall but not from the other?
Readers who ponder the point properly will develop a successful solu-
tion.
Once the ball has done all the rebounding
it is destined to do in the
duffers will find this a wonderful proposition; others will sneer at the
lack of realism.The game lacks that all-important factor, friction!
To allow the ball to be slowed to a stop, birdie multiplies SPEED by
some constant that is less than one, say .995, each time the program goes
through its move-and-test loop. Because SPEED decreases by a factor of
.995 each time through the loop, both XSPEED and YSPEED will also be
multiplied by this constant within the loop.
It may of course happen that the ball eventually slows to zero with-
out having dropped into the cup. In this case birdie must call a halt to the
loop, and so the loop must be not of the "for" type but of the "while"
type. The second kind of loop keeps the cycle going as long as (while)
some condition holds. In this case the condition is that SPEED be greater
80 Theme Two Matter Misbehaves
than some rather small number such as 0.5. At such a point birdie sends
the user back to the interactive part of the program where he or she is
prompted for a putt.
What hazards does the hapless golfer encounter on the second hole?
One hazard is referred to as a circular twilight zone. Having entered the
zone, the ball suffers a random change in its current direction. What
happens is that birdie tests whether the ball lies within the charmed cir-
cle and, if it does, changes the angle RADAIM by a random number be-
tween — 10 and + 10. By planning a careful series of bounces, a good
putter can send the ball around the twilight zone.
The second hazard is harder to avoid. A demon ball orbits the cup at
a fixed distance. It completes an orbit for every 10 cycles of the loop. If
the player's ball happens to touch the demon ball, the player's ball reap-
pears back at the tee-off line. Most readers who have followed the course
this far will probably think of a way to manage this awe-inspiring event.
eagle, as the elaborate illustration in Figure 7.3 shows, has a more
complicated green than birdie. Largely a glorified version of birdie, it
features some advanced hazards. For example, whenever the ball tra-
verses the neck connecting one end of the layout to the other, it experi-
ences a force pulling toward the neck's center. The force is related to the
ball's distance from the centerline, as though the passage were gracefully
banked. There is also a sand trap, where the SPEED is decreased not by a
factor of .995 but by .9. Only the most careful of strokes will get one out
of the trap without sending the ball careening around the layout like a
runaway bullet. The final hazard involves a bit of "rough." Here the ball
becomes lost, disappearing before it even rolls to a stop. How to find the
ball? If you reposition the putter in the right location, the ball will appear
beside it.
Further Reading
Bruce A. Artwick. Microcomputer Displays, Graphics, and Animation. Prentice
Hall, 1984.
" -7
\3
,
s Til KthiIII!ICS
81
82 Theme Two Matter Misbehaves
other and dodging the return fire. Both ships and missiles are subject to
many games developed by students, and most such games soon found
their way into commercial packages that were largely responsible for the
revolution in home computers. Commercial versions of Star Trek have
only recently been introduced, although arcade versions have been
available for some time.
The version of Star Trek described here takes the reader back to the
clandestine romance of the earliest computer games. Furthermore, it
opposite side of the sun. On the screen bright points of light — called
photon torpedos on the television program —
fly outward from the fir-
ing vessel and burn their way around the sun in a gently curving array of
menace. Unless the enemy ship is commanded by a pilot of extraordi-
nary skill, the ship is destined to meet one of the missiles and explode in
a burst of interstellar debris. The screen signals the event with a brief
cloud of dots and announces either victory for the federation or
VICTORY FOR THE KLINGON FORCES.
Because the action near the sun is so intense, cautious players prefer
The main disadvantage of the strategy is the need to
to orbit farther out.
recharge a solar energy cell. The control of each ship depends on its en-
ergy cell. When the cell is spent, the ship must quickly move closer to the
sun to replenish its supply of solar photons. In a distant orbit the photon
stream is weak and the ship runs the risk of becoming a sitting duck.
There is another tricky feature to be aware of in high orbital flight:
the battle space in Star Trek is "toroidal." In other words, if the ship
moves too close to one edge of the screen, it will disappear there and
reappear near the opposite edge.
Each ship has an infinite supply of missiles, but there can never be
more than 10 of them in flight at the same time. The missiles obey the
same laws of physics as the ships do. A missile lasts either until it strikes
a ship (including its own) or until it runs out of fuel. So much for the
game.
The program I call trek is the most ambitious one presented in this
book, not so much because of its complexity as because of its length.
Some of the more standard routines can only be sketched in. Program-
ming neophytes may nonetheless try the project with some hope of suc-
cess and considerable entertainment.
trek cycles through six major sections of code as long as both ships
are operational:
With the possible exception of the first section, many readers will
find that trek is relatively straightforward to write. Reading keys will be
84 Theme Two Matter Misbehaves
•
•
<<
*
Figure 8. 1 Enterprise and the Klingon battle cruiser exchange missiles.
On key(/c) gosub n.
When the "On key" command is executed, the program checks at the
beginning of every subsequent command to determine whether or not
key k was pressed. If it was, the program branches to the command at
8 Star Trek Dynamics 85
Figure 8.2 The Klingon ship is not able to dodge the barrage.
oidal, the new position derived from the acceleration found in the force
table must be calculated modulo the horizontal or vertical distance
across the rectangular display.
Two arrays give the current velocity and position for the two star-
ships and as many as 20 missiles; the arrays are called vel and pos. Each
array has two columns and 22 rows. The first two rows hold starship data
and the next 20 are devoted to missiles. Thus in the first row of vel the
two entries vel(l,l) and vel(l,2) are respectively the velocities in the x
(horizontal) direction and the y (vertical) direction of Enterprise. Simi-
larly, vel(2,l)and vel(2,2) give the two mutually perpendicular velocity
components of the Klingon battle cruiser. A special variable called mis-
num enables trek to keep track of the number of missiles currently in
flight. Misnum ranges from 2 (no missiles) through 22 (20 missiles).
DISTANCE FORCE
10 8.000
11 6.612
12 5.556
800
FORCE =
(DISTANCE) 2
178 .025
179 .025
180 .025
Every time a player presses either direction key, one of the two variables
is increased or decreased by 10 degrees as appropriate.
fdgo and kngo to 0; the throttle is turned off until the next time the thrust
key is pressed.
When the index i becomes greater than 2, the calculation of thrust
can be bypassed because missiles have no thrust. The rest of the updat-
ing loop is devoted to calculating new velocities and positions for the
moving objects on the screen. For each object the numerical magnitude
of the acceleration is added to that of the velocity, and the magnitude of
the velocity added to that of the position. Such a simplistic calculation
is
system of units that assumes the passage of one unit of time for each pro-
gram cycle.
To check for contacts among the various objects the program must
first determine for each ship whether the ship lies on or within the
boundary of the sun. Since trek has already calculated the updated dis-
tance between each ship and the sun, the program needs only to com-
pare that distance with the solar radius, say 10 units. If either ship has
collided with the sun, trek responds with an appropriate screen mes-
sage, such as klingon vaporized; the program then branches to its dis-
play segment.
A second check for contact must determine for each missile whether
the missile lies within a certain small distance of either ship. Here trek
uses a simple but effective shortcut: it finds the difference between the x
coordinates of the missile and a ship, and it does the same for the two y
coordinates. Finally it adds the two differences; the process avoids both
squaring and taking square roots, and the result is nearly as good as the
usual distance calculation. If the sum of the two differences is less than,
say, 4, theprogram scores a hit. A message appears on the screen, such
asenterprise hit by A missile, klingon wins. A single loop carries out
the test for each missile. Its index starts at 3 and ends at misnum, the
number of missiles in space plus 2.
To update the energy levels of the ships the program divides the
solar acceleration obtained from the table by 60. Since the acceleration
increases as the ship moves closer to the sun, such a ship can receive a
more concentrated stream of energetic solar photons. The energy is then
added to a fuel variable called fdft or knfl, depending on which starship is
involved. Each of these variables is decreased by .1 when thrust is ap-
90 Theme Two Matter Misbehaves
their indexes; missiles whose age has reached 25 program cycles must all
be found at the beginning of a contiguous group of missiles in each array,
and so only they must be removed. Similarly, new missiles are always
added at the end of the contiguous group.
Introduce two new variables called old and new, which serve as
pointers to the oldest and newest missiles in each array. As missiles are
removed and added, only the values of old and new must be changed.
One can then apply modular arithmetic to keep the contiguous group of
missiles cycling around in each array. When a new missile is to be added
at index value 23, trek reduces the index modulo 23 to 0 and then adds
3 to avoid replacing one of the starship coordinates by a missile coordi-
nate. The variables old and new undergo the same process. Such a data
structure is called a circular queue. If this arcade trick is used, the posi-
tion-updating segment of the program must be modified: split each sin-
gle loop into two smaller loops, one for ships and the other for missiles.
When a player presses a key to fire a missile,trek first checks a
count of missiles currently activated by that side. If the count is less than
10, trek consults the values of the flag variables fdfr and knfr. If fdfr is 1,
for example, the program adds 1 to the missile count for the Federation,
increases misnum by 1 and then loads the position and velocity coordi-
nates of Enterprise into the appropriate slots of pos and vel. In the pro-
cess the program should add four units to the position coordinates and
two units to the velocity coordinates; in both cases the addition is made
along the same direction as the ship is currently moving. For example,
the horizontal position coordinate of a missile fired by Enterprise is four
8 Star Trek Dynamics 91
times the cosine of ) dor plus the horizontal position coordinate of Enter-
prise; the vertical coordinate increases by four times the sine oijdor. The
initial position of the missile is thereby kept clear of the ship, preventing
immediate destruction by the ship's own photon torpedo. The same
operation applied to the missile's velocity coordinates reflects a relative
launch speed of two units per cycle: a missile travels two units per cycle
faster than the ship that launches it.
The last major section of trek displays the sun, two ships and what-
ever missiles are active at a given time. The program draws a circle of
radius 10 in the center of the screen and then works its way through the
array pos. The Federation and Klingon ships are represented by icons.
One icon is essentially a circle that recalls the famed discoidal Enterprise
with its twin engine booms. The Klingon icon is angular (see Figure 8.4).
Readers are free to attempt any miniature variation on these ships as
92 Theme Two Matter Misbehaves
long as two things are reasonably clear at a glance: which ship is which
and where each one is headed. In drawing the icon for either spacecraft,
trek calls on a list of display points that must be translated and rotated to
reflect the position and orientation of each object. For these operations
the program consults the array pos and the variables fdor and knot.
Missiles are simpler. The display program draws each missile as a
point within a single loop, consulting pos as it goes along.
trek is one disadvantage of the display screens now in
subject to
popular use. Such screens operate in storage mode: an object drawn on
the screen remains there. To avoid a confusing welter of remnant ships
and missiles trek must draw each object twice. It first draws the object
in its old position in black. Then it redraws the object in its new position
in the normal color.
I program to the Trekkers
shall leave the details of initializing the
who attempt it. some of you may find
In spite of arcade programming,
the game too slow; you may be tempted to call it Star Truck. For better
performance try compiling your program, or impose arms limitations on
the number of missiles allotted to each side.
I have described only the bare-bones version of Star Trek. Fancier
but private editions have been built and they continue to propagate;
games have appeared that allow three or more spacecraft, laser guns,
color graphics and status displays. I must thank Jonathan N. Groff of
Clearwater, Fla., for reminding me of this underground classic and for
introducing me to a version of the game that includes an automated
Klingon. Earthlings representing the Federation are continually wiped
out by Groff's program.
, M , — —— 1
Weather ii a Jar
T JL he famed Lorenz attractor seems an apt symbol for the field of dy-
namics and chaos. Its gracefully interfolded wings remind us of the but-
terfly that flutters in Venezuela only to cause a typhoon in Taiwan. But
how many readers know the arcana behind the Lorenz attractor, that it
represents a miniature weather system confined to ajar? I will show how
to simulate the system, not with Lorenz's differential equations, but
with an equivalent dynamical system of equal fascination Lorenz's —
water wheel.
James Gleick tells the story behind the Lorenz attractor in his book,
Chaos. (See the Further Reading section at the end of this chapter.)
More than 30 years ago the MIT weather theorist Edward Lorenz
constructed a primitive weather simulating program that ran on his
Royal McBee computer, "a thicket of wiring and vacuum tubes
that . . broke down every week or so." The program incorporated
.
93
94 Theme Two Matter Misbehaves
hardly expected that his model would hint so strongly in the other direc-
tion.
It happened one day when he typed in data for yet another run and
went off for a coffee to let the Royal McBee buzz along on its own. When
he came back to the office, he discovered to his horror that the run was
for nothing. He had accidently omitted several decimal digits in the
input numbers. A careful experimenter, Lorenz re-entered the data,
fully expecting that the results of the more accurate numbers would
differ very little (if at all) from those of the original run. He was aston-
ished to find that the weather patterns prevailing in his miniature world
at the end of the new run were completely different. He repeated both
runs and got the same result. And again.
Searching for the reasons for the divergence, Lorenz refined and
simplified his weather model. In the end it did not span the whole world,
nor a single country, nor even a county. It consisted of a single convec-
tion cell. Such volumes are fairly common in weather systems: Warm
air, heated by ground radiation rises. As it goes up the air cools. Could a
single convection cell hold the key to strange behavior in his weather
model?
Figure 9.1 shows a single cylindrical volume of circulating air. Heat
applied at the bottom of the cylinder causes the central air to expand and
rise, cooling as it goes. At the top of the cylinder, the air spreads out to
the sides of the cylinder and begins to descend, cooling even more and
completing the circulation. Lorenz used three differential equations to
model events inside the convection cell. When he solved these by com-
puter under different initial conditions and for different values of the pa-
rameter that represented the rate of heating, it did not take him long to
discover an extraordinary phenomenon. In certain cases, a very slight
change in the initial inputs would cause completely different behavior in
the weather-in-a-jar system. The phenomenon now goes by the name
"sensitivity to initial conditions." It is the hallmark of chaos.
The famous Lorenz attractor (Figure 9.1) summarizes all possible
behaviors to which the weather-in-a-jar is "attracted" as it runs. The
lines that wind around and around within the attractor represent trajec-
tories in phase space, a three-dimensional space in which every point
represents a unique combination of velocity, temperature, and rate of
temperature change. As the computer solves the equations iteratively,
the point moves through phase space. When the heat is turned up, so to
speak, the point traces out the strange, nested curves of the Lorenz at-
tractor.Here, you can see sensitivity to initial conditions explicitly.
There are pairs of curves that pass arbitrarily close together within the
9 Weather in a Jar 95
attrac tor's central portion, yet diverge to different wings of the butterfly.
Within a short time, jar weathers that seem nearly identical develop in
completely different ways.
To make your own Lorenzian weather model and watch it run, you
do not have to build a little jar with air circulating inside it (although a
French physicist did something very similar). Nor is it necessary to write
a computer program that solves the three equations iteratively. All you
have to do is write a program that mimics a certain water-wheel, a pre-
cise mechanical analog of weather in a jar.
Figure 9.2 shows a most peculiar water wheel in the act of turning.
Eight leaky buckets hang from the wheel at evenly spaced points. Above
the center of the wheel, a steady stream of water pours into each bucket
as it swings underneath. Each bucket leaks at the same rate and, as it fol-
lows the wheel around, loses water.
The Lorenzian water wheel has no direct application that I am aware
of — except to illustrate the behavior of the convection cell. Here, water
is the analog of heat. Each bucket represents a portion of the cell's air
that loses heat as it circulates within the cylinder. The analog does not
suffer much from this discrete form of air and, provided there are
enough buckets, the exact number is not important. The varying speed
of the water wheel recreates the behavior of the air within the weather
cell.
And what strange behavior it is! With water pouring slowly onto the
wheel after a discreet clockwise nudge, it will rotate gently clockwise,
96 Theme Two Matter Misbehaves
vary with the speed of the wheel. The algorithm in Figure 9.3 consists of
four parts, an input segment, a dynamical computation segment, a rela-
belling segment, and a display segment.
The user of WEATHER WHEEL
inputs the rate / at which water
enters the system through the spout. The initial velocity v simply sets the
wheel turning. Note that the initial velocity must be non-zero.
***compute dynamics***
dt <r- abs(l/v)
bucket(O) <- bucket(O) + f *dt
for k <- 0 to 7
if bucket(k)>=g*dt
***display wheel***
(display procedure)
routine covers the lower area of the square to an appropriate height with
graphic water. Two options enter the picture in this case: How much
water should buckets be allowed to hold?
Readers who place no limits on bucket capacity must, nevertheless,
limit the graphic fill to the top of each bucket. Readers who limit the
amount in their programs will not face this problem. On the one hand,
9 Weather in a Jar 99
Further Reading
James Gleick. CHAOS Making a New Science. Viking, 1987.
n
1 PORTRA J
Saul bellow
100
10 A Portrait of Chaos 101
x «- rx(l — x)
The arrow indicates that once r, x, and 1 — x have all been multiplied to-
gether, the resulting number becomes the new value for x, that is, it re-
places the old value. The process can be repeated so that the formula
continually spews out new values for x.
mals (x) approaches the maximum (1), the food supply (1 — x) dwindles
to nothing (0). The parameter r expresses the proportionality. It may be
thought of as the fecundity of the population. The higher the value of r,
the more quickly the population will rebound from any disaster.
Strangely enough, higher values are precisely the ones that lead most
quickly to chaotic populations.
Although the equation is too simple to represent real animal popula-
tions, it can serve as a rough approximation to population dynamics.
If the parameter r is less than 2, the sequence of numbers produced
is magnified, the enlarged region looks very much like the whole.
The fate of the hypothetical populations is clearly portrayed in Fig-
ure 10.1. The diagram is produced by plotting r against the values to
which the logistic formula converges. The result is a kind of tree. One-
point attractors make up the trunk; two-point attractors, the first pair of
branches. At an r value of 3.57, the onset of chaos can be seen clearly:
the branches suddenly proliferate.
Chaos can be characterized using the Lyapunov formula. For each
dynamic system, the formula produces a single number, the Lyapunov
exponent. If the number is less than 0, the system is stable. If the number
is greater than 0, the system is capable of chaotic behavior.
The Lyapunov formula is complicated, but it can be translated into a
series of simple steps. In the case of the logistic system, we start with one
particular value of r. The logistic formula is iterated, say, 600 times, so
that the numbers converge to whatever attractor is present in the sys-
tem. After the numbers settle down, it is safe to compute the Lyapunov
total <- 0
forn «- 1 to 4,000
x <— rx(l — x)
fofo/ <- total + ((log|r - 2rx|)/log 2)
//op <- total /4.000
The algorithm first sets fota/ = 0 and then iterates the logistic formula
4,000 times. On each iteration it computes a new value for total by add-
ing the old value of total to the logarithm of r |
—
2rx\ divided by the loga-
rithm of 2. (The vertical bars indicate the absolute value of r — 2rx.) The
quantity |r — magnitude of the rate at which succes-
2rx\ represents the
sive values are growing or shrinking.When it has added up all 4,000 log-
arithms, the algorithm divides the sum by 4,000. The result, which has
been assigned to the variable lyap above, is something like an average
logarithm of change. The result closely approximates the Lyapunov ex-
ponent.
Readers who demand precision can more accurately estimate the
Lyapunov exponent by increasing the number of iterations and, at the
end of the procedure, by dividing the sum of logarithms by the number
of iterations.
Iencourage readers to use the algorithm above to calculate the Lya-
punov exponent for r equal to 3. Then compare the result with that ob-
tained when r equals 3.57. The first number should be slightly negative,
indicating a stable system, and the second number should be positive, a
warning of chaos.
Figures 10.2 through 10.4 are all based on the logistic equation.
Markus merely adds one twist of his own. To produce his pictures,
Markus used periodic forcing. This means that r systematically changes
its value, alternating between two fixed numbers, a and b. In other
values, it may take on a specific value, say, 0.015 for a number of these
initial values. Then the exponent may suddenly switch to another value,
0.142, to which it may stick for several more successive initial x values
before reverting to the first value. The switching back and forth can be-
come quite frequent.
Lyapunov space often contains darkish bands that run along the
spikes. These represent superstable regions in which the underlying
forced logistic systems exhibit the most regular behavior.
The Lyapunov space generated by alternating a and b values con-
tains a tiny fleck that resembles a swallow. The fleck is enlarged in the
image at the bottom of Figure 10.2. There, just off the swallow's tail, lies
10 A Portrait of Chaos 107
another little fleck. Readers are free to guess just what it might turn out
to be when it is similarly enlarged.
The appearance of self-similarity in the figure should not surprise
students of chaos. Structures that exhibit self-similarity are more often
than not produced by chaotic processes.
The methods used to create the mother swallow and its offspring can
The images in
be varied slightly to generate a host of different creatures.
Figures 10.3 and 10.4 differ only in the a and b value sequences that
were used. For example, a jellyfish —
the yellow tentacled blob shown
in Figure 10.3 —
is spawned from a sequence that begins b, b, a, b, a and
that repeats over and over again.
Figure 10.4 resembles the cover of a science fiction magazine from
the 1950s. I call it Zircon Zity because it is obviously the futuristic me-
tropolis of the Zirconites (whoever they are). The underlying sequence
of the zity is bbbbbbaaaaaa. By repeating this sequence while calculating
the Lyapunov exponent, a computer can build the city with all its deli-
cate bridges, golden spaceships, and interplanetary walkways.
What does all this have to do with enzymes, carbohydrates, and nu-
trition? At best, a small region in some Lyapunov map might actually de-
scribe the dynamics of enzymes breaking down carbohydrates. But per-
haps more to the point, Markus's work makes it possible to visualize the
dynamics of periodic forcing. One might say he has made chaos easier to
digest.
A Lyapunov Program
For those readers who wish to explore Lyapunov space, I can
give a few hints about how they might create the appropriate
program. The heart of the program should be a double loop
that runs through values of a and b. To compute the Lyapunov
exponent for each combination of a and b, the program should
include a routine based on the algorithm given on page 103.
The routine should allow various sequences of a's and b's to be
stored in an array. The routine could enable the user to specify
the sequence by filling the array with 0's (representing a) and
l's (representing b).
With each iteration of the Lyapunov loop, a counter called
index may be used to step through the array. Each time the
108 Theme Two Matter Misbehaves
inner loop produces a new value for index, it will look up the
current value of either a or b, depending on whether it finds a
0 or a 1 in the array at the value of index. Finally, the program
should include a table of logarithms to help speed the
computations. Indeed, it may take hours for a personal
computer to generate a single image in Lyapunov space.
Further Reading
A. K. Dewdney. The Magic Machine: A Handbook of Computer Sorcery. W. H.
Freeman, 1990.
Mario Markus. "Chaos in Maps with Continuous and Discontinuous Maxima/'
Computers in Physics, September/October 1990, pp. 481-493.
Designer Fractals
S
V^*J o, mathematicians observe, if fleas are all the same except for size,
then all their hopping and rotations reduce to affine transformations.
What exactly is this high-sounding term? It is nothing more than a for-
mula for scaling, turning, displacing, and sometimes even distorting an
object geometrically. As in the case of fleas, a single affine transforma-
tion can be applied repeatedly to produce miniature replicas of the origi-
nal. People who prefer not to waste their talents on propagating fleas can
apply these rather simple geometric formulas to generate images as in-
tricate as the paintings in museums or landscapes in nature.
A small set of affine transformations can create such abstract works
as the Sierpinski triangle in Figure 11.1. A larger group of transforma-
tions can re-create landscapes such as the Monterey coastline shown in
Figure 11.2. In fact, any image whatsoever can be reproduced from a
series of affine transformations. The trick is knowing which ones to
choose. Along these lines, Michael F. Barnsley of Iterated Systems, Inc.,
in Norcross, Ga., has discovered a general procedure for reducing an
image into a series of affine transformations. His technique has opened
up some exciting possibilities for the transmission of television and
computer images. Before I describe his work, let me say a bit more about
affine transformations.
When an affine transformation is applied to a figure such as a triangle
or a leaf, it moves the points that make up the figure to new locations. In
the process, the transformation may translate, scale, rotate, and stretch
109
110 Theme Two Matter Misbehaves
lation in size and proximity to the second triangle as the second does to
the first. One can apply the transformation repeatedly and watch the tri-
angles trace a path into infinitesimal oblivion.
If one applies an infinite series of affine transformations to an object,
the result has the property of being self-similar, that is, a magnified por-
tion of the result looks like the whole. Hence, a series of affine transfor-
mations can create a self-similar object, better known as a fractal.
All affine transformations have the same kind of formula for moving
the points of a figure around in a plane. The original point can be defined
by two coordinates, which I will call x and y. The new point has the coor-
dinates (x\ y'). The transformation is then defined by two equations:
x' = ox + by + e
y' = cx + dy + f
and a, d, e and / were all 0? The two equations that define the affine
transformation would become:
Ill
X' = .by
Y'= - .5 x
To determine its effect on a specific point, say (1,2), one merely applies
the formulas. Thus, becomes (.5 X 2), which equals 1, and similarly y'
becomes — .5. If one carries out this operation for a great many points
in a triangle, a general pattern emerges. The entire triangle seems to have
rotated 90 degrees clockwise and simultaneously to have shrunk to half
its former size. If e and /were both equal to 1 instead of 0, then not only
would the triangle be reduced and rotated, it would also be shifted one
whole unit up and to the right.
quadrant and shouts "Bob." Abby lets the ball bounce only once, swings
her racket and hits the ball over the net so that it lands in Bob's quadrant.
Abby is not allowed to hit the ball to just anywhere in Bob's quad-
rant, however. To make the perfect shot as prescribed by the rules, she
must first judge where the ball landed in her own quadrant. This task is
rather simple because the tennis ball, which has been soaked in black
ink, leaves a mark on the court. Abby creates a mental map of the ink
mark within the entire court. She superposes the map on Bob's home
quadrant by shrinking it to half its dimensions. The position of the su-
perposed ink mark on Bob's quadrant is where she must hit the ball. If
the ball had landed in the center of the whole court, Abby would have
been required to hit the ball to the center of Bob's quadrant. In this case,
however, the ball landed two meters north and six meters west of the
center of the whole court. Because the dimensions of Bob's quadrant
and the others are half those of the court as a whole, Abby should hit the
ball one meter north and three meters west of the center of Bob's quad-
rant.
Abby's great shot represents an affine transformation. She has cre-
ated a second ink mark, which has been displaced to Bob's quadrant and
is closer to its boundaries.
After Abby's return, the umpire calls out "David." Bob rushes to
catch the ball on the bounce and makes a perfect shot into David's home
quadrant. The umpire, perhaps a bit maddened by the sun, then starts to
shout names at random. Yet Abby, Bob, Carla, and David, being con-
summate calculators, play a flawless game. Each player always hits the
ball to just the right point. After a while, however, the ink marks left by
the tennis ball create a fractal pattern on the court. In fact, the marks
eventually blacken the court uniformly. That is when the umpire calls a
halt to the play.
Figure 11.3 shows the early stages of the game. After Bob made his
first shot to David, the umpire called "David" for a second time. This did
not present a problem, except for David of course. He hit the ball toward
the southeast corner of his own quadrant because his quadrant is in the
southeast corner of the whole court. After the ball bounced in David's
own quadrant, the umpire called "Carla," and David hit the ball to her
quadrant according to the rules. If the umpire had yelled "David" again
and again, David would have had to direct the ball ever closer to the
southeast corner.
Fractal tennis illustrates a key feature of iterated-function systems.
A single point mapped repeatedly by a random sequence of affine trans-
114 Theme Two Matter Misbehaves
CARLA'S DAVID'S
QUADRANT QUADRANT
'DAVID' 'CARLA'
formations will eventually "fill in" a certain region. The umpire's calls,
the game come into its own when it is played on the leaf of a black
spleenwort fern. The game still involves four players, but unlike the
classic smooth square of the practice court, the fern-leaf court has a
jagged outline. As Figure 11.3 shows, when the umpire calls "Abby,"
one of the players must hit the ball to Abby's leaflet. The point where the
ball must land depends on the position of the last bounce relative to the
1 1 Designer Fractals 115
whole leaf. In this way, the call "Abby" corresponds to an affine trans-
formation. The call "Bob" is also an affine transformation that sends the
"ball" to the corresponding point in the leaflet at the left side of the leaf
near the base. The call "Carla" does the same thing in relation to the leaf-
let at the right side of the base. Finally, the call "David" sends any point
of the leaf as a whole into the straightline segment representing the stem
at the base of the leaf.
When the point is put into play, the umpire begins to call the names
of these four players in arandom order. The point might start in the mid-
dle of the leaf,hop to the middle of Bob's leaflet, then shift to a point in
Carla's leaflet and so on. The game goes on for 10,000 hits. As it con-
tinues, an image of the fern leaf, delicate and organic-looking, emerges
(see Figure 11.4).
There is one element of the game that I have yet to describe. The se-
quence is not quite random: the judge favors certain players as he makes
the 10,000 calls. The case of the spleenwort leaf provides a perfect ex-
ample. Abby's leaflet has the largest area. Therefore, if the umpire is just
as likely to shout "Abby" as any of the other three names, Abby's leaflet
will fill in more slowly than the others'. To adjust for this, the umpire
gives Abby the lion's share of play. In fact, the amount is proportional to
Abby's share of the total leaf area.
The umpire calls "Bob" and "Carla" roughly the same number of
times, the numbers in both cases being proportional to the areas of their
respective leaflets. Because the stem has the least area of all, David will
get to play the least.
Perceptive readers may have noticed that the four transformations
associated with the spleenwort leaf change the basic outline into four re-
gions that approximately subdivide the outlined area. Barnsley calls this
subdivision a collage. He and his colleagues have found a theorem that
guarantees good fractal reproduction. The collage theorem says that the
more accurately the outline of a fractal shape is approximated by a col-
lage of a certain number of affine transformations of the shape, the more
accurately the iterated-function system will reproduce the original frac-
tal.
dle, of course, and so do the triangles in their "corners. " The final object,
insofar as any finite scheme can reproduce it, is literally full of triangular
holes at all visible scales of magnitude.
Readers who have computers at their command can reproduce the
Sierpinski triangle by following an algorithm for the appropriate iter-
ated-function system. I will describe the algorithm in general terms. It
begins by setting the coordinates x and y equal to 0. Then three main
operations are repeated 10,000 times: First, one of the affine transfor-
mations is chosenrandom. Second, the chosen affine transformation
at
is applied to the current coordinates of the point, namely, (x, y). The re-
sult is a set of new values that are now deposited in the x and y symbols,
so to speak. Third, a test is made to determine whether 10 iterations
have been carried out.
The third step ensures that the ball has been in play long enough to
be somewhere in the court. In a general scheme such as this, one does
not know in advance the best place to start the ball bouncing. Hence, one
1 1 Designer Fractals 117
starts it from the origin and assumes that after 10 iterations it has pretty
well "settled into" regular play.
This algorithm will work for any iterated-function system if one adds
an extra feature. Because an affine transformation must be chosen at a
rate that depends on the area it must cover, the algorithm must select
each transformation with a certain probability.
What are the formulas for the affine transformations that produce
the Sierpinski triangle? At the beginning of this chapter, I described the
type of formula one needs, and I mentioned that six coefficients deter-
mine the transformation's character. The coefficients for the Sierpinski
triangle are given below.
a b c d e f
(1) .5 0 0 .5 0 0
(2) .5 0 0 .5 .5 0
(3) .5 0 0 .5 .5 .5
several bits to specify a gray level or color at that point. Ordinary pixel-
by-pixel storage might therefore take up a million bits or more. One can
apply standard compression techniques to such pictorial data to store
the same information in a smaller space, but iterated-function systems
118 Theme Two Matter Misbehaves
Further Reading
Michael F. Barnsley. Fractals Everywhere. Academic Press, 1988.
Benoit B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman, 1983.
The number of distinct scales of length of natural
patterns is for all practical purposes infinite.
Q
W-^ince Benoit Mandelbrot first coined the term, we have learned
B.
to look for fractals everywhere, especially in nature. Although nature
contains no true fractals, in which every part contains an infinite regress
of similar parts, it abounds with structures that produce the illusion. One
may find self-similar structure in certain leaves and plants, in shorelines,
perhaps even in the structure of galaxies and galactic clusters. But a
chapter on the elements of fractal generation may as well practice on the
traditional elements of nature: earth, air, fire and water.
Earth may be symbolized by a jagged mountain, air by a puffy fractal
cloud, fire by a fractal flame and water by an infinitely curly wave. Air
and water are shown in Figures 12.1 and 12.3 but readers can supply
earth and fire for themselves, based on what they glean from this chap-
ter.
119
120 Theme Two Matter Misbehaves
sub-cloud, then a translation (shift) of the sub-cloud into its target posi-
tion.The effect of such a transformation is to move any point in the big
cloud into the corresponding point of the sub-cloud. Thus a point near
the top of the big cloud will end up close to the top of the sub-cloud.
To set up an affine transformation, you must first determine a rea-
sonable coordinate system, one that makes the transformations simple.
By placing the origin at the center of the big cloud, the transformations
are easy to obtain, especially if the exercise is carried out on graph paper.
At the end of this chapter, I will explain exactly how I obtained them.
The general form of an affine transformation is:
x'«-ax + by + e and
y'«-cx + dy + f
The values of a, b, c, d, e, and /are best presented in a table. For the
cloud the table has six rows, one for each sub-cloud in the collage. The
sub-clouds are labelled with capital letters that have nothing to do with
lower case letters just mentioned. For each sub-cloud, naturally, there is
122 Theme Two Matter Misbehaves
a corresponding transformation that maps the whole cloud into that par-
ticular sub-cloud:
a b c d e f
x <— x'
1. x «- 0, y «- 0
2. forn <- 1 to 20,000
Z <- random (A,B,C,D,E,F)
(x,y) «- Z(x,y)
if n > 10 then plot {x,y)
Within the loop, I have condensed what will ultimately be many pro-
gram instructions into single lines. For example, the 'instruction" Z <—
'
the third at .52 and so on. In each case, merely add the current probabil-
ity to the ongoing sum.
If a random number between 0 and 1 is chosen, it must lie some-
where on the unit line. The segment that it happens to fall into will be the
124 Theme Two Matter Misbehaves
1. r <— random
2. if r < .21 then transform A
3. if r > = .21 and r < .30 then transform B
4. if r > = .30 and r < .52 then transform C etc.
Even this algorithm is not quite complete. What, after all, do the
commands "transform A," and mean? The structure that I have
so on,
chosen for CLOUD must expand each of these commands into little al-
gorithms of their own, algorithms that correspond, in fact, to the second
line of the loop.
To actually carry out transformation B, for example, requires two
steps:
every time a new point (x,y) in the virtual cloud is computed by the pro-
gram, it must convert these coordinates into a new point (w,z) in the dis-
play cloud.
The virtual cloud happens to be 14 units (of graph paper) in diame-
ter.To create a display cloud that is, say 112 pixels in diameter, the vir-
tual coordinates must each be multiplied by 8. But that is not enough.
They must also be translated from the left edge of the screen over to the
middle. The following statements will handle the case of a 20- by-100
screen that has its origin in the upper left corner. The variables w and z
represent the display coordinates.
1. w <- 8x + 100
2. z «- 8y - 50
This completes the description of CLOUD. I will not claim for a mo-
ment that I have selected the best possible collage for my cloud. Others
may find a better arrangement of sub-clouds that fill the overall shape in
a more natural or aesthetically exciting fashion. In general, the more
open space within the collage that is not covered by sub-figures, the
more open and diffuse the resulting graphic image will be.
The second IFS fractal represents the element water. This time I will
use not a two-dimensional collage but a one-dimensional one. Figure
12.4 shows a pair of spirals joined together at their apexes to produce a
shape that, overall, looks somewhat like a wave. The shape may be re-
garded as a one-dimensional "region" that may be sub-divided into
spheres of influence for three separate transformations, A, B, and C.
The first transformation, A, maps the entire double-spiral wave into
a smaller version of itself still centered on the apex. This transformation
not only shrinks, but it rotates the figure so that it still fits the smaller
portion of itself. The second transformation maps the entire wave into
the small wavelet labelled B Readers will see at once that
in the figure.
this is simply a smaller version of the entire double spiral placed at the
trailing edge of the large wave.
But what about the other half of the wave, the trough into which it
threatens to crash with a fractal roar? The third transformation, C, sim-
ply rotates the entire figure by 180 degrees so that whatever gets gener-
ated on one side of the image has a chance of being mapped over to the
other side in order to complete the picture. In fact, because the right half
of the wave has half the area, the third transformation gets half the ac-
tion. The probability with which the program I call WAVE uses transfor-
a b c d e f p
C -1 0 0 -1 0 0 .50
mation C is exactly .5. The table above shows the IF system I developed
to produce the wave image. Readers are free to write their own version
of WAVE, using these equations or others they might wish to derive for
themselves.
This raises the question, of course, "Just how do you find those
equations?" Insofar as they involve only contractions, rotations, and
translations, they can be calculated on the basis of measurements taken
directly from the figure you have drawn on graph paper.
Consider, for example, the subcloud B in the cloud collage in Figure
12.2. Its diameter, as measured it on squared paper, was 3 units while
I
the cloud as a whole had a diameter of 14 units. This meant that the pro-
gram would have to shrink the large cloud by a factor of 3/i4 or .214.
Next, I decided that the small cloud should reproduce the whole cloud at
an angle of 68 degrees in the positive sense. This would turn it well to the
left so that the same surface would be reproduced in the cloudlet at the
o = .214cos(68) b= .214sin(68)
c = .214sin(68) d= .214cos(68)
tor, the first four numbers in row B of the cloud's IFS table emerge.
The translations, e and /, turn out to be especially easy to calculate.
The shrunken and rotated sub-object has the same relation to the origin
as the whole object does. Where does the origin go when the sub-object
is at last translated to its final resting place? The horizontal distance is e
subflames, two at the base of the flame and one at the top.
This much completes the excursion into the elements of IFS sys-
tems, not nature's workshop, but your own.
Further Reading
Michael F. Barnsley. Fractals Everywhere. Academic Press, 1988.
Benoit B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman, 1983.
THEME THREE
Mathematics Matters
T>
JL %oss Honsberger has spent more than two decades collecting
mathematical morsels for general consumption. Attending one of his
rare public lectures, I had the pleasure of sampling one of his mathemati-
131
132 Theme Three Mathematics Matters
swear that what follows are Honsberger's exact words, but he readily
admits to a certain, broad similarity:
"It takes no genius to see that the plane divides the cone into two
pieces. But it was Dandelin's idea to insert a sphere into each piece. Like
an over-inflated balloon, each sphere contacts the wall of the cone and
touches the elliptical plane at a certain point. But where? One can imag-
ine Dandelin's heart leaping at the thought that the two spheres might
touch the plane at the two focal points of the ellipse."
Honsberger places his marking pen on the transparency. He labels
the two points of contact by the symbols F and G. Are these the foci of
the ellipse?
"Let's take a look atwhat clever old Dandelin did. First, through any
point P that we care to on the ellipse, we may draw a straight line
select
that runs up the side of the cone to its tip. Second, the line will touch the
two spheres at two points, say, A and B. No matter where we pick P to lie
on the ellipse, the length of AB will be the same.
"Ah, but that gives it away! The distance from the point F to P equals
the distance from P to A. After all, both PF and PA are tangents to the
same sphere from the same point. By the same reasoning, the distance
from the second point, G, to P equals the distance from B to P. Are we
not finished? PF + PG = PA + PB, and the latter sum is just the (con-
stant) length of AB.
"Now isn't that the darndest thing?" Honsberger sounds rural.
As I look around the lecture hall, students appear stunned. Profes-
sors alternately smile and frown. One of them behind me murmurs,
"Well, I'll be."
Without pausing for a breath, Honsberger serves up the next morsel.
We find ourselves staring at a slide of a peculiar board game.
"Here's a simple little exercise in checker-jumping. I imagine that
such a clever audience will have no trouble figuring this one out." A dev-
ilish gleam invades his eye, a warning that something unusual is about to
happen.
The slide shows a grid of squares with a line drawn through it (see
Figure 13.2). Honsberger explains the rules: solvers can arrange a given
number of checkers any way they like behind the line. Checkers can be
jumped and removed in the vertical or horizontal direction, but the final
jump can leave only one checker. The problem is to decide how many
checkers it will take, at a minimum, to "propel" the last checker a given
distance d beyond the line. In deciding this, solvers must also devise an
arrangement that allows the frenzy of jumping to take place.
"Does anybody want to take a crack at this problem?" Honsberger
looks up at the audience, sees there are no takers and smiles ingen-
uously.
"Well, then, let's try a few examples."
He places two
checkers adjacent to each other on the board, jumps
the back checker over the front one, then strides triumphantly to the
blackboard, where he writes
d number of checkers
1 2
134 Theme Three Mathematics Matters
-—
—
J
-
1
Next he places four checkers on the board. He jumps the checkers until a
single checker is left in the second row.
"I'm just saving you people the trouble of figuring it out. Believe me,
this is the best that anyone can do." He writes "2" under "d" and "4"
under "number of checkers." He creates another configuration of eight
checkers and manages to propel one checker to the third row. He scrib-
bles "3" and "S" on the blackboard.
"Anybody want to guess how many checkers it takes to send one
checker four units beyond the line?"
Somebody volunteers the figure 16. No. The answer turns out to be
20 checkers, at a minimum.
The audience now getting somewhat worked up. Could the rela-
is
Hh
1 1
— •
••
1
• #
•
•
H
Honsberger does not stop the lecture to describe Conway's difficult
proof, although he would not dream of discouraging anyone from at-
tempting it. Instead he quickly moves on to a discussion of the pigeon-
hole principle.
This famed principle simply states that if I build 9,999 pigeonholes
for 10,000 pigeons, at least one of the holes would house more than one
bird. The pigeonhole principle has been used to prove many theorems in
combinatorics, the branch of mathematics that deals with finite collec-
tions.
"The next mathematical morsel is one of the strangest applications
of the pigeonhole principle ever made. Imagine that someone has placed
650 points inside a circle of radius 16 units. You have been given an an-
nulus, a flat ring in the shape of a washer. The outside radius of the
washer three units, and the inside radius is two. You are then chal-
is
,,
lenged to place the washer so that it covers at least 10 of the 650 points.
"Impossible," whispers an impetuous undergraduate behind me.
"What if all the points are in a tiny area?"
"Then he can cover all of them with one washer, you idiot\" retorts
another student.
Is it really possible to cover 10 points with the washer? Honsberger
begins the proof by drawing a diagram shown in Figure 13.3. He invites
136 Theme Three Mathematics Matters
us to imagine that a copy of the washer has been centered at each of the
650 points inside the circle.
Some of the points may be near the edge of the circle, in which case
some of the annuli will extend beyond its circumference. But because
each point lies inside the circle and because the washer has radius three,
all the annuli will lie within the larger circle having the same center and
having radius 19, that is, the sum of 16 and three. The area of the washer
is the difference between the area of a circle of radius three and one of
radius two. This comes to five times n.
"The 650 washers blanket the large circle with a total coverage of
650 times 5n, that is 3,250tt. Of course, much of the coverage will be
overlapping, but suppose for the moment that no point of the inner circle
is buried under more than nine washers. In such a case, the total amount
of area covered within the larger circle could not come to more than
3,249ft, nine times the area of the circle. But because 3,249ft is less than
3,25071, some point, x, must be covered by at least 10 washers. The pi-
geonhole principle strikes again."
Honsberger pauses to catch his breath. "You see it now, don't you?"
Then he feigns surprise. "You don't?"
The application of the pigeonhole principle is clear enough, but
some of us are confused. We thought the idea was to cover 10 points by
one washer, not to hide some point x under 10 washers. Suddenly, our
minds are turned inside out like a pair of trousers.
13 Mathematical Morsels 137
"Look at the point x. If you take away the 10 washers that cover it
and replace these by a single washer centered at x, then that washer
alone must cover the centers of the 10 washers that we took away. Each
of these centers is one of the 650 original points!" The morsel is digested
as we hear a faint gulp from somewhere at the back of the lecture room.
The piece de resistance of Honsberger's menu arrives in the form of
a Grecian urn adorning his next transparency (see Figure 13.4). "How
much can a Grecian earn?" quips Honsberger.
When the groans have died away, he explains the problem. An urn is
filled with 75 white beans and 150 black ones. Next to the urn is a large
pile of black beans. The beans are removed from the urn according to
certain rules.
Figure 1 3.4 What is the color of the last of 75 white beans and 150 black
ones in the urn?
138 Theme Three Mathematics Matters
"Here's how it works. Remove two beans from the urn at random. If
at least one of the two beans is black, place it on the pile and drop the
other bean, whether white or black, back into the urn. But if both of the
removed beans are white, discard both of them and take one black bean
,,
from the pile and drop it into the urn.
"Each time a Greek or anyone else dips into the urn to remove two
beans at random, either operation ensures that there will be one fewer
bean in the urn that there was before the move. Slowly and steadily, the
original supply of black and white beans dwindles. At last there are three
beans left in the urn, then two, then one. What color is the last bean?"
The simple and startling answer is white. By figuring out why, a
Greek can earn intangible delights worth more than a hill of beans.
Further Reading
Ross Honsberger, ed. Mathematical Gems: From Elementary Combinatorics,
Number Theory, and Geometry. Dolciani Mathematical Expositions, No. 1.
Mathematical Association of America, 1973.
Ross Honsberger, ed. Mathematical Morsels. Dolciani Mathematical Exposi-
tions, No. 3. Mathematical Association of America, 1979.
Ross Honsberger, ed. Mathematical Plums. Dolciani Mathematical Expositions,
No. 4. Mathematical Association of America, 1979.
—— -
km City
139
140 Theme Three Mathematics Matters
containing each letter of the alphabet. Since then Sallows has invented
many new recreations butnone so engaging as golygons.
In the fall of 1988 Sallows began his search for golygons. It did not
take him long to find an eight-sided golygon. Yet he could find no such
objects that had fewer than eight sides. Nor did he discover a golygon
with nine sides, nor 10, nor 11, . . until at last he stumbled on a 16-
.
sided golygon.
Wondering whether he had missed any, Sallows wrote a computer
program to automate the search. It spewed out no less than 28 different
16-sided golygons (see Figure 14.2) before moving on to higher orders.
The program did not find golygons with from 17 up to 23 sides, but it
generated numerous 24-sided golygons —
2,108 to be exact.
By then Sallows had a hunch that the number of sides in a golygon
must be a multiple of eight. Yet his program, which was already laboring
in the 20's, was unequal to the task of discovering any 32-sided goly-
gons. Frustrated, Sallows appealed to Martin Gardner, the supreme au-
14 Golygon City 141
second side of the golygon will run either two blocks to the west or two
blocks to the east. It follows that all odd sides in the golygon (the first,
third, fifth, etc.) are an odd number of blocks long and run north or
south; all even sides (the second, fourth, sixth, etc.) are an even number
of blocks long and run east or west. Because the last side of the golygon
meets the first at right angles, the last side must run east or west. There-
fore, the last block is an even side of the golygon, and the number of
sides in a golygon must be a multiple of two.
To show that the number of sides must be a multiple of four, we
begin by calculating the total distance we traveled to the north of the
starting point. To do this, we simply add the number of blocks we walked
to the north and subtract the number of blocks we traveled to the south.
(A net negative distance to the north simply means that we are south of
the starting point.)
Because all north and south sides are an odd number of blocks long,
we are essentially adding and subtracting consecutive odd numbers. It
takes only a little tinkering to convince ourselves that the result is always
even when we add or subtract an even number of odd lengths for ex- —
ample, 1+3— 5 + 7 = 6. By the same token, an odd number of odd
lengths always gives an odd sum. Therefore, the distance walked north is
an even number of blocks if and only if we have walked along an even
number of north and south sides.
Now if we walk from the starting point around Golygon City and re-
turn, the distance to the north of the starting point equals zero. Because
zero is an even number, the golygon must have an even number of north
and south sides. The total number of sides is twice the number of north
and south sides, because for every north or south side there must be an
east or west side. Therefore, the number of sides in a golygon is a multi-
ple of four.
How on earth did Gardner show that the number of sides must be a
multiple of eight? Let us accompany the master of his journey.
14 Golygon City 143
f3f%
FOUR TEE
W|E|L|V|E
Z E m E
fio|u|r|e1
F
vl
T IE
TgThTt
floor may be thought of as divided into 52 squares, like the squares of the
special paper on which this enquiry started. Each square is one step on a
side. The L-shaped tiles consist of three squares in a row and an addi-
tional square comprising the foot of the L. Anyone who finds the task im-
possible must, of course, prove it to be so.
I close with some final words from Sallows, the engineer who started
all this. The "words" are ZERO, ONE, TWO and so on, up to FIFTEEN.
They can be arranged in a special golygon all their own in which the let-
ters of these words determine the sides of what can only be called a logo-
lygon (see Figure 14.5).
Further Reading
A. K. Dewdney. The Armchair Universe: An Exploration of Computer Worlds.
W. H. Freeman, 1987.
Lee Sallows, Martin Gardner, Richard Guy, and Donald Knuth. "Serial Isogons
of 90 Degrees." Mathematics Magazine, Vol. 64, No. 5 (Dec. 1991), pp.
315-324.
Scanning
T
a
JL he medical practice called CAT scanning herein lends its name to
new recreationin which readers attempt to reconstruct unknown ob-
jects on the basis of what might be called digital X rays, or D rays. A
Cheshire cat may not be reconstructive from its grin, but some cats can
be reconstructed from their D rays.
In 1979 Allan M. Cormack and Sir Godfrey N. Hounsfield shared
the Nobel prize in medicine for the invention of the CAT scanner. Short
for computed axial tomography, the machine combines a computer and
a series of X-ray "slices" of a patient to reconstruct a cross section of his
or her anatomy, replete with bones, vessels, and other tissues.
fat,
all. Here the X rays do not spray everywhere through my body. Instead
they are confined to a single plane. On the other side of my body they
produce what can only be called a one-dimensional shadow, a strip of
dark and light that betrays the presence of bones and organs only within
that plane and only as seen from that angle.
As shown in Figure 15.1, a medical technician positions a patient in-
side a CAT scanner so that an X-ray source may project its beam through
the patient within a specific plane. On the other side of the patient a row
148
15 Scanning the Cat 149
of detectors records the radiation that went through the patient along
that particular angle. From here, the one-dimensional shadow is relayed
in digital form to a computer. All of this conspires to make but one snap-
shot, so to speak.
The next snapshot is taken from a slightly different angle. The X-ray
detector and source are rotated a bit, and a new beam of X rays slices
through the patient within the same plane. The new array of readings is
also sent to the computer.
When enough snapshots have been taken, the computer begins to
reconstruct the patient's cross section in the plane of all the X rays. How
is thisdone? It hardly takes a Nobel laureate to understand it. In fact, we
shall do precisely the same kind of thing as the computer on a humbler
scale. Rather than asking readers to spend half a million dollars on a CAT
scanner, I shall provide some recreational CAT scanning that requires
nothing more than pencil and graph paper.
The recreational version I call simply the catscanner reconstructs
two-dimensional images composed of small black-and-white squares in
an image grid as in Figure 15.2. For those who see no challenge in this
exercise, let me hasten to add that the image is normally not provided,
only the information from the so-called D rays.
150 Theme Three Mathematics Matters
0 0 7 1 6 3 4 5 2 7 0 0
t t t t t t t t t t t t
0 —
0
8 —
2 —
6 «4
i 1
5
^_
M—
''"'it —
3 M—
7 —
0
0
—
Rows: 7, 1,5, 3, 4, 2, 6
Columns: 0, 1,6, 3, 4, 5, 2, 7
Notice that at least one reading in one of the sequences is equal to the
number of the nonzero readings in the other sequence. In fact, because
there are more than one, readers may take their pick of which one to
work on next. The final outcome will be the same. If, for example, you
pick the 7 in the first sequence, fill in the appropriate squares and carry
out the arithmetic, the next sequence is:
Rows: 0, 1, 5, 3, 4, 2, 6
Columns: 0, 0, 5, 2, 3, 4, 1, 6
Once all the numbers have been reduced to zero, the picture of the spiral
will be staring you in the face.
152 Theme Three Mathematics Matters
The catscanner does not decipher all patterns as easily as it does the
spiral.A catastrophe would occur if two patterns that produced the same
sequences of numbers were placed in the catscanner. By trial and error,
you can probably come up with a few examples.
If you examine catastrophic patterns in a systematic way, however,
you may notice that all such patterns have features that I call chains.
Suppose that two different patterns —
call then A and B —
produce the
same sequences of numbers (see Figure 15.3). Then pattern A must have
the same number of rows and columns as pattern B. If pattern A is su-
perposed on pattern B, there must be at least one black square in A that
overlaps a white square in B. (Otherwise the patterns would not be dif-
ferent.) This square is the first link in the chain.
one square were the only difference between patterns A and
If this
0 4 5 4 6 5 6 4 4 5 3 7 0
4 4 4 4 4 4 4 4 4 4
1. 1 t
10
a
o
.
o ;
J
10 1: 1 1 i
1
11
1
0 4 5 4 6 5 6 4 4 5 3 7 0
t t ,i
I
J 1i .1. .L I ,1 J, L
0
1
6
2 f - =
10 I i
A-
3 i
T
7 1
10 I I
11
I I 1 I
Figure 1 5.3 Patterns A and B and a chain that converts one into another.
154 Theme Three Mathematics Matters
shown in Figure 15.4. To save space, I have omitted those patterns that
are reflections or rotations of others.
Readers who have access to computers can write a simple program
that simulates the catscanner. The program I call grin (Figure 15.5) then
stores the readings in two arrays that I cannot refrain from calling x-
array and y-array. Next the program requests the number of non-zero
entries in the two arrays and stores them in xcount and ycount.
GRIN searches through the arrays of catscanner readings until it finds
the number xcount in the y-array or the number ycount in the x-array.
The program carries out the appropriate arithmetic, draws the corre-
sponding squares on the screen and then sets a special variable called
done to 1. The last step prevents the program from repeating the pre-
vious instructions until it has had a chance to recompute xcount and
ycount. When xcount reaches 0, the non-zero numbers have all been pro-
cessed, done is set to 0 and the computer takes a catnap. A somewhat ab-
breviated version of the algorithm is given above.
Here are some on your catscanner.
categorical patterns to try out
Blending the medical with the recreational for a moment, the following
categorical pattern was recently found in a CAT scan of a cat. What had it
eaten?
15 Scanning the Cat 155
if x-array (I) =
ycount and done = 0
then x-array (I) <— 0
for each y-array (J) > 0
decrement y-array (J)
color square at (I,J)
done <— 1
if = xcount and done
y-array (I) = 0
then y-array (I) <— 0
for each x-array (J) >0
decrement x-array (J)
color square at (J,I)
done <— 1
compute new xcount and ycount
until xcount = 0
Rows: 9, 5, 7, 5, 6
Columns: 5, 3, 5, 0, 5, 2, 5, 0, 1, 5, 1
Rows: 1 1, 5, 4
Columns: 3, 2, 3, 1, 1, 1, 1, 2, 3, 2, 1
square grids would appear to limit the reconstruction game to just two
sets of D rays, one horizontal and the other vertical. But what about diag-
onals? If diagonal D rays are permitted, four sets of D rays are possible,
1, 1
Vertical: 2, 1, 1, 3, 3, 6, 6, 8, 9, 7, 5, 5, 5, 5, 6, 8, 8, 8, 4, 4, 2
Second diagonal: 1 , 2, 2, 2, 2, 4, 5, 4, 5, 5, 4, 5, 6, 6, 9, 9, 7, 5, 5,
4, 2, 3, 3, 3, 2, 1
The horizontal was recorded on the left of the object, the first diago-
nalbeam was recorded on the lower left, the vertical beam was recorded
below and the second diagonal beam was recorded below and to the
right of the object. In each sequence, one of the numbers appears in bold
type. This number represents the ray that passed through the center of
the object.
The reconstruction process may use any insights contained herein,
but there is no substitute for good old-fashioned logical thought. Readers
may even try one of the first reconstruction techniques employed in
medical imaging, the back-projection technique.
You can determine a minimal outline by drawing the region in which
all four D rays are present over the grid. Then back-project: because
The shade of gray can be entered in the squares numerically (but one
must have a steady hand) or, better still, can be reflected by a number of
dots. If the quotient turns out to be .8, for example, place eight dots
in each of the squares of the ray. A quotient of 1.2 would then require
12 dots. The process is time-consuming but perfect for that long flight,
quiet lunch, or slow evening. When a square is dotted in for a second,
third, or even fourth time, room must be found for additional dots. At
the end of the process, the object will be plainly visible, if not precisely
rendered. It can be cleaned up by erasing all those squares that contain
dark. This can bedone by a process of elimination like the technique for
reconstructing categorical patterns. Yet I think that logicians and pro-
grammers alike will find the solution to be the cat's meow.
Further Reading
Gabor T. Herman. Image Reconstruction from Projections: The Fundamentals of
Computerized Tomography. Academic Press, 1980.
in Train
London Bridge is broken down
My fair lady.
ANONYMOUS
1 1 helps to be flexible when you think about rigidity. I learned this les-
158
16 Rigid Thinking 159
amount of force. Such bars come in all conceivable lengths, and if the
ends of two or more of them touch, an instant universal joint is formed.
The joint allows the two bars to swivel and twist unless other connecting
bars constrain their motion.
Imagine, for example, a framework of 12 bars of equal lengths ar-
ranged into a cube. The cubic framework is not rigid. Placed on a table, it
would flop over in an instant. Indeed, if such a framework were rigid,
bridges and towers would not need diagonal girders.
Recently I attempted to brace a cube by adding diagonal bars to
some of its six square faces. How many bars would it take to make the
cube rigid?Four bars, judiciously placed, seemed enough until I found a
way to make the cube flex. Even a cube that had diagonal bars added to
five of its faces turned out not to be rigid (Figure 16.1). The five bars,
along with six of those already present in the cube, form two tetrahe-
drons that are hinged along a common bar. If the two tetrahedrons are
folded against each other, two of the four joints that define the unbraced
square face move toward each other as in Figure 16.1. The other two
joints move outward. No matter how five diagonal bars are added to the
faces of a cube, there will always be a way to flex it. No fewer than six
bars are needed.
Instead of bracing a cube on its faces, what if it were braced by diago-
nal bars that run from one joint right through the center of the cube to the
opposite joint? (With the careless elan of theorists, readers may ignore
the intersections of the diagonals.) A cube braced by four interior diago-
nals has a strange kind of flexibility that theorists call an infinitesimal
flex. In some sense, an infinitesimal flex is a motion of one part of a
framework relative to another. The motion is so small, however, that it
Figure 16.1 The braced cube at the left has an ordinary flex (center),
whereas the one at the right has an infinitesimal flex.
160 Theme Three Mathematics Matters
cubic bracings. Even the diagrams in Figure 16.1 are a bit complicated.
Perhaps it is time to descend from the three-dimensional space that gave
birth to the theory down to the plane, a two-dimensional space inhabited
by a vast panoply of various flat frameworks. Although readers can eas-
ily figure out that a square can be made rigid with a single diagonal, they
will find it rather challenging to figure out how to brace a grid of squares.
For example, how many diagonals must be added to make a four-by-four
16 Rigid Thinking 161
grid of squares immune to flexes? Figure 16.2 shows two ways to brace
such a grid with only seven diagonals. But one of the braced grids is not
Can readers tell which one?
rigid.
The answer can be deduced in the following manner. Make up a dia-
gram composed of two sets of dots. The first set represents the four rows
of the grid, one dot per row. Likewise, the second set corresponds to the
four columns. For each of the seven diagonal bars in the grid, connect the
appropriate dots in the diagram. For example, if there is a diagonal bar in
the square situated in the third row and the fourth column, then draw a
line from the third dot in the first set to the fourth dot in the second set.
Whether the grid is now rigid can be answered by asking the follow-
ing question: Is the dot diagram connected? In other words, is there a
continuous path from any dot in the diagram to any other? If (and only
if) so, the grid is rigid. This elegant theorem —
first proved by Henry
Crapo of the inria near Paris and Ethan D. Bolker of the University of
Massachusetts at Boston —
can help readers quickly determine whether
a grid will flex. The diagram for the grid on the left in Figure 16.2 is con-
nected, but the other is not. As an exercise in rigid thinking, I will leave
readers with the problem of using the Crapo-Bolker theorem to decide
why seven is the minimum number of bars necessary to brace the grid.
As far as I know, there is no corresponding theory to advise readers, or
my father, about how to brace scaffolds or other cubic grids.
Figure 16.2 Dot diagrams reveal whether a grid is rigid (left) or not
(center and right).
162 Theme Three Mathematics Matters
angles. Then one day he felt close. Before him was a nonconvex surface
that flexed. But it was not quite what topologists call a sphere. Two edges
within the surface touched each other, like a deflated basketball in which
one side is pressed against the other. The thing was distinctly annoying.
So near and yet so far.
It was then that the idea of a crinkle came to him. He suddenly
When this tiny flex is performed, the surface bounds the same vol-
ume. These days Connelly ponders whether the constant volume prop-
erty holds true for all flexible, nonconvex surfaces made of triangles. If
he conjectures that they do, he himself may have to be flexible. Some
young upstart may find a counterexample.
As something of an upstart myself, I gave my father some trouble
over the collapse of the scaffolding. But within a few hours of the acci-
dent, the scaffolding was up again. It was identical to the previous struc-
ture, except for one extra spruce pole. My father climbed the scaffold
confidently. I am sure the tiny wobbles I detected were merely infinites-
imal flexes.
Further Reading
Jay Kappraff. Connections: The Geometric Bridge Between Art and Science.
McGraw-Hill, 1991.
— ^
Automated Mat
algebraic expressions.
TJ. here an old vaudeville comedy routine that pokes good fun at
is
the strong-man act familiar from the circus and the state fair. A heavily
muscled man takes the stage with his not so heavily muscled female as-
sistant. The man strains mightily against an enormous weight, and after
tremendous effort he manages to lift it above his head. The spectators
cheer, but the cheers turn to laughter when the assistant casually picks
up the weight in one hand and carries it offstage.
There are two computer programs that leave one with a similar sense
of comic deflation over the mental "muscle" allegedly displayed by a
high score on the traditional I.Q. Both programs perform at or near
test.
genius level on two tasks widely used in the tests, the completion of nu-
merical sequences and the perception of visual analogies. Yet both pro-
grams are simple to understand, and it is startling to realize just how
dull-witted they are.
Although I have no wish to offend readers who suppose themselves
plentifully endowed with mind stuff, I am twitting the I.Q. test with a se-
rious purpose. The stated intent of the test is to measure intelligence,
and few human qualities evoke such pride in their presence or anxiety
over their absence as intelligence does. Nevertheless, the concept of in-
telligencepresupposed by the traditional I.Q. test is seriously mis-
guided.The reasoning behind this assessment is cogently set forth by
Stephen Jay Gould of Harvard University in his book The Mismeasure of
Man (see Further Reading). What it comes to is this: The traditional I.Q.
165
166 Theme Three Mathematics Matters
must be some core ability, or some small set of core abilities, that pro-
vides an index of what one means by general intelligence. Because the
very idea of general intelligence presupposes a strong correlation among
the core abilities, the precise kind of graded task adopted by the I.Q. test
is relatively unimportant. One good as another.
task is as
One of the I.Q. programs presented here is derived from a more
elaborate program written by Marcel Feenstra, a student living in Rot-
terdam. Feenstra's program is called hi q, and it solves two kinds of nu-
merical problems that often appear on standard I.Q. tests: sequence
completion and numerical analogies. Feenstra tested hi q on a number
of sample I.Q. tests that appear in a book by Hans J. Eysenck of the Uni-
versity of London, Know Your Own I.Q. (see Further Reading). The I.Q.
of Hi Q is apparently in the neighborhood of 160. Although the experi-
ment was not exactly a carefully controlled one, it leaves little doubt that
the program would score quite well under real test conditions.
The program I have in mind is called se Q, and it duplicates Hi q's per-
formances on numerical-sequence completion. Readers who write and
run SE Q may consider their own numerical intelligence amplified, as it
were, by proxy. The main idea of the program is straightforward. When
one is given a sequence of numbers and told to find the next number in
the sequence, one does not search for the number directly. Instead one
searches for the rule that led to the numbers already present. There is a
mathematical aside to be made here: For any finite sequence of num-
bers, there are infinitely many rules that give rise to it. The search thus
boils down to finding a simple rule for generating the sequence.
There are two kinds of rules considered by se Q: additive and
just
multiplicative. For example, to find the next number in the sequence 2,
4, 8, 14, ... one might look for an additive rule, and the best way to
,
2
2468 2
4
2
8
> 2
14
\
\
[ii] 1
2345 1
2
1
6
> 1
24
\
\
[
1 20
two numbers in the first row, namely 2 and 4. Their difference is 2, and
so 2 is the first number in the second row. Similarly, the other numbers
in the second row are 8 — 4, or 4, and 14 — 8, or 6; the second row is the
sequence 2, 4, 6. Continuing the same process to a third row of the pyra-
mid gives a sequence with only two numbers, and they are both 2's.
The equality of all the numbers in some row of the pyramid is the
signal, so to speak, to stop building the pyramid upward and to start
building it sideways. For example, suppose the third number in the third
row is also 2. It is then reasonable to suppose the next number in the sec-
ond row is obtained from the preceding number, namely 6, by adding 2:
the sum is 8. the newly derived number in the second sequence can then
be added to the last number given in the first sequence: 14 plus 8 is 22,
and 22 is indeed given a perfect score by the test makers. New numbers
in each sequence percolate down the pyramid once a constant sequence
is derived at the top.
A great many questions on I.Q. tests about numerical sequences
yield to this simple procedure. Readers who have more than a nodding
acquaintance with algebra will recognize the signature of a polynomial in
the exercise. Any polynomial evaluated for consecutive integers yields a
sequence that generates a difference pyramid. Given enough values of
the polynomial, a row of identical numbers will eventually top off the
difference pyramid. The number of rows needed to build the pyramid up
to a constant row, minus 1, is the degree of the polynomial. The se-
quence 2, 4, 8, 14, which gives rise to a constant row of 2's in the third
level of the difference pyramid, is generated by successive values of the
quadratic, or second-degree, polynomial x — x + 2.
2
168 Theme Three Mathematics Matters
substituting only simple differences, c(l) <— b{2) — b{l) and c(2) <—
b(3) - b(2), or simple quotients, c(l) *- b(2)/b(l) and c(2) <- b{3)l
b{2). Apparently it is rare for sequence-completion questions on I.Q.
tests to get more complex than the formulas allow for.
When SE Q develops a pyramid, it tries each generalized substitution
for the set of with each simple substitution for the set of c's. Concep-
fr's
b(i)<-a(i + 1)-[kxa(i)]
c(i) <—b(i + 1 - b(i))
COMPUTE SOLUTION?
I
TRY DIFFERENCE FORMULAS
ON FIRST ROW AND QUOTIENT
FORMULAS ON SECOND ROW
LOOP FOR k
LOOP FOR i
COMPUTE SOLUTION?
i
TRY QUOTIENT FORMULAS
ON FIRST AND SECOND ROWS
LOOP FOR k
LOOP FOR i
b(i)«-[a(i + l)-k]/a(i)
c(i)<-b(i+.1)7b(i)
COMPUTE SOLUTION?
I
TRY QUOTIENT FORMULAS
ON FIRST ROW AND DIFFERENCE
FORMULAS ON SECOND ROW
LOOP FOR k
LOOP FOR i
b(i)<-[a(i + 1)-k]/a(i)
c(i) <—b(i + 1) - b(i)
COMPUTE SOLUTION?
Within the loop, each time new values for c(l) and c(2) are computed
they are tested for equality. If they prove to be equal, their common
value is stored in a variable called c and the current value of k is saved in a
variable called kk. Just after the loop there are instructions that construct
the solution to the original sequence (if one has been found) from the
values of c and kk. In the example I am describing one obtains b(4), the
new member of the second row, by adding c to b(3). The solution, a(5), is
then obtained by multiplying a(4) and b(4) and adding kk to the product.
Two instructions at the end of each loop thus suffice to recover a so-
lution from a successful search within the loop. The instructions appro-
priate for each loop depend on the formulas used in it, and I shall leave it
to those who write SE Q to discover the instructions for themselves. Use
a bit of algebra to isolate the variable of interest. In each case, if one of
the loops in the program finds a solution, there must be an instruction to
printit. The program may then skip the remaining loops and stop, or it
may execute all the loops in an effort to find more than one solution. By
executing all the loops Feenstra has detected several "bad" I.Q. ques-
tions that have more than one solution. If none of the four loops finds
3. Insert the word that completes the first word and starts the second. GRO ( ) PER
In each case the would-be genius must supply the missing number in ac-
cordance with some perceived rules. Feenstra's hi q program handles
such questions by procedures that draw on the same kinds of formulas as
the sequence-completion program does. I encourage readers to try
them. Answers to the problems above, as well as others, appear at the
end of this chapter.
Although hi Q answers only one major kind of I.Q. test question, the
solutions to other kinds of questions can also be mechanized. In fact, a
program that solves visual analogies was written more than 25 years ago
by Thomas G. Evans as part of a Ph.D. dissertation done at the Massa-
chusetts Institute of Technology. Heavy as it sounds, the essential ideas
of Evans' program are easy to understand.
172 Theme Three Mathematics Matters
The visual analogies it solves all have the same form: figure A is to
figure B as figure C is to one four figures listed as potential an-
of, say,
answers; in each case it generates a set of rules that can transform figure
C into the potential answer. The figure obtained from the transforma-
tion rules that most closely resemble the rules for transforming figure A
into figure B is selected as the solution.
Evans' program repeats essentially one operation five times. Two
figures at a time, a source figure and a destination figure, serve as input.
For each pair of figures the program then develops a three-part tabular
description of how the source figure becomes the destination figure.
First the program lists the spatial relations among the parts of the source
figure; then lists the spatial relations among the parts of the destination
it
figure. Both descriptions consider only three spatial relations, above, left
and inside. Finally, the program describes how parts of the source figure
change into parts of the destination figure in one of four basic ways: each
part can be altered in size, rotated, reflected, or deleted.
Suppose figures A, B and C each have three parts, a circle, a square
and a triangle. In figures A and B the program may label the triangles a,
the squares b and the circles c, but it makes no attempt to label the parts
of figure C in the same way. Instead it arbitrarily assigns the labels x, y,
and z to the three parts of figure C. It then develops its three-part tabular
description for the pair of figures A and B and four more descriptions,
one for each pairing of figure C with a potential solution. The last four
tables all employ the labels x, y, and z throughout.
The final operation of Evans' program is to make every possible
substitution of a, b, and c for x, y, and z. Since x, y, and z can be permuted
in only six ways, there are six substitutions to be tried. One of the substi-
tutions may convert the tabular description of the pair of figures A and B
into the corresponding tabular description of figure C paired with one of
the potential answers. The figure in this pair is the solution. Even if no
perfect matches are found, however, the program can score the relative
success of an analogy and so pick the substitution that yields the best
match.
Patrick Henry Winston describes the visual-analogies program in his
book Artificial Intelligence (see Further Reading.) Winston states that the
program "works well," and he attributes its success to the use of an ef-
fective framework for representing knowledge about the geometric fig-
a: UNCHANGED
IS TO
b: REDUCED
a ABOVE b b ABOVE c
c: ENLARGED
a ABOVE c b ABOVE a
c INSIDE b a INSIDE c
x: UNCHANGED
y: UNCHANGED
x LEFT y
z: UNCHANGED
z LEFT y
z INSIDE x
x: REDUCED
y: ENLARGED
y LEFT x
z: UNCHANGED
z LEFT x
z INSIDE y
IS TO
x: REDUCED
y: UNCHANGED
z: ENLARGED
x ABOVE y
z ABOVE y
x INSIDE z
x: REDUCED
y: ENLARGED
LEFT z z: UNCHANGED
y LEFT z
x INSIDE y
173
174 Theme Three Mathematics Matters
same things. For all one knows there may be no relation whatever be-
tween the way Feenstra's or Evans' I.Q.-test programs perform and the
way people solve the same kinds of problems. Presumably human intel-
ligence deploys more general strategies in attacking particular problems.
This point brings me full circle to the reconsideration of human in-
telligence: what it is and how it is measured. As I have noted, Stephen
Jay Gould has characterized I.Q. as a mismeasure of man. His criticisms
carefully document two major fallacies that underlie the concept: the
uncritical reification of an abstraction and the ranking of the reified ab-
straction along a single scale. Language itself accounts in large part for
our tendency to make things of what are at best nebulous abstractions.
Moreover, once we have persuaded ourselves that we are dealing with a
thing, our reflex is to measure it.
In demanding a single numerical measure we succumb to the second
fallacy, namely ranking. We want to reduce complex phenomena to a
single scale. Such practices have led to excellent physics, but they have
also led to some poor social science. I.Q. testing is a case in point; it is to
the 20th century what craniometry was to the 19th. In both instances
entire racial groups found themselves mismeasured not only because
the measure was almost meaningless to begin with but also because
there were biases introduced (either consciously or unconsciously) in
the process of measuring.
1 7 Automated Math 175
Further Reading
Hans J.Eysenck. Know Your Own LQ. Penquin Books, 1982.
Stephen J. Gould. The Mismeasure of Man. W. W. Norton, 1983.
Patrick Henry Winston. Artificial Intelligence, 2nd ed. Addison- Wesley, 1984.
THEME FOUR
LOMPUTERS LREATE
In the chapters that follow, computers com-
pose canons and play chaotic improvisations,
cultivate the art of disjointed conversation,
cartoonize human faces, and paint scenes from
other planets. The degree to which humans
intervene in these creations varies from exam-
ple to example. The one, creating those
last
fascinating arabesques of centuries past, is left
tohumans —
so far.
The composition of a strict, first-order
canon by the rule of renaissance music in the
first chapter, for example, allowsno human
intervention whatever. The computer searches
systematically through all possible melodic
1 1was in 1965 that I first heard the sound of computing. An IBM 7090
at the University of Michigan Computing Center had been fitted with a
simple electromagnetic pickup connected to a loudspeaker. As a com-
puter program ran, a specific register in the machine changed its con-
tents many thousands of times per second. The resulting pattern of min-
iature clicks was heard as an astonishing rush of alien sound that
alternated among buzzing, screaming, burping, rumbling, and whining.
At times a grinding noise would change from bass to treble. This may
have been the sound made by a double loop in the program; perhaps the
inner loop executed ever faster, creating a tone of increasing pitch. It all
179
180 Theme Four Computers Create
x <- (a x •
+ b) mod m
Here, when one specifies the parameters a, b and m
in advance, an initial
value of the variable x is converted into a succession of values by the
continued iteration of the assignment. The expression "mod m" is an ab-
breviation for "modulowhich means that the number computed in-
ra,"
side the brackets should be treated like the hours of an ra-hour clock. For
instance, 10 modulo 8 equals 2. Thus if m is 8 and if a, b, and the initial
value of x are all integers, one obtains a sequence of numbers ranging be-
tween 0 and 7.
The resulting sequence of numbers is readily converted into a suc-
cession of notes by a simple table:
0 12 3 4 5 6 7
do re mi fa sol la ti do
0 12
3 4 5 6 7
262 294 330 349 392 440 494 523
18 The Computer Composer 181
Note C C# D D* E F F# G G# A A# B C
Frequency 261.6 277.2 293.7 311.1 329.6 349.2 370.0 392.0 415.3 440.0 466.2 493.9 523.3
Frequencies of notes above or below this octave are obtained by multiplying or dividing by 1 .05946 and
rounding off as appropriate. The number is ife the twelfth root of two.
,
input a x to,
for / = 1 to 100
x «- (a x + to) mod 8
•
the frequency of the note the program will play. I wonder what other
possibilities readers might invent for themselves. In the meantime here
an interesting question about boredom. For given values of a, b, and m,
is
how many notes will be played before the melody begins to repeat itself?
Harmony is now withinthe vocal competence of many home com-
puters. Those equipped with two or more speakers will be able to play
the entire repertoire generated by a program I call canon. Indeed, a few
enthusiasts will undoubtedly carry the project much further. Some
readers may already have acquired a MIDI. The acronym stands for Mu-
sical Instrument Digital Interface, an electronic black box that converts
signals generated by one's computer into commands for electronic in-
struments such as musical keyboards and individual synthesizer chan-
nels. (Readers interested in learning more about MIDI may write the In-
ternational MIDI Association, 12439 Magnolia Boulevard, Suite 104,
North Hollywood, 91607.)
Calif.
canon generates two-part harmony involving two almost identical
melodic lines. Rounds such as "Row, Row, Row Your Boat" and "Frere
Jacques" exemplify the type if not the species, canon generates a canon
in the academic tradition known as first-species imitation, a first stage in
the serious study of counterpoint.
Such a harmony has two melodic lines that satisfy four criteria. First,
all notes have the same duration. Second, one line begins after the other.
Third, both lines are identical except that one line is transposed upward
by some standard musical interval (unison, perfect fourth, perfect fifth,
or octave). Fourth, the two lines together must satisfy, note for note,
certain rules of first-species imitation. All the rules are found in standard
texts. Such rules generally include the allowed note-for-note harmonic
intervals (Figure 18.2) and establish the shape of participating melodic
lines. In the interest of simplicity the latter has been omitted.
An example of a harmony in first-species imitation is shown in Fig-
ure 18.3. The example was written by a human being, not by a machine.
A glance makes it plain that after a certain point the composer tires of the
strenuous demands imposed by all four criteria. Rule three is usually the
first to go; enough if the second line imitates the first in spirit only.
it is
b
UPPER NOTE NUMBER
OF HALF-
c C# D D# E F F# G G # A A# B C NAME STEPS
X X X X X X 1 0
c# X X X X X X 1+/2° 1
D X X X X X 2 2
D# X X X X 3- 3
E X X X X 3 4
F X X X X P4 5
F# X X X X 4+/5° 6
LOWER NOTE G X X X P5 7
G# X X 6- 8
A X X 6 9
A# X X 7~ 10
B X 7 11
C 8 12
Notes sounded together are consonant, according to table a, if the combinations do not fall on
an X. The names and sizes (in half-steps) of the resulting harmonic intervals are found in table b.
The intervals of unison (1), minor and major third (3~ and 3), perfect fourth (P4), perfect fifth
_
(P5), minor and major sixth (6 and 6) and octave (8) are considered consonant in first-species
imitation. The corresponding numbers of semitone (half) steps are 0, 3, 4, 5, 7, 8, 9, and 12.
1 —
o*ti—o
° "
1_0 O & 1
canon, the value 7. This is the tonic note, and it not change. The re-
will
maining entries in mel all start at the value 0. A while loop tests a Boo-
lean, or logic, variable called found, which is initially set false. Found is
made true if discovered by the instruc-
a valid canonic melodic line is
tions in the body of the loop. First, the array mel is incremented. This can
be done by scanning the array from right to left. In the process of scan-
ning, the counting procedure looks for an array entry that is less than 13.
On finding such an entry, it adds 1 to it and changes all the entries to the
right (if there are any) to 0. This is precisely what happens in ordinary
counting, where 9 replaces 13. For example, 3572 + 1 = 3573,
3579 + 1 = 3580 and 3599 + 1 = 3600.
The next job of the loop is to compare each note mel(j) with the note
mel(j + del) + int. In other words, the program adds int to the note that
is del notes after mel(j) and looks up the difference of the two note
ences to look up in the table.) Once such a melodic line is found and
printed out, the program asks the composer, "Do you want to con-
tinue?" If the answer program branches back to the found <—
is yes, the
false instruction and the count picks up where it left off.
One can, of course, play the melodic lines discovered by canon
through the tiny loudspeaker of one's home computer. Readers of a mu-
sical bent, however, will develop the knack of humming the line or of
transcribing it, along with its canonic companion, onto sheet music. The
canon can then be tested at another keyboard in all its harmonic glory.
Rhythm is a more sophisticated musical form that some readers may
realize; traditional Western music has never been very elaborate rhyth-
mically. Popular musical culture, on the other hand, has embraced an ex-
traordinary variety of rhythmical forms (Figure 18.4). Most of them
originate either directly or indirectly from traditional African or Asian
music. This includes most rock music, jazz, Caribbean, and Latin-Amer-
ican music. Westerners are also increasingly aware of the complex con-
tribution of the tablas (a pair of drums played by the fingers) to Indian
musical forms such as the raga.
The program I call beat enables one to spedify simple rhythms as
sequences of O's and I's (Figure 18.5). These are translated into sounds
by the simple expedient of running through the sequence repeatedly.
Each time through, the presence of a 1 triggers a brief tone pulse. A 0
triggers nothing.
Actually beat is simple enough to describe without further ado.
Structurally it is rather similar to solfeggio (the program that plays lin-
for = 1 to numj
k<- 1
then sound
The variables called num and dur refer respectively to the size of the
input array and the duration between sounds. The outer loop specifies
that the basic rhythmic interval determined by pulse will be played 25
X
CYMBAL
ROCK: SNARE DRUM
BASS DRUM
1010101010101010
00001001 01 001001
CYMBAL
SNARE DRUM
1011 0000101 0100 1 BASS DRUM
HI HAT
REGGAE: SNARE DRUM
BASS DRUM
1 0 HI HAT
0 1 SNARE DRUM
0 0 BASS DRUM
CYMBAL
JAZZ: SNARE DRUM
BASS DRUM
10 0 0 0 10 CYMBAL
110
1 1
110
1 1
0 0 0 1 0 SNARE DRUM
10 0 0 1 1 0 0 0 0 1 BASS DRUM
X— SNARE DRUM
SAMBA: SNARE DRUM RIM
BASS DRUM
HI HAT
1 o 1 1 0 1 1 1 1 1 o 1 SNARE DRUM
0 1 0 0 1 0 0 0 0 0 1 0 SNARE DRUM RIM
0 0 0 0 1 0 0 0 0 1 BASS DRUM
0 1 0 1 0 0 1 1 0 HI HAT
times. This number can easily be altered by readers who stumble onto
rhythms they would like to hear for a longer period of time. The next
inner loop controls the array index; the algorithm will consider each
entry in turn in order to decide whether or not to play a tone. How long
to wait between sonic events? That much is determined by a special
waiting loop that simply counts up to the specified duration, dur. Then, if
pulse(j) is 1, the program beat will play a tone, a buzz, or whatever may
be available. If dur is small, the rhythm will be fast. If dur is large, the
rhythm will be slow.
188 Theme Four Computers Create
computer program with two rules. In one role the program computes
what it computes. In the other role the program is fitted with a tone or
two next to its inner loops, outer loops, and conditional (if) statements.
The program has a song to sing for each problem it is given. Those who
listen regularly to their favorite program (be it recreational or commer-
cial) will develop an ear for its performance. I have no doubt that some
F
JL ew readers have heard of Victor Chaosky His music has an other-
.
worldly quality that is hard to describe. But critics have yet to call it un-
musical. His April One Suite, though played by a single instrument that
sounds at times suspiciously like the tone generator on a home com-
puter, leaves no doubt of the composer's brilliant, chaotic talent.
Some people have attempted to imitate the music of Chaosky, all
with amazing success. One of these is Arthur Davidson, a low tempera-
ture physicist at IBM's Yorktown Research facility in Yorktown
Heights, NY. He uses the famed logistic equation, the simplest chaotic
system known, to produce the notes from his personal computer, an
IBM PC running turbo Pascal. He notes that more than one visitor to his
office has remarked (in almost the same words on each occasion), "Say!
Isn't that Philip Glass?"
They may have heard of the composer Glass, but not, evidently, of
From time to time, Davidson runs the program he calls
Victor Chaosky.
CHAOS IN A MAJOR (or CHAOS-A for short), listening intently. This
is the sound of chaos reduced to a manageable scale. Interesting musical
patterns seem to repeat themselves with slight variations when, sud-
denly and unaccountably, they change gears as if Chaosky had aban-
doned his theme in mid-passage, inspired by a new musical idea. But the
patterns are not merely musical. Can Davidson hear in them a hint of or-
Among his missions at IBM
ganization to be exploited or learned from?
Research, he studies non-linear dynamics, the behavior of physical or
mathematical systems that do not have a linear response to their state
variables, but a non-linear (e.g. quadratic) one.
189
190 Theme Four Computers Create
As a child, Davidson had studied the violin and still likes to "fool
around" on the piano. "Anyone who has heard me will tell you that I am
not a musician/ he says. A few years back, Davidson was heavily in-
'
volved with the logistic equation, staring at the famed map by day and,
as usual, playing around with musical scales in the evening. "Eventually,
I two things together." The rest is history of a sort
got the idea to put the
that some future student of simultaneous invention may want to ex-
plore: At the same time, others were trying exactly the same idea.
There are a few versions of the logistic equation, all equivalent. The
one favored by Davidson has the fewest symbols in it:
x <— x(a — x)
0 12 3
sent successive values in the logistic formula. The horizontal lines repre-
sent iterations of the equation. In the parabola labelled 3.1 two points
are marked. These comprise a two-point attractor representing the equi-
librium behavior of the system when a = 3.1. Successive parabolas
yield a geometric interpretation of what is happening in the logistic sys-
tem at certain values of the a-parameter. The largest parabola is a sample
of chaotic behavior. Only 100 points are shown but if the iteration had
continued, the parabola would soon be black with them! Chaos.
This situation corresponds to a slice across the bifurcation diagram
in Figure 19.1 at the level a = 3.88. On the way to chaos, readers who
simply write a program that produces and plots successive values of the
formula as points on a horizontal line will notice the well-known period-
doubling phenomenon.
If your program is written to accept different values for a from the
keyboard, then to run the equation for, say, 100 iterations, it will pro-
duce values that converge on a one-point attractor for any a up to ap-
proximately 3. After that a two-point attractor shows up. For example,
at 3.1 successive numbers bounce back and forth between two limiting
values, converging to them. At a = 3.5, there is a four-point attractor. At
19 Chaos in A Major 193
Davidson did, that when a is increased above 3.57, the chaotic points
spread out to cover more and more of the parabola. Davidson's descrip-
tion of what he saw is colorful enough to repeat.
"Now in playing around with these things on a PC, I noticed that
iterating the map in the chaotic regime would not exactly repeat a value,
but it would frequently almost repeat a value. In fact it would almost re-
peat whole sequences of values." (see Figure 19.3.) "Aha! This is where
I heard the bell ring. It was exactly how I had come to regard music! To
maintain your interest, music must represent some sort of pattern that
you recognize. . . .
divided the range of x-values up into subranges, one for each note in the
diatonic (major) scale from A
to A. Then he set to work.
A bare bones chaos composition program can be written on the basis
of a seven-line algorithm. Inside a loop which may be one of several
types, including even a simple for-loop, iterate the logistic equation
once, translate the value produced by the equation into a frequency,
then play the tone that corresponds to the frequency. Figure 19.4 shows
the essential steps based on a repeat loop that can only be terminated
when the user presses a key.
Within the loop, when the next value of x is calculated, it is con-
verted into an integer between 0 and 12 called step, then into a fre-
quency called tone.
The notation in which this last calculation is expressed leans slightly
in the direction of turbo Pascal. Essentially, a base frequency of 220
Herz (middle-A on the musical scale) is multiplied by 2 to the power of
step 112. The function called exp denotes taking a power of the transcen-
dental number e, then correcting with a factor of ln(2), the natural log of
2. So much amounts to a power of 2 and what follows is just the power
taken, namely, step/12. If step = 0, the base note ,
A, remains the same.
If step = 1, 220 multiplied by 2 to the power of V12. This is
the result is
one-twelfth of the way up the semitone scale from A to the A one octave
higher. Thus, when step = 12, the frequency of 220 is multiplied by 2 to
yield a frequency of 440, an octave above 220.
input x and a
repeat
x <— x*(a — x)
tone «- int(220*exp(ln(2)*step/12)
play tone
The twelve-tone semitone scale will sound just a bit too "modern"
for some readers. To get a more pleasing diatonic scale, the basic calcu-
lations must be changed. First, the value of x will have to be transformed
into an integer between 0 and 8 (0 and 7 will serve about as well). The
resulting number, step, will then be converted to a tone by adding an in-
teger that causes the appropriate semitones to be skipped. Under this ar-
rangement, the needed tones are: 0 (A), 2 (B), 4 (C#), 5 (D), 7 (E), 9 (F#),
11 (G#), 12 (A). The problem of writing the one or two lines of code that
will convert step into tone can, I think, safely be left to most readers.
How do you get sound out of your system? Davidson uses the turbo
Pascal command called "Sound." Specifically, Sound (220) or more gen-
erally, Sound (freq) will produce a tone of middle A in the first case and a
tone of whatever frequency happens to be specified by the variable freq
in the second case. In order to hold the tone for a time, Davidson inserts
a delay loop (" delay (n)" in turbo Pascal, where n is in milliseconds). The
sound must, after this delay, be turned off. The next step in CHAOS A
will therefore be the turbo Pascal command "Nosound." Anyone pro-
gramming in BASIC can use a somewhat simpler command: SOUND
freq, dur. By this I mean that SOUND is a function that has two argu-
ments. The first argument, whatever you call it, is either a number or a
variable that specifies the frequency in Herz of the desired note. The
second argument specifies the duration in "clock ticks," each BASIC
clock tick lasting approximately Vis of a second.
There are a dozen useful features that can be added to the basic
CHAOS A program to make it a genuine tool for the intellect, not to
mention a flexible music maker. Here is what Davidson's version of the
program does:
Davidson is the first to admit that the program can be developed well
beyond this point. In fact, there is no need to stick to the logistic equa-
tion. There is a wonderful book by Francis Moon (see Further Reading)
that lays out a number of other simple equations, including one based on
the circle. I await the results of reader programs with bated breath, as
does Davidson.
196 Theme Four Computers Create
Figure 19.5
9 Chaos in A Major 197
198 Theme Four Computers Create
Further Reading
Francis C. Moon. Chaotic Vibrations. John Wiley & Sons, 1987.
20
When meet someone on a
I professional basis, I want
them to shave their arms.
people off the street, were policed by referees who were experts in com-
puting and artificial intelligence.
199
200 Theme Four Computers Create
pad on which each entity would ultimately be ranked from most human
to most computerlike. Behind the scenes museum officials wrung their
hands and muttered. There had been an hour delay setting up some of
the lines to long distance participants. What if no program fooled any of
the judges?
The audience moved from screen to screen, laughing here and
groaning there. Some people had no doubt that the screen for terminal
five (labeled whimsical conversation) belonged to a program:
TERM: Hello, judge, what is your mood today? happy? sad? ready for
—
some fun? Hello how's the weather up there today? Let's talk about
psychology!
JUDGE:It has been a long day! Now think I'm ready for some fun. The
I
weather isn't very pleasant today. Do you have any jokes that could lift
the clouds?
20 Mark V. Shaney 201
TERM: Everybody talks about the weather but nobody seems to do much
about it. Why do you need to tell me you think you're ready for some
fun? Groannnnnn. . . .
TERM: Now you have really outdone yourself in asking stupid things!
Woof . . . woof . . . woof. . . . Why do you think did ask you?
I
If the entity behind screen five was a computer, who could doubt
that the entity behind screen four (the plays of Shakespeare) was a
human?
TERM: Ah, of course, that play would better be called Brutus, but the title
of Julius Caesar was and is more saleable.
Here it seemed obvious that the entity behind screen four was meet-
ing the questions andcomments of the judge head on, so to speak. As this
and other conversations with judges revealed, the entity was quite
knowledgeable about Shakespeare in a way that expert systems, even
equipped with all the same facts, could hardly express in fluent English.
By the same token, however, audience members who were less conver-
sant with computers and AI were more willing to believe that its exten-
sive knowledge betokened something of the superhuman, something of
the computer, in other words.
Museum officials needn't have gnawed their nails about the out-
come. Five of the judges ranked the whimsical conversant on the human
side of a line that was supposed to separate the humans from the com-
was revealed at the end of the Loebner Prize competition as
puters. All
cameras whirred and flashbulbs crackled. Headlines could now read:
202 Theme Four Computers Create
repeat
r «- random
determine pair follower
output follower
<— second
first
In this way, each follower word will be selected, in the long run, with a
frequency that reflects its frequency in the original text. And in this way,
the text so generated bears an eerie resemblance to the original:
"When I meet someone on a professional basis, I want them to shave
their arms. Whileconference a few weeks back, I spent an interest-
at a
I wouldn't dare take them seriously! This
ing evening with a grain of salt.
brings me back to the brash people who dare others to do so or not. I love
a good flame argument, probably more than anyone . . .
"I am going to introduce a new topic: does anyone have any sugges-
tions? Anybody else have any comments experience on or about mixed
race couples, married or otherwise, discrimination forwards or reverse,
204 Theme Four Computers Create
one complainer put it: "Will someone please pull the plug on Mark V.
Shaney?' Given Mark's relative success on Net. Singles, might there be
'
some hope for a near relative in next year's Loebner Prize Competition?
It all depends on what I mean by a "near relative."
one or more followers that are also words. But what is true of pairs of
words is also true of triples. Every triple of consecutive words that occur
in the text is followed by a fourth word. This suggests that one might con-
struct a four-dimensional table and generate, in consequence, text that is
even closer to the language of the received text.
There is no reason, of course, why a second-order Mark V. Shaney
could not be constructed to operate on triples of words rather than single
ones. Let us call her Shirley Shaney. I expect that Shirley will sound
somehow more sensible than her disruptive brother. Readers with a
modicum of programming skill have enough advice to build a Shirely
Shaney. Warning: Once Shirley is written and debugged, she will require
rather large volumes of text to get started. An entertaining form of input
would involve conversations between Shirley and her maker. Cycles of
table building would alternate with sentence generating while Shirley
slowly "learned" her creator's conversational pattern. At such a pass her
creator could then watch for the announcement of the next Loebner
Prize Competition.
Fi Sri
I never forget a face, but in your case I'll be glad to
make an exception.
T JL he face is unmistakable. There are the low, floppy ears, the prom-
inent cheekbones, the high pompadour. Ronald Reagan's face is familiar
around the world, but somehow it is even easier to spot his likeness in a
caricature than it is in a photograph (Figure 21.1). Surely the art of cari-
cature calls for deep insight into human nature. If this be the stuff of
computation, surely the computer is a trivial adjunct —little more than a
sketch pad —that merely stores the highly subtle renderings of the cari-
caturist in a visual form.
Or is it? The caricatures on these pages were all generated by a pro-
gram devised by Susan E. Brennan, a staff scientist at the Hewlett-Pack-
ard Laboratories in Palo Alto, Calif. To run the program a mouse, a light
pen, or some other analogue of a pencil might be convenient, but they
are certainly not essential. The results depend hardly at all on a steady
hand or a practiced eye. Instead, once a photographic likeness of the face
is entered into the computer, the program takes over and draws the cari-
205
206 Theme Four Computers Create
in the process because when they are recognized, they are recognized
almost instantly. Could it be that instead of remembering a friend's face,
we remember a caricature of it? To address these issues Brennan in-
vented her simple technique for generating caricatures, and she de-
scribed it in her master's thesis at the Massachusetts Institute of Tech-
nology. She continues that interest in her spare time; in her working
hours she now experiments with new forms of communication between
21 Face Space 207
brow of the average face. Three norms are constructed in this way: there
is an average male face, an average female face, and an average, overall
208
21 Face Space 209
ing what she calls face space. The entered coordinates for the points de-
fining a photograph can be strung together in a predetermined order.
The result is a list of numbers that can be treated as coordinates of a sin-
gle point in a high-dimensional space. For example, both the average
faces and the photographic face are represented by 186 points, each of
which has two coordinates. The resulting list of 372 numbers for each
face is a point in a 372-dimensional space. In principle every face can be
assigned to a point in face space, and any two faces in face space can be
connected by a straight line.
There is no need to be mystified over the concept of a higher-dimen-
sional space. Face space is merely a handy abstraction for describing dif-
ferences and similarities among faces. The familiar concepts of the
straight line and the distance between two points have straightforward
analogues in any higher-dimensional space. All the points along a
straight line in face space represent proportional changes in each coordi-
nate value. The distance between two points in face space is a measure
of their similarity: similar faces are close neighbors in face space, and
dissimilar faces are literally farther apart.
In face space one can imagine the norm as being near the center of a
cloud of points representing realistic images of real faces. A line joins
210 Theme Four Computers Create
each real face to the norm. The points along the line correspond to a suc-
cession of intermediate faces that look increasingly like the real face.
Beyond that face are the caricatures, but there is a natural limit to recog-
nizable exaggeration: the caricatures eventually lose their human quali-
ties and degenerate into a chaotic state Brennan calls facelessness.
The idea that every face is a point in face space suggests another fas-
cinating transformation. Since any two faces in face space can be joined
by one can ask the program to generate a transitional se-
a straight line,
quence from one face to another. Brennan finds such sequences particu-
larly intriguing when the two endpoint faces are male and female: the
program effortlessly transforms Elizabeth Taylor into, say, the late John
F. Kennedy (Figure 21.4).
The reader can duplicate some of Brennan's feats of caricature by
writing a smaller version of her program; I facebender. It re-
call it
quires the user to supply at least two faces: a norm and the target face to
be caricatured. I have referred above to the norm, whose coordinates
have been generously provided by Brennan (Figure 21.5). The user must
then convert the target face into the same form. In the absence of so-
phisticated digitizing equipment the reader can, with relatively little
pain, convert a photograph of a loved one (possibly oneself) into a list of
coordinates. Brennan warns, however, that the face in the photograph
must have a bland, neutral expression; even a slight smile will grow to a
monstrous grimace. The face must also be fully frontal; if the head is
turned, facebender will turn it even more.
To determine the scale for the axes, assume the coordinates of the
left and right pupils are the same as the norms: the left should be at (135,
145) and the right at (190, 145). (Remember that horizontal coordinates
increase from left to right and vertical coordinates increase downward.)
Once the distance scale is established the user must find the rest of the
coordinates by careful measurement. In Brennan's digitizing scheme the
points on the face are organized into 39 facial features; each feature is a
arrays have 186 rows and two columns: one face point per row and one
coordinate per column. Points are arranged in the serial order given in
the list The advantage of this ordering is that all lines in the
for norm.
final picture can then be drawn between successive points in the array;
of course, lines are not drawn between successive array points when one
feature is complete and another is about to be drawn.
The first feature the program draws is the pupil of the left eye; the
second feature is the right pupil. Each pupil can be rendered as either a
dot or a small circle; somehow the circles look friendlier. For the re-
maining features, however, lines are drawn to join consecutive points in
the array. A special array called features is needed to skip the line be-
tween the last point in one facial feature and the first point in the next.
The array gives the number of points in each feature, and a double loop
supervises the skips (Figure 21.6).
Because the two features have already been drawn, the display
first
routine begins with the third feature, namely the left iris. The first point
in the left iris is the third point of the array disp, which is indexed by the
variable i; hence the value of i is initially set equal to 3. The array features
is indexed by another variable, and it ranges from 1 to 37 because there
are 37 features left to draw. Within the ; loop another variable called
count keeps track of the number of lines drawn for each feature; it in-
creases by 1 with each passage through the ; loop. The index i is also in-
creased with each passage through the loop; it identifies the point in the
array disp thatis currently participating in the frantic expercise of con-
nect-the-dots.
Inside the loop is a second loop called a while loop; it compares the
number of points joined so far in feature ; with the total number of points
in that feature. The program leaves the while loop when the two num-
bers are equal; the feature is complete. If there are still points to connect
CM CM CM CM NO IS ON CO
00
rH
00
rH
00
rH
00 co CO
rH rH rH
On
rH
©
CM
rH rH rH co" cm" rH is" oo"
SO no NO NO m rH IS ts
rH rH rH rH' rH CM
V —
rH
^
rH
—
f s ^ s ^^-^ ^ s
rH rH ON ON ON ON rH CM IS CM
rn X 1
t> S> IN
_h
rn n CO CO
V i
n ON
rn
©
CN
in CD no" is" co" o" o" oo" oo"
©"
co on
rH rH
m NO
rH rH srH rH'
m m ©
rH CM
SO
rH
IS
rH
—
v —
s — >w >>w' s —
^ N ^ ^
CM CM CM CM 00 00 NO IS ON CO
_h
rH ; j
t> IS 00 00 CM CM CO co ON
rn _J n n oH
rn rH n
rH ri n i
©
CN
©" NO oo" oo" On" On" CM
©" cm" co"
On
tH
m SO CO ON rH NO
rH rH rH rH rH rH rH CM rH
m SO
rH
ON Q\ IS SO CO CM CO O mSO 00 00 IS ON CM NO CM
rH pH rH
-or <Oh ©
rH , —
WO
— in sO l® IS is CM CM CO co ON
rn _in — ~
:
1
i
1— — —
< rr rn
.
!
i
©
CN
rn oT Is" rH ©o" no" so" so" no" Is" m" NO" oo"
©" no" so"
co 00 o ON
rH rH rH CM rH 00 rH CM rH rH
e o m so
rH rH
IS CM 00 co in
rH rH rH rH rH CM rH
© m
rH
rH © © ©
is to CO CO co CM CM CM CM ON CO
^> HiO CO CO in in an is CO CO CO co On o
rH
oo"
rH rH rH rH rH rH
00 ©" co" rH CN rH in
© rH rH rH rH rH rH rH rH rH rH
is" so" so" Is" no" CO" co" is" On"
CN
oo"
(N GO m ON © m © ©o m CO I** rH IS CM 00
rH rH ?H rH
rl rH^ rH d rj^ rH .rH rH^ rH, rH rH^ r-^
CM
rH^
rH rH S* SS S. co fO rH On ON is NO © O © 00 SO CO CO
©
CM
LO in © ©
NO NO CO CO
rH rH rH rH rH rH rH rH rH rH rH rH rH rH rH rH
© CO
rH
CO ©
rH CM is" CM
©
00
ON © rH
CO On CO ON rH IS CM
00 NO IS 00 NO NO
is cm is no
CO CM
is rH IS m ©
m CM
rH
rH
co CO —
s>
ooooooooooooooooooooo
PhPuPhPhPhPliPliPliPhPhPliPhPhPuiD-iPhPhPmPLiPhPli
o
Ph
rHrHmincOCOCOCOCOCOCOCOsOsOsOsOsOsO'^-Tt-lS IS
o
a 3 pci
PQ
O pq Ph
00!
pq o&
PQ
pq
w H
[Tj
O
co
CO p^
PQ pq
H DC OZ pq >^
>< pq
X pq
Ph
W O PJ
a Ph
Ph
hJ S3 H E-h
2 P^
D
H H
p^ pq
P0 PH o w Ph Ph Ph Ph
d E O O
pq
Q pq
O hJ oD Ph
o
Ph D 5 PJ
Ph Ph
9 oo
Ph S PH
H Oooo CO
o o oo o
H o o H DC H H E-h
H H H Ph Ph Ph O Ph H H Ph E-h
OOOOO w O O Oo O
PQ H E-h 2 H PQ PQ PQ
212
' ' H
00
-Itn
CN
o
(N
o
CN
"^t
O 00
rH
ro
CN
^ so
CN CN 00"
§
On ON rH ^ CN-
CN
CN
NO
rH
w
rH
CO
rH rH
PCS
00 00 rH <N
CN
o
(N
rH
CN
ON IN
ON, rH (N ON
of
CN
00
v£)
^ ~ rH
O rH d>
—
(N
o
N. co '
ro _o
rH £ cn W^
rH
ON CN
m
in <n
ON
CO
o
^—1
rH
^ O
ON VO
ON ^
(N <N CN "2 CO
CO CO <N
SO NO ro
T~H rH1
O
o m CN
CN
o o
rH CO
ON
in rH
04 OrH ON
ON ON ON 00
O ON
rH
CN CN ON rH r^ rH rH CN
ON ©~ CN
so"
m in
m o ^ rO
in rs
rH ^rH
vo" tn
CO ^0 On
co
IN
00 w
rH rH^ CN
o
00 ^ 0> CN
00
m Tt CN CO «fr CO CO CO 00 SO
©
CN
o
CN
NO
rH
ON
ro
\£i 00 00 00 00 On ON CO rH
rH CN CN
« « * «
on oo~
-Iro
rH
o w
t^s
rH ON
CO 00
m O
On "3-
rH
m" cn" CN
NO NO NO
rH ^
CO
rH
ro
CN (N _ W
rH
ON
^ £\
co
00
CN
HHM
g (N 5" <N t+ LO NO 00 00 NO NO CN 00
CD
CNrs JO
00
m rH OS
53 ^ IN IN IN
00 ^"1 ^"1
00 00 CO rH
rH^ rH CN CN
00 rH
ro >— $5i ON CN
ON CN
fN
o w S-iro"
ON
^
r-\ in
00" in 00"
5J- IN
rH rH rH CN
rH O oT m"
m
rH
so no
cm" co"
m
00 CO CO CO CO CO CO CO CO cocococococococo
H H hh hh H H H E-hHHHHE-hHH
2 2 2222 2 2 2 22222222
O
PL,
O
Oh
OOOO
pL, Ph Ph Ph
00
Ph Ph
0
Ph
00000000
PhPhPhPhPhPhPhPh
IN IN CO CO IN rH CO CO COCOCOCOCNCNCNCO
Ph
w 2
pc
w
u pq 53 Ph
<
Ph
2 pq 2 J Ph
3 2 O
Ph*
w o Ph
Q O PQ & 3
O PQ M pc5
PJ H
o
Ph
O PJ
Q p< 2 w Ph Ph
< Ph Ph
DU J
-7
s
Ph s H 00 PJ 2 Ph
EC
u -I
o o H O H
H X H X 2 2
Ph H Ph CJ o I— Ph Ph
O O pq a < O PJ 2 55 £
H PQ hJ p< PC H Ph U U
213
214 Theme Four Computers Create
in the feature, the program draws a line from point z in the array rfzsp to
point i + 1. My notation is merely shorthand. A real display command
would call for a line from the point whose coordinates are disp(i,l) and
disp(i,2) to the point with coordinates disp(i+l,l) and disp(i+l,2).
The heart of facebender is its exaggeration routine. Its structure is
even simpler than the display routine I have just outlined (Figure 21.6).
For each of the 186 facial points in the arrays face and norm, the loop
calculates a new array called bend. The new array encodes the carica-
ture-to-be. Each coordinate of the array bend is calculated by adding the
corresponding coordinate of the array face to a quantity that exaggerates
the differences between norm and face. The exaggeration factor / is
typed in by the user; / then multiplies the difference between the hori-
zontal coordinates of face and norm, and it also multiplies the difference
between the vertical coordinates.
The only things left to do are to organize the program and, option-
ally, to tune up the drawing routine. A simple, nonprocedural approach
book that is devoted largely to easy programs. I asked Brennan for an al-
ternate method. Could straight lines be used instead? Much to her sur-
prise and mine, caricatures drawn with straight lines proved almost as
good as the onesdrawn with splines. Indeed, all her images appearing
here were drawn using straight lines. With only a small loss in aesthetic
value the programmer can avoid a most troublesome technique. One can
immediately set about digitizing a favorite photograph.
Brennan's caricature generator has been applied in several studies of
facial recognition. Faces from her program have been transmitted over
telephone lines as part of an experiment in teleconferencing at the Mas-
sachusetts Institute of Technology Media Laboratory. In 1985 she did
an experiment with Gillian Rhodes of the University of Otago in New
Zealand, who was then a graduate student working with Roger N. Shep-
ard of Stanford University. First she generated caricatures of faculty
members and students in the psychology department at Stanford. The
caricatures were then tested for recognizability against standard line
drawings.
Brennan has summarized the findings: "The
caricature generator
was particularly useful for this study because enabled us to generate
it
Further Reading
A. K. Dewdney. The Magic Machine: A Handbook of Computer Sorcery. W. H.
Freeman, 1990.
Voltage Sculptures
(^^n the day of the earth year 2991, the Armstrong interstellar
first
spacecraft touched down on the fourth planet orbiting the star Tau Ceti.
The Armstrong's crew detected movement from the northeast and fo-
cused the ship's camera on a distant rocky cliff. There on a ledge was a
nest made of rock crystals and an egg that resembled a fried pastry, a
French cruller to be exact. The egg began to dissolve, and from it
emerged a snakelike creature composed of two intertwined rings. The
mission biologist quickly dubbed it a "gorgonoid." As the probe moved
closer to get a better look at the gorgonoid, the creature stiffened in
fright and bounced off the cliff into an acetylene river.
To be sure, the world of the gorgonoid is science fiction, but its image
resides in a computer at the IBM Thomas J. Watson Research Center.
Clifford A. Pickover, a graphics wizard at IBM, created the alien I call
the gorgonoid to demonstrate powerful, new tools for computer
graphics. He has developed the techniques as part of his mission to help
other scientists visualize the intricate shapes produced by physical phe-
nomena or derived from theories. Pickover, whose microscopic bio-
morphs appeared in my book, The Magic Machine, describes his cre-
ations as "graphics from an unseen world" (Figure 22.1 and color
insert).
Although the gorgonoid egg looks like an alien life-form, it is actually
a model based on physical principles discovered in terrestrial laborato-
ries. If one could peel away the "shell" of the gorgonoid egg, one would
216
22 Voltage Sculptures 217
find a frame composed of two "wires." One is bent into a circle; the
other winds around the circle in a spiral that rejoins itself. If the wires
were charged with a certain voltage, they would generate an electric
force that would be stronger at points close to the wire frame than at
points farther away. Pickover' s computer program finds all the points
representing a given strength of the force and then plots them to form
the shell of the gorgonoid egg. Pickover calls this imaging technique volt-
age sculpture.
Pickover engages in the art of voltage sculpture to depict a variety of
atomic structures from single molecules to the complex spiral of DNA.
Because the voltage sculpture displays the electric forces surrounding
the molecules, investigators may be able to deduce how some molecules
produced by living cells can fit certain receptor sites in other cells.
The young gorgonoid is not a voltage sculpture but what might be
called a worm necklace. Like the egg, the gorgonoid is based on two wire
loops, one winding around the other. To make the body of the gorgon-
oid, Pickover adorns the wires with spherical beads: large ones for the
circular wire, small ones for the spiral one. The beads are spaced evenly
along the wires, and consecutive beads overlap.
The mature gorgonoid is a worm necklace made of three wires: the
wraps around the second, which in turn curls around the third. The
first
mature gorgonoid also has an eye made from three nearly concentric
spheres that intersect to form an iris from one sphere and a pupil from
another.
A mature gorgonoid can spot a predator a mile away through an am-
monia haze —
an important survival strategy when it is being stalked by
a pacmantis. This cup-shaped creature spends half its time basking in the
rays of Tau Ceti. But when the pacmantis gets hungry, it rolls on the
ground, opening and closing its mouth like the computer sprite known as
Pac-man.
The anatomy of the pacmantis is no more complicated than the mor-
phology of the gorgonoid. To bring the pacmantis to life, Pickover
creates a computer pendulum. He simulates a ball that is tied to one end
of a rigid wire; the other end is connected to a pivot that allows the wire
and ball to swing freely in all directions.
Initially, the pendulum is pushed sideways with a certain velocity
and swings down under the influence of gravity. After it swings back and
forth, it arrives at a point that is a certain distance away from its starting
point. In the course of its subsequent swings, the ball covers most of the
available space within the sphere of possible positions.
22 Voltage Sculptures 219
x = Rs\n(At)cos(Bt)
y = /?sin(vAf)sin(Bf)
z = Rcos(At)
R, A, and B are constants. For each value of t, the three formulas collec-
tively specify a single point in three-dimensional space. As the value of t
is incremented (as time passes), the formula produces a succession of
points that generate the spherical Lissajous curve.
By setting values for R, A, and B, the rates at which the curves oscil-
late, one may generate fascinating figures. The curve will close back on
itself unless the ratio of A to B is an irrational number, not a likely event
in a computer.
Readers can devise a simple computer program to view a spherical
Lissajous curve on a two-dimensional screen. The program should first
ask for the values of R, A, and B. The program should then enter a loop
where the value of t is increased from, say, 1 to 1,000. For each value of
t, the program should calculate x and y according to the formulas. The x
Further Reading
Clifford A. Pickover. Computers, Pattern, Chaos, and Beauty. St. Martin's
Press, 1990.
23
j r y Han
222
23 Latticeworks by Hand 223
here. Later I discovered the same latticework in a book about Islamic art
of the medieval period. My deflation at not being first was more than
compensated for by the discovery itself; the method seemed confirmed.
Since then it has been my lot to "rediscover" other designs.
The method requires the would-be artisan to set up a grid of points.
The grid is limited to one of four types: triangular, square, rectangular or
hexagonal. Such grids are easy to lay out by ruler or compass: draw a
base line, then use the compass to mark off evenly spaced points. Square
and rectangular grids employ a right-angle construction to add new
points above and below the base line. Triangular and hexagonal grids re-
quire equilateral triangles.
The design under discussion began life as a triangular grid. A circle
was then drawn at each of the grid points. Here intuition made its first
entrance, because the size of the circle happens to be critical. In a mo-
ment I shall explain the role intuition may play in selecting the size.
Once the circles are all drawn, the amateur artisan selects points
evenly spaced around the circle. These points will anchor the lineal ele-
ments of the design. The position and number of points must reflect the
symmetry of the grid itself. In other words, the points should preserve
symmetry with respect to reflections and rotations. Any of the intended
symmetries should carry points on one circle onto points on another cir-
cle or on the same circle. In the example under construction the number
of points on each circle must be a multiple of 3. 1 chose 12 to give body to
the lattice. Since the underlying pattern was to have reflectional sym-
23 Latticeworks by Hand 225
metry, only two positions for the points on the circles were possible. I
chose the position in which six of the points were closest to the sur-
rounding circles. As a general rule, whenever there is a choice, the best
decisions are those that harmonize with a symmetry already present.
In the next stage of construction one joins the points on each circle to
points on other circles. Here intuition makes a second entrance. The
possibilities appear to be so numerous that only intuition would seem to
serve. In fact, the combinatorial possibilities are greatly limited once
more by conditions of symmetry: if I join a certain point on circle A to
another on circle B, the symmetries of the pattern carry that connection
onto other points on circle A. Before one has drawn more than two lines
it may be necessary to erase the experiment and try another connection.
A kind of feedback loop binds this design phase with the earlier
choice of circle size. Once a seemingly satisfactory and consistent
scheme of interconnection has emerged, the results may look unauthen-
tic,not to mention ugly. The lines do not harmonize with the symmetry
of the pattern. In such a case it is usually obvious whether shrinking or
expanding the circles will produce connections that parallel the major
symmetries of the pattern. Here intuition may provide the leap of in-
sight, a kind of artistic "Aha!" experience. In the mind's eye one sud-
denly sees the lines generated by the new circles.
At this point in apprenticeship a certain excitement causes the com-
pass and ruler to quiver slightly. An amazement that is perhaps half ar-
tistic and half mathematical grips the holder of these instruments.
Should one take credit for an intuition that was merely acceding to ge-
ometry?
In any event, it is now time to pave the highways of thought by giving
them some width. No sophisticated system of roads should suffer traffic
lights, and so how can the angular freeways be interlaced? In true weav-
ing, after all, overs and unders alternate. Can the artisan be forced into
some kind of logical cul-de-sac where a road faces two consecutive un-
derpasses? Topology saves the day.
The following experiment in scribbling shows how. Draw a large
rectangle on a sheet of paper. Then scribble inside the rectangle, abiding
by only two rules:
ing, it already has the required structure. In other words, one never finds
that an overpass is called for at a crossing that has already been desig-
nated an underpass. Eventually all bridges have been built and the scrib-
ble takes on an appearance that is almost intelligent.
The over-under rule works because in a sense it must. The simplest
demonstration at a public level invokes a pleasant thought excursion.
The scribble divides the rectangle into many small regions, or pieces. It
turns out that the regions in the rectangle can each be given one of two
colors, so thatno two regions sharing a common boundary are assigned
the same color. (A convincing elementary proof of this property would
take at most a few paragraphs, but I hasten to the punch line.) Suppose
the regions are painted in this manner with, say, red and blue paint.
Driving along one of the roads toward a crossing, we would notice one of
two things: either the region on our right would be red and the one on our
left would be blue or vice versa.
23.3) .
The second design was produced by methods similar to the first. Ad-
vanced latticeworks have not only what might be called primary circles
of inflection but also secondary ones. Each five-pointed star in the sec-
ond design arises from such a secondary circle. I have included two ad-
Further Reading
Issam El-Said and Ay§e Parman. Geometric Concepts in Islamic Art. World of
Islam Festival Publishing Company, London, 1976.
Illustration
Text
Color insert
231
In
Acceleration table, in TREK program, 87 Lorenz, 93-99
Addition, neural network, 56 one-point, 101, 194
Affine transformation two-point, 101, 194
in IFS, 109-118 Augmented finite-state machine
for natural system, 120-128 (AFSM), 38
AFSM (augmented finite-state machine),
38 Back-propagation algorithm, 49-50,
Alexandrov, A. D., 160 53-55
Algorithm (See also Program) Barnsley, Michael F., 109, 112,
back-propagation, 49-50, 53-55 116-118, 119-120
BEAT, 186-187, 190 BASIC language, 74-78, 83-84, 197
BIRDIE, 72, 79-80 BEAT (algorithm), 186-187, 190
British Museum, 29 Bifurcation diagram, 193-194
CANON, 182-186 Billiard-ball computer, 30-31
CLOUD, 123-125 Binary principle, 14, 16
EAGLE, 72, 79-80 BIRDIE (algorithm), 72, 79-80
FACEBENDER, 210-214 Bolker, Ethan D., 161
GRIN, 154-155 Brain
hill-climbing, 55 human, 26-36, 67, 174
HOLE IN ONE, 71-78 infinite, 33-36
IFS, 123 of a tur-mite, 62-65
Lyapunov, 107-108 Braitenberg, Valentino, 43
Mark V. Shaney, 203 Brennan, Susan E., 205-215
POLARNET, 46, 48-56 British Museum Algorithm, 29
SE Q, 166-170 Brooks, Rodney, 37
SOLFEGGIO, 180-183
TREK, 83-92 CANON (algorithm), 182-186
TURMITE, 64-65 Caricature, by computer, 205-215
WAVE, 126-127 Cartesian coordinates, 49, 52-53
WEATHER WHEEL, 96-99 CAT (computerized axial tomography)
Alternating tripod gait, 41-43 scan, 148-157
Ammonoid, 219 Catastrophic pattern, 150-153
Analog multiplication, 25 Categorical pattern, 150-154
AND gate, 14, 18-23 Cauchy, Augustin-Louis, 162
in billiard-ball computer, 30-31 Cauchy's theorem, 162
Angle, Colin, 38 Chain
Apraphul, island of, 16 in catastrophic pattern, 152-153
Artificial intelligence, 26-36 Markov, in language program, 204
in I.Q. testing, 174 Chaos
Attila, a robot, 43-44 in logistic system, 101-108, 192
Attractor in music, 191
chaotic, 101-102 in weather system, 93-99
234 Index
Machine 166-170
augmented finite-state (AFSM), 38
millipede, 41 Olsen, Odd Arild, 65
Turing, 57-67 One-point attractor, 101, 194
Mandelbrot, Benoit B., 28, 119 Orbit, of spaceship, 81-92
Mandelbrot set, 28-29, 35 OR gate, 8, 18-22
Markov chain, in language program, 204 Over-under method, 226
Markus, Mario, 100-103, 103, 107
Mark V. Shaney (algorithm), 203 Pattern
Mark V. Shaney program, 199, 202-204 catastrophic, 150-153
Memory, in rope-and-pulley computer, categorical, 150-154
22-24 reconstruction of scanned, 152-157
Memory spindle (of Tinkertoy of a tur-mite, 61-67
computer), 7-15 PC Therapist program, 202
Method Pendulum method, 218
circle-grid, 224-226 Penrose, Roger, 26-32
in-betweening, 207-208 Period doubling, in logistic system, 195
over-under, 226 Periodic forcing, in logistic system, 103
pendulum, 218 Pickover, Clifford A., 216-221
pyramid, in numerical-sequence Pigeonhole principle, 135-136
completion test, 167 Pixel, in golf display, 74-75
worm-necklace, 218-219 Platonic reality, 28
Microminiature golf, 71-80 Polar coordinates, conversionof, 48-56
8
W. H. Freeman and Company
41 Madison Avenue
New York, NY 10010
20 Beaumont Street
Oxford OX1 2NQ, England