June 30, 2002 -- People tend to engage in a form of primitive thinking known as "like causes like," psychologists have shown.
For example, doctors once believed that the lungs of a fox cured asthma and other lung ailments. People assumed that fowl droppings eliminated the similar-appearing ringworm. Freudians asserted that fixation at the oral stage led to preoccupation with smoking, eating, and kissing.
It is perhaps not surprising, therefore, that people have long thought the complexity of computer outputs was a result of complex programs.
It's been known for a while, however, that this is not necessarily the case. Computer scientists and mathematicians, notably John von Neumann in the 1950s and John Conway in the 1970s, have studied simple rules and algorithms and have observed that their consequences sometimes appear inordinately complex.
Nevertheless, it's safe to say that no one has treated this idea with anything like the intensity and thoroughness of Stephen Wolfram in his fascinating, ambitious and controversial new book, A New Kind of Science.
Simple Rule, Complex Consequences
The book is a mammoth 1,200 pages, so let me in this 800-word column focus on Wolfram's rule 110, one of a number of very simple algorithms capable of generating an amazing degree of intricacy and, in theory at least, of computing anything any state-of-the-art computer can compute.
Imagine a grid (or, if you like, a colossal checkerboard), the top row of which has some white squares and some black ones. The coloring of the squares in the first row determines the coloring of the squares in the second row as follows:
Pick a square in the second row and check the colors of the three squares above it in the first row (the one behind it to the left, the one immediately behind it, and the one behind it to the right). If the colors of these three squares are, respectively, WWB, WBW, WBB, BWB, or BBW, then color the square in the second row black. Otherwise, color it white. Do this for every square in the second row.
Via the same rule the coloring of the squares in the second row determines the coloring of the squares in the third row and, in general, the coloring of the squares in any row determines the coloring of the squares in the next row.That's it, and yet, Wolfram argues convincingly, the patterns of black and white squares that result are astonishingly similar to patterns that arise in biology, chemistry, physics, psychology, economics, and a host of other sciences. These patterns do not look random nor do they appear to be regular or repetitive. They are, however, (in some senses) exceedingly complex.
Moreover, if the first row is considered the input, and black squares are considered to be 1's and white ones 0's, then each succeeding row can be considered the output of a computation that transforms one binary number into another.
Not only can this simple so-called "one-dimensional cellular automaton" perform the particular calculation just described, but, as Wolfram proves, it is capable of performing all possible calculations! It is a "universal" computer that, via appropriate codings, can emulate the actions of any other special-purpose computer, including, for example, the word-processor on which I am now writing.
A number of such idealized universal computers have been studied (ranging from Turing machines through John Conway's Game of Life to more recent examples), but Wolfram's rule 110 is especially simple. He concludes from it and a myriad of other considerations too numerous and detailed to even adumbrate here that scientists should direct their energies toward simple programs rather than equations since programs are better at capturing the complicated interactions that characterize scientific phenomena.
A New Kind of Science also puts forward a "Principle of Computational Equivalence," which asserts, among other things, that almost all processes, artificial (such as his rule 110) or natural (such as those occurring in biology or physics) that are not obviously simple can give rise to universal computers. This is reminiscent of an old result known as the Church-Turing thesis which maintains that any rule-governed process or computation that can be performed at all can be performed by a Turing machine or equivalent universal computer. Wolfram, however, extends the principle, gives it a novel twist, and applies it everywhere.
In fact, his polymathic approach is part of what is exciting about the book. Simple programs, he avers, can be used to explain space and time, mathematics, free will, and perception as well as help clarify biology, physics, and other sciences. They also explain how a universe as complex-appearing and various as ours might have come about: the underlying physical theories provide a set of simple rules for "updating" the state of the universe and such rules are, as Wolfram demonstrates repeatedly, capable of generating the complexity around (and in) us, if allowed to unfold over long enough periods of time.
Some of the book's claims are hubristic and hyperbolic. Many others have been around for a while, but no one has put them all together in such a compelling way to articulate if not a new kind of science, at least a new way of looking at the established kind.
Professor of mathematics at Temple University and adjunct professor of journalism at Columbia University, John Allen Paulos is the author of several best-selling books, including Innumeracy and A Mathematician Reads the Newspaper. His Who’s Counting? column on ABCNEWS.com appears the first weekend of every month.