Re: Algorithmic Revolution?

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

One more point with regard to Wolfram and our list's theme. I think
that implicit in his conception of the underlying rules of the universe
you have to assume some kind of all-universe model. The reason is that
he does not expect our universe's program to be particularly special
or unique. He thinks it will be relatively short, but given the kind
of computational structures that might be the basis for the universe,
the program is expected to be basically random.

Every computational system has a certain percentage of its programs that
can produce interesting-looking structure, and the expectation is that
the same thing will hold for whatever computational model turns out to
most simply express the universe's program. Whatever our program is, it
will turn out to be one of the ones that produces structure. But these
are almost certainly a tiny percentage of the whole, based on Wolfram's
results. And the specifics of which ones will produce structure are
very difficult to define. Making a tiny change in a program will often
produce a completely different output, at least with the computational
systems Wolfram investigates. The ones which produce structure are
scattered very randomly throughout the space of all possible programs.

For example, among the nearest-neighbor, 2-state, 1-dimensional CAs that
Wolfram uses as his simple exemplars, there are 256 possible different
programs, which Wolfram numbers from 0 to 255. As it turns out, only one
of them, program number 110, produces a certain kind of complex structure
that has particle-like behavior with very complex kinds of interactions.
Of all of them, this is the one which at least superficially would be
the most likely to be able to evolve life (although it's almost certainly
too simple to actually do so).

But let's suppose that we learned that we lived in a universe based on
rule 110. Why would that be? Why, of all the 256 possible programs,
would only rule 110 exist? Well, there are two plausible answers.
One is that someone selected rule 110, but that raises all kinds
of insurmountable problems of its own. The other is that all of the
programs were instantiated, and then of course we turned out to live in
rule 110 because it was the only one that could sustain life.

So Wolfram's approach leads very naturally to the assumption that all
possible programs are being run. If it does turn out that our universe's
program is relatively simple but still densely packed and "random" among
a vast space of comparable programs, most of which would produce sterile
universes, then I think we would be forced to seriously consider that
all of the other programs were being run, too.

My one concern is that if Wolfram is right and our universe is a random
program from some set, and if there are much more than on the order
of 100 bits in the program, we will never be able to find the right
program. If the nature of the program space is similar to what Wolfram's
explorations suggest, that most of the space is unstructured and there
is no way to identify the likely fruitful programs, there will be no
way for us to know if we are on the right track or not. We won't have
the hope of finding a program that "almost works" and then successively
refining it to get closer and closer, because the true program will be
completely different from an almost-true program.

The situation will be something like the search for a cryptographic key,
where you can't really hope to get closer and closer until you get it.
You're stabbing totally in the dark until you fall upon the right one.
And if the search space is too large, you will never find the answer.

Hal Finney
Received on Sun Nov 24 2002 - 19:41:33 PST