But what the picture on the facing page demonstrates is that if one just does statistical analysis by computing frequencies of blocks one will see no evidence of any such underlying simplicity. One might imagine that if one were to compute other quantities one could immediately find such evidence. … And perhaps as a result of this, it has sometimes been thought that if one could just compute frequencies of blocks of all lengths one would have a kind of universal test for randomness.

And in general how short a description of something one can find will depend on what features of it one wants to capture—which is why one may end up ascribing a different complexity to something when one looks at it for different purposes. But if one uses a particular method of perception or analysis, then one can always see how short a description this manages to produce. And the shorter the description is, the lower one considers the complexity to be.

But what if one looks at other kinds of systems? … But if one has such a system, how does one decide what questions are interesting to ask about it? … And if one does this, then what I have found is that one is usually immediately led to ask questions that run into phenomena like undecidability.

Yet having said this, one can ask how one can tell in an actual experiment on some particular system in nature to what extent intrinsic randomness generation is really the mechanism responsible for whatever seemingly random behavior one observed. … Thus for example, however many times one runs a rule 30 cellular automaton, starting with a single black cell, the behavior one gets will always be exactly the same. … And in such systems, one can

But an obvious issue with saying that one should study systems with the simplest possible structure is that such systems might just not be capable of exhibiting the kinds of behavior that one might consider interesting—or that actually occurs in nature. … Much later one may go back and look at the simpler system again. … But much more often, one will instead discover behavior that one never thought was possible.

And one can then consider the axioms of a system as defining possible transformations from one sequence of these elements to another—just like the rules in the multiway systems we discussed in Chapter 5 . … But just as in the multiway systems in Chapter 5 one can also consider an explicit process of evolution, in which one starts from a Simple idealizations of proofs in mathematics. … The proofs above then show how one string—say —can be transformed into another—say —by using the axioms.

But after these one has to go a long way before one finds other ones. So if one were to go still further, would one eventually find yet more? It turns out that with the criterion we have used one would not.

Then one can ask whether such squares are more often black or more often white, and one can compare this with the result obtained by looking at the frequencies of letters in the language of the original message. … For unless one has the correct key, the chance that what one recovers will be meaningful in the language of the original message is absolutely negligible. … Methods like the ones above still turn out to allow features of the encrypting sequence to be found.

[No text on this page] Evolution of one-dimensional slices through some of the two-dimensional cellular automata from the previous two pages [ 173 , 174 ]. Each picture shows the colors of cells that lie on the one-dimensional line that goes through the middle of each two-dimensional pattern. The results are strikingly similar to ones we saw in previous chapters [ 2 , 3 ] in purely one-dimensional cellular automata.

But if one considers for example analogs of logic for variables with more than two possible values, the picture below shows that one immediately gets systems with still fewer theorems. … But if one picks a different axiom system for logic—say one of the others on page 808 —then the length of a particular proof will usually change. … But as one tries to prove progressively longer theorems it appears that whatever axiom system one uses for logic the lengths of proofs can increase as fast as exponentially.