Basic logic is not, since at least in principle one can always determine the truth of any statement in this system by the finite—if perhaps exponentially long—procedure of trying all possible combinations of truth values for the variables that appear in it. And essentially the same turns out to be the case for pure predicate logic, in which one just formally adds "for all" and "there exists" constructs.

So what then happens if one looks at all possible simple axiom systems—much as we looked, say, at all possible simple cellular automata earlier in this book?

undecidability—this is no longer the case, and as I discussed above I suspect that it will actually be quite common for there to be all sorts of short theorems that have only extremely long proofs. … And so, for example, what are usually viewed as more successful areas of pure mathematics may have more compact networks, while areas that seem to involve all sorts of isolated facts—like elementary number theory or theory of specific cellular automata—may have sparser networks with more tendrils.

And indeed it is sobering to notice that if one just listens even to bird songs and whale songs there is little that fundamentally seems to distinguish them from what can be generated by all sorts of processes in nature—say the motion of chimes blowing in the wind or of plasma in the Earth's magnetosphere. … But it is extremely common in all sorts of natural systems to see effects that propagate from one element to another.

And in fact in the past it was often assumed that just to generate radio signals at all must require intelligence and technology. … But in practice essentially all serious searches for extraterrestrial intelligence made so far have been based on using radio telescopes to look for signals with sharply defined frequencies.

But in practice if one just receives a signal one normally has no way to tell which of all possible rules for producing it were in fact used. … But the discoveries in this book have made it clear that in fact such computation is quite common in all sorts of systems that do not show anything that we would normally consider intelligence.

Register Machines All of the various kinds of systems that we have discussed so far in this chapter can readily be implemented on practical computers. … But at the lowest level, the CPUs of all standard computers have registers that store numbers, and any program we write is ultimately converted into a sequence of simple instructions that specify operations to be performed on these registers.

It has been observed that this happens for all initial values of n up to at least 10 16 , but despite a fair amount of mathematical effort since the problem was first posed in the 1930s, no general proof for all values of n has ever been found. … In all other cases, the values of n in the sequence appear to grow forever. … One reason that all sequences do not grow forever is that even with perfect randomness, there will be fluctuations, and occasionally n will reach a low value that makes it get stuck in a repetitive sequence.

Comparison of [periods for cellular automaton] rules Rules 45, 30 and 60, together with their conjugates and reflections, yield the longest repetition periods of all elementary rules (see page 1087 ).

The pictures above show representations of the mappings corresponding to various rules, obtained by plotting Sum[a[t + 1, i] 2 -i , {i, -n, n}] against Sum[a[t, i] 2 -i , {i, -n, n}] for all possible choices of the a[t, i] . … Rule 170 is the classic shift map which shifts all cell values one position to the left without changing them.