Simple Complexity and Comdex
Press, L., Communications of the Association for Computing Machinery, Volume 33, Issue 7 (July 1990), Pages: 21 - 26 July, 1990.
One of todays' emerging paradigms is the view that complex behavior
or form can emerge from the interaction of relatively simple
components, if you have enough of them and they have enough time to
do whatever they do. The emergent behavior or form might seem
systematic or chaotic. Some examples are neural nets, cellular
automata, fractals, electronic mail networks, market economies,
whirlpools, and snowflakes. Years ago, similar systems were often
called "self-organizing," and they were found in models of memory,
pattern recognition, multilevel stores, libraries, etc. However,
the area languished, awaiting the development of theory and
powerful hardware. Personal workstations played an important role
in facilitating experimentation with this sort of model, and mass-
market personal computers are now up to the task.
The Blind Watchmaker
If you are drawn to such topics or would like to learn more, take a
look at zoologist Richard Dawkins' book "The Blind Watchmaker," and
it's companion software. The title of the book alludes to the
argument of William Paley, an eighteenth-century theologian, that
complex objects like watches or human eyes had to have been
purposely designed. Paley felt that the existence of watches
implied watchmakers and the existence of people implied a God.
Dawkins disagrees, and sets forth a theory in which evolution
follows from the existence of self-copying or replicating entities
(like crystals, ideas, or DNA molecules), occasional copying
errors, and some property of the replicator that influences the
probability of its being replicated. Given time for countless
millions of replication generations, he feels we will inevitably
see gradual, cumulative evolution, leading to complex systems like
people and trees. It took hyracotherium 20 million years to evolve
from the size of a terrier to that of a modern horse.
Perhaps I liked the book because much of it is couched in
information processing terms, for example, DNA molecules are
compared to high-capacity ROM. His explanation of natural
selection also leads down entertaining side roads like speculation
on the three-dimensional "image" of its environment that a bat
constructs from audio input. How does the bat's subjective
experience of the three-dimensional world compare to one based on
optical input? Dawkins also constantly reminds the reader, using
memorable examples, that we do not have the ability to accurately
conceive of geologically long time spans or extremely improbable
events (given our short lives).
If you would like to learn more about natural selection while
having a good time and taking some interesting side trips, you will
like this book, but there is more. Dawkins has also written a
program to go with it. The program illustrates the effect of
cumulative small changes over time, on artificial, 18-gene
"biomorphs."
Figure 1 shows a screen with a biomorph in the center, surrounded
by 14 potential progeny. However, the potential progeny are not
exactly like the parent. They are "mutants," with a different value
for one of their simulated genes. The "genes" are values in an
array, called the "chromosome." The biomorphs are drawings
produced by a procedure which uses the current value of chromosome
array as input. For example, gene 9 determines the number of
branchings in the figure, genes 1-3 determine its horizontal
extent, etc. Some of the two-valued genes can be permanently set
on or off.
Evolution takes place because only one of the 14 possible progeny
will become the parent of the next generation. It is like a seal
colony in which only males who win harems breed. But, which of the
progeny will be selected? The user plays the role of Mother
Nature, choosing the lucky biomorph. The selected biomorph moves
to the center of the screen, 14 of its possible offspring are
displayed, and you choose again, etc.
The user guides biomorph evolution. If you decided to try to
evolve a small biomorph, you would glance at each new generation
and select the one which seemed smallest. After a few generations,
you might be down to a simple stick with a few branches.
Similarly, you can go for large biomorphs, roundish biomorphs,
etc. The most striking feature I noticed was that there would be
relatively little change for several generations, followed by a
sudden jump (see Figure 2). Biomorph evolution is definitely non-
linear. A slight change in a gene can produce marked change in the
biomorph which develops under its control.
In addition to breeding biomorphs, the program lets you engineer
them, save them in albums, record lineage, etc. The publisher even
runs contests for expert biomorph breeders. The program runs on
the Macintosh.
Desktop Fractals
How long is the California coastline? Measured from a satellite
photo, you might get an answer like 1,000 miles, but an ant that
decides to walk from San Diego to San Francisco, faithfully
negotiating every nook and cranny of the coastline, will cover a
longer distance, and a bacteria will have a major hike. Seen from
very close in, the california border seems to be an infinitely long
line containing a finite area. Weird. Furthermore, there is some
similarity in the view of the wandering coastline from the
satellite or ant or bacteria perspective. By capitalizing on this
self-similarity at different levels, simple programs can generate
complex images.
For example, the fern in Figure 3a, was generated by the short
program listed in Figure 3b. The drawing is produced by a 4-line
loop, which is driven my the 48 integers in array "a". The loop
generates a different drawing if one or more of the 48 input
coefficients are changed.
The fern program was written by Michael F. Barnsley, and his fern
image was on the cover of the June, 1989 issue of National
Geographic. The program is based on Barnsley's theory of iterated
function systems (IFS), and the 48-integers are an example of an
IFS code.
You can learn more about IFS codes and the pictures they generate
with Barnsley's Desktop Fractal Design System, a program for PC-
compatible computers, published by Academic Press. The program
comes with a library of IFS codes for assorted drawings, and the
user can alter these by changing the codes, or experiment with his
or her own codes. For example, Figure 4 shows two slightly
different drawings and the IFS codes which produced them.
The current program is limited to two-dimensional drawings, but
Barnsley is working on a Macintosh version, a version which can
concatenate images to make more complex drawings, and if he can
come up with a good user interface, a 3-d program. If you decide
to really get into it, you can work your way through Barnsley's
upper-division math text "Fractals Everywhere."
Barnsley is also pursuing practical application of IFS for image
compression. The IFS code for producing an image is a much more
concise representation of that image than its full bitmap, but,
given an arbitrary image, can you automatically derive the IFS code
from which it can be accurately reproduced? Barnsley feels he can,
and has formed a company called Iterated Systems Inc. to develop
commercial products. They are marketing hardware and software
solutions which run on PC-compatible computers and Sun
Workstations. Figure 5 is an example of an image generated from an
automatically derived IFS code.
From the demonstrations I have seen, it seems as though this
technique is suited to the application niche where extremely high
compression is necessary and a degree of inaccuracy reproduction is
tolerable. It is an asymmetric technique, taking longer to
compress an image than to regenerate it. An attractive feature of
Barnsley's approach is that the user can tune the system, making
tradeoffs between fidelity, compressed file size, and compression
and expansion times.
Golden Oldies
Among the first people to get caught up in the idea of complex
systems and behavior emerging from simple repetition were the MIT
hackers running Martin Gardner's Life program on a very expensive
personal computer, the TX-2, at MIT in the 1950s. The rules of
Life are simple. The screen is a rectangular grid on which
"living" points are represented by an asterisk, and "dead" points
are blank, so each point has 8 adjacent neighbors. You initialize
the program with a configuration of living points, and in
successive generations a point either lives or dies according to
these rules:
x A cell with 2 or 3 living neighbors survives for another
generation, otherwise it dies from overcrowding or lonliness.
x A birth occurs in an empty cell with 3 living neighbors.
Early Life hackers discovered initial configurations which would
give rise to "organisms" which would glide across the screen, spawn
"children" which glided away, "eat" others, etc. They were
intrigued by these systems, and if you think you might be, get the
"Golden Oldies" game disk from Software Toolworks. In addition to
Life, it contains an early adventure game, the original Pong, and
Clark Weisenbaum's non-directive therapy game Eliza. You could
also write your own Life program rather quickly, and A. K.
Dewdney's book the "Armchair Universe," contains ideas for several
similar simulations you can program yourself.
Comdex Notes
Switching gears -- I attended the Comdex show, and jotted a few
notes on the back of my program. Here they are.
32-bit Micros: Many manufacturers displayed EISA-bus computers and
motherboards, but none were shipping. The first EISA computers
will be expensive because of profit skimming and the cost of
support chips. In the long run, business considerations, not
technical merit, will determine the market shares of EISA and IBM's
Micro Channel for 32-bit bus machines.
DAT: Digital audio tape (DAT) drives were shown by several
vendors. With gigabyte-plus capacity on a pocket-sized cassette,
and transfer rates around 180 Kbytes/second, DATs seem to have a
bright future backing up LAN servers. Their adoption will be
slowed by competing format standards, DDS (digital data storage)
and Data/DAT. DDS is a sequential format while Data/DAT allows
file and record addressabilty. Both have powerful backers. For an
overview of DAT technology and formats, see the special section of
the November 30, 1989 issue of EDN Magazine.
O/S Forecasts: At the last four COMDEX shows, Byte Magazine has
asked attendees which operating system they expected to become the
dominant force in the personal computer market by the end of 1992.
Jeffrey Tartar, Editor of the SoftLetter, has been tracking these
surveys, and here is what he found:
Spr Fall Spr Fall
88 88 89 89
Traditional DOS 30% 18% 14% 18%
Extended DOS n/a 31% 30% 31%
Unix 24% 23% 22% 18%
OS/2 32% 16% 20% 16%
Mac 4% 3% 3% 3%
Other 1% 1% 1% 1%
None 9% 8% 10% 13%
Too bad so much time was wasted on OS/2 for the 80286, and too
bad there is not a unified Unix.
Teeny Display: Cyberspace Corporation demonstrated a CGA display
which was a lightweight eyepiece attached to a headband. It was
only an inch or so high, but clearly legible. Their must be some
heads-up applications for this display.
Servers: Compaq demonstrated their Systempro, an expensive,
multiprocessing file server. Novell used it at their booth, where
they ran benchmarks with 250 workstations. I don't know which was
more impressive -- the visual impact of a room with 250 computers
on a wall running benchmarks or the speed of the system, which
easily outran a network half the size with a PS/2 server. Zenith
also has a "super server" and there will be others. Adios
minicomputers.
Winnebiko: Steven Roberts displayed his high-tech recumbent bicycle
in a sponsor's booth at Comdex (see Figure 6). Roberts is an
engineer who has spent the last six years as a free-lance writer
while touring the country on his solar-powered, computer and
communication equipped bike. You can share his adventures
vicariously by subscribing to his newsletter, the Journal of High-
tech Nomadness, buying a copy of his book, or corresponding with
him via email.
Coalitions: IBM and MicroSoft made a joint announcement endorsing
DOS with Windows for systems with 1-2 MB memory and OS/2 for larger
machines (realistically, at least 4 MB). In return for IBM's
support of Windows, MicroSoft agreed to deliver OS/2 versions of
graphically-oriented software before Windows versions. They also
promised 32-bit OS/2 for 1990. WordPerfect and Lotus agreed to
cooperate on user interface innovation and development. Look for a
common user interfaces and dynamic data exchange in Presentation
Manager versions of 123 and WordPerfect.
Flash Disk: Several companies demonstrated systems using Intel
flash EPROMs. Digipro used them in a solid-state disk emulator
which reads at the speed of RAM and writes at the speed of a hard
disk. Psion will use them for removable storage in a line of
portables they announced. According to Intel, the EPROMs can be
safely written 100,000 times. Today they cost more than RAM, but
that can change. It's too soon to guess whether they will be an
effective alternative to rotating storage or the bubble memory of
the 1990s.
Remote Keyboard: The Toteboard, an infrared-linked PC keyboard, was
shown by nView (see Figure 7). I had a chance to test a Toteboard,
and like it. For use in stand-up presentations, it balances
comfortably on one hand and can be pointed in pretty much any
direction. (I used it in a classroom). It would be terrific for
desktop use if the keyboard were a little larger and of higher
quality. Here's hoping they combine their transmitter with a
desktop keyboard.
286 R. I. P.: There were dozens of 386 and 386SX motherboard
vendors at Comdex, which means cheap clones capable of running DOS
with Windows 3.0 and OS/2. Since Comdex, Intel has announced
standard and low-power (for portables) versions of a 20-mhz 386SX,
along with a cache controller, math and Ethernet coprocessors, and
a two-chip AT-interface set. Intel Vice President Michael Aymar
predicts a single-chip PC motherboard (without memory) by 1993. If
Intel does not take legal action, there will also soon be
alternative suppliers for 386 chips. Michael Slater, Editor of the
Microprocessor Report, predicts that 486-based computers will
eliminate high-end (33-mhz) 386s.
Scanners: There were many handheld scanners being offered to system
integrators, so I would expect them to become very cheap also. A
handheld scanner in conjunction with robust optical character
recognition (OCR) software would make a nice scholar or student's
companion. I can imagine myself with a portable PC and a scanner
at the library, recording excerpts from books or periodicals. The
tricky part is OCR software that can read different fonts and
typeset material, but the speed of modern personal computers may
make that commonplace before long.
Touch Screens: The touchscreen technology at Elographic's booth was
a real eye opener. The resolution and sensitivity of their
hardware is terrific. They also have a wide variety of development
software, making it possible to quickly develop applications with
screen constructs which are suited to touch screen. For example,
they implemented a Comdex booth-location system, which was a snap
to use, in just a few hours of Pascal programming using their
tools. If, as I did, you formed your impression of touch screen
hardware and software in the days of low-resolution arrays of LCDs
around the edges of displays, give it a second look.
Floppy Replacement: In 1976 magnetic floppy disks replaced paper
tape as the removeable storage medium of choice for hobbyist
personal computers. That was an obvious move, but the next step is
not so clear -- there are many contenders. Insite Perpherals is
off to as fast a start as any. They demonstrated their "floptical"
disk, on which they record magnetically, but position the read-
write head optically. The precise positioning made possible by the
optically recorded information allows them to squeeze 20.9 MB on a
standard sized 3.5 inch disk. Their drives can also read standard
magnetic media, and they should be available this year. One
industry committee has recommended the floptical disc as a
standard, but the case is far from closed.
=====
Figure 1: Biomorph Evolution. The "biomorph" in the center is
surrounded by 14 possible descendants. The shape of the center
biomorph was determined by the values of the parameters ("genes")
shown in the "chromosome" at the top of the display. Most of the
alternative descendants are "mutants;" for example, the one to the
upper left of the parent differs in the values of the 8th and 9th
genes. "evolution" is controlled by the user who selects which
descendent will survive, becoming the parent of the subsequent
generation.
Figure 2: Biomorph Descendants. Here we have a biomorph (in the
upper left) with 26 of its descendants. Most of the changes
between generations are slight, but the first and 23rd descendants
are dramatically different than their parent. Number 23's mother
explained mathematical attractors, but his father remained
suspicious.
Figure 3: Fractal Fern. This drawing of a fern (a) was generated
by the simple program (b). The heart of the program is the four-
line loop at the end, and the drawing it produces is determined by
the integers in the array "a".
Figure 6 -- This is Steven Robert's current Winnebikeo. He is
currently building the next one which will feature ...
Figure 7 -- hand-held keyboard (B&W photo coming under separate
cover)
==
Pointers:
Dawkins, Richard, "The Blind Watchmaker," W. W. Norton, 1987. An
order coupon for the companion software ($9.95) is in the book.
The Desktop Fractal Design System, Academic Press, Inc., Harcourt
Brace Javanovich, Publishers, New York. This is Michael
Barnsley's software package. His upper division textbook,
"Fractals Everywhere," is also published by Academic Press. If
you are interested in his commercial application of fractals for
data compression, contact Iterated Solutions, Inc., 5550
Peachtree Parkway, Building A, Suite 545, Norcross, GA 30092,
(404) 840-0310.
Dewdney, A. K., "The Armchair Universe," W. H. Freeman and Company,
New York, 1988. This is a collection of Dewdney's "Computer
Recreations" columns from Scientific American Magazine. Several of
them describe systems in which complexity emerges from simple
elements, and they can all be programmed on a personal computer.
Langdon, Christopher, "Artificial Life," Addison-Wesley, Redwood
City, California, 1989. This is the Proceedings of a 1987 Workshop
on the Synthesis and Simulation of Living Systems held at the
Center for Nonlinear Studies at Los Alamos National Laboratory. If
you like the programs described in this column, and want something
more theoretical and varied than Dewdney's book, look at this one
(which includes a paper by Richard Dawkins). The second Symposium
was held recently, and Addison-Wesley will also publish that
proceedings.
The Software Toolworks, One Toolworks Plaza, 13557 Ventura
Boulevard, Sherman Oaks, CA 91423, (818) 907-6789.
Cyberspace Corporation, 4405 International Boulevard, Suite C102,
Norcross, GA 30093-9607, (404) 381-7133
Steven Roberts, Nomadic Research Labs, Box 2390, Santa Cruz, CA
95063, (408) 459-9780, wordy@cup.portal.com
Digipro, Inc., 102 Lowry Street, Huntsville, AL 35805, (205) 536-
2047
Psion, Inc., 118 Echo Lake, Watertown, CT 06795, (203) 274-7521
nView Corporation, 11835 Canon Boulevard, Newport News, VA 23606,
(804) 873-1354
Elographics, 105 Randolph Road, Oak Ridge, TN 37830, (615) 482-
4100
Insite Peripherals, 4433 Fortran Drive, San Jose, CA 95134-2302,
(408) 946-8080.
===
Stop Spaghetti: Is your desk a tangle of wires and cables? O'Neill
Communications demonstrated their LAWN (local area wireless
network). LAWN transmitters cover a 100 foot radius, and the
system is geared toward plug and play simplicity.
O'Neil Communications, Inc., 100 Thanet Circle, Suite 202,
Princeton, NJ 08540, (609) 925-1095