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