Re: Algorithmic Revolution?

From: Hal Finney <hal.domain.name.hidden>
Date: Sun, 24 Nov 2002 16:17:26 -0800

I think there are a couple of things about Wolfram's book which aren't
well understood.

Most importantly, he is not specifically commited to cellular automata.
He does focus on them, especially 1-dimensional, 2-state CAs, as a
particularly simple model of computation, which also has the property
that a relatively high percentage of randomly chosen programs produce
apparent complexity. But he explores a number of other computational
systems, including higher dimensional and higher state CAs; mobile CAs;
Turing machines; substitution systems; sequential substitution systems;
tag systems; cyclic tag systems; register machines; symbolic systems;
arithmetic; recursive sequences; iterated maps; continuous (non-quantized)
CAs; partial differential equations; network systems; multiway systems;
constraint satisfaction systems; and higher dimension versions of many
of these.

The lesson he draws is that generally, the same kinds of patterns
are seen in virtually all of these ways of expressing computation.
You see simple, constant outputs; simple repetition; chaotic patterns;
and occasionally, the mysterious "structure" on the edge of chaos, which
often shows tantalizing particle-like phenomena and other interesting
analogs to real-world phenomena.

Where he does fall back on CAs, I don't think his point is so much
that the phenomena are based precisely on CAs, but that random, simple
algorithms when implemented in CAs often produce very similar patterns to
what we see in the real world. And that this is probably not coincidence.
It suggests that these kinds of patterns could be considered attractors
in pattern space. They are easier to produce than other patterns that
might seem superficially similar. Their algorithm complexity is lower.
And this insight might inform our efforts to understand the true nature
of the phenomena which create these patterns.

Where Wolfram turns to physics, his speciality, he explicitly departs
the CA model as he tries to sketch a possible mathematical basis for
the universe that is consistent with the paradoxical phenomena of QM and
relativity. He uses network systems, hypothetical sub-quantum "nodes"
which are connected to one another and whose connections might change
under simple rules. This is not completely original; I think Wheeler
and others pursued ideas similar to this back in the 70s. Wolfram takes
it a little farther in showing how you could get some relativity-style
phenomena, but it's a very bare beginning effort.

My main point is that characterizing Wolfram as saying that the universe
is a CA, or biological patterns or fluid turbulence or any other phenomena
are caused by CAs, is not correct. He is not saying these phenomena are
caused by CAs, he is saying that extremely simple CA programs produce
similar phenomena, suggesting that such phenomena emerge spontaneously
from computational systems.

As for the universe, I think his point is that the grand, mathematical
elegance of string theory and similar methods is the wrong approach.
These beautiful mathematical models are too rigid and brittle to describe
a universe like ours. The universe is more likely to be built out of
a messy, random and simple little program that just happens to create
patterns that have the properties necessary for life to evolve.

In the context of our list, this can be thought of as a philosophical
bias towards Schmidhuber and away from Tegmark. In Tegmark's model,
string theory is relatively near the origin of the tree of mathematical
structure; it is simple. If it produced enough particles and interactions
of the right kinds to allow for life, it would be an excellent candidate
for the place where we live. But in Schmidhuber's model, it's just as
likely that some random hodgepodge of a program a few thousand bits in
length will "just happen" to produce a very robust, dynamic and varied
universe with all kinds of structure at different size scales. Such a
universe is an inherently friendly home for life as there are so many
possible niches for it to grow.

Of course, at this point we are in no position to decide between these
two philosophies. Wolfram's book is ultimatly a call to our intuition,
an appeal for equal time to be given to Schmidhuber-ish approaches
based on random programs, as for the traditional Tegmarkian mathematical
modelling which is done in physics. I think there is something to be
said for this shift in perspective, and I hope that at least a small
minority of researchers will attempt to move Wolfram's program forward.

Hal Finney
Received on Sun Nov 24 2002 - 19:18:29 PST