This leaves only one remaining type of system from Chapter 3 : register machines. … As an example, one can consider a generalization of the arithmetic systems discussed on page 122 —in which one has a whole number n , and at each step one finds the remainder after dividing by a constant, and based on the value of this remainder one then applies some specified arithmetic operation to n .

So one might wonder how then it could be consistent with experiments that have been done in physics? … Examples of one-dimensional cellular automata which exhibit a symmetry between space and time. … The particular rules shown are reversible second-order ones with numbers 90R and 150R.

Yet from what we saw in Chapter 11 one suspects that in fact there are not. … But if the number of elements that can be updated in one step is sufficiently different this tends to become impossible. And thus for example the first picture below shows that it can take t 2 steps for a Turing machine that updates just one cell at each step to build up the same pattern as a one-dimensional cellular automaton builds up in t steps by updating every cell in parallel.

between class 2 and class 3 in terms of what one might think of as overall activity. … For different values of this parameter, the behavior one sees is different. … But since continuous cellular automata have underlying rules based on a continuous parameter, one can ask what happens if one smoothly varies this parameter—and in particular one can ask what sequence of classes of behavior one ends up seeing.

In the intermediate pattern of behavior one may also be able to identify some definite structures. Ones that do not last long can be very different from ones that would persist forever. … One immediate difference, however, is that in traditional particle physics one does not imagine a pattern of behavior as definite and determined as in the picture above.

possible strings of a given length are eventually generated if one starts from the string representing "true". … In general one might have to wait an arbitrarily large number of steps to find out whether a given string will ever be generated. … I suspect that it has to do with the fact that in mathematics one usually wants axiom systems that one can think of as somehow describing definite kinds of objects—about which one then expects to be able to establish all sorts of definite statements.

Network Systems One feature of systems like cellular automata is that their elements are always set up in a regular array that remains the same from one step to the next. … Of course, to make a picture of a network system, one has to choose particular positions for each of its nodes. … In constructing network systems one could in general allow each node to have any number of connections coming from it.

But the key to understanding what is going on is simply to realize that one has to think not only about the systems one is studying, but also about the types of experiments and observations that one uses in the process of studying them. … But what exactly is it that determines the types of initial conditions that one can use in an experiment? … But how can one compare such processes?

The impossibility of such perpetual motion machines is one common statement of the Second Law of Thermodynamics. … The specific value of the entropy will depend on what measurements one makes, but the content of the Second Law is that if one repeats the same measurements at different times, then the entropy deduced from them will tend to increase with time. … But in a practical experiment, one cannot expect to be able to make anything like such complete measurements.

And if one did this what one would find is that many of the rules exhibit obviously simple repetitive or nested behavior. … If one starts from scratch then it is not particularly difficult to construct rules—though usually fairly complicated ones—that one knows are universal. … But if one is just given an arbitrary rule—