A New Kind of Science: The NKS Forum (http://forum.wolframscience.com/index.php)
- Pure NKS (http://forum.wolframscience.com/forumdisplay.php?forumid=3)
-- Question on 122R (http://forum.wolframscience.com/showthread.php?threadid=552)

Question on 122R

On page 442-3 of the NKS book is a picture of the reversible cellular automaton 122R.

Question: If allowed to run indefinitely in either direction does it eventually wrap around and meet itself? That is does it form a persistent structure non-orientable as to time?

__________________
L. J. Thaden

"Eventually" is a long time.

In general, any CA on a finite grid eventually repeats. It has to, because the number of possible states is bounded above, while time (by hypothesis) isn't. Once it hits a state, being deterministic and depending only on a single previous state, it must go through the same sequence as it did from that state when it hit it before.

But in general these repetition periods are huge, once the number of cells of width is more than a handful. If the width has a lot of divisors, you might hit a subcycle sooner. But the number of possible states goes up exponentially with the width. If the repetition period is longer than the lifetime of the universe, saying it must eventually repeat it pretty meaningless.

Two points:

(1) Actually, I meant to ask whether anyone has run 122R out until it terminates.

Conceivably it could terminate in another cycle that is shared by both ends. Geometrically this might look like the surface of another torus perpendicular to the one formed by the illustration of 122R in the NKS book. If it did form this additional torus, would it also be reversible?

(2) Just a comment on: “If the repetition period is longer than the lifetime of the universe, saying it must eventually repeat it pretty meaningless.”

What is the tick of the clock measuring the life of the universe? Or how many times does the photon cycle in propagating in one second? Even if the “repetition periods are huge” we still want to inquire into what their meaning is.

__________________
L. J. Thaden

(1) Well it can't "terminate", though it can repeat. Since it is reversible, if it is "alive" in the direction that gets it to step n, it is "alive" in the direction that keeps going beyond step n. So it doesn't terminate. But it can "close", by revisiting a pair of successive steps that it has hit before. Then it necessarily goes around in a cycle, because it depends only on what happened on the previous 2 steps.

You can easily get it to repeat from a small initial condition, especially one with lots of divisors to allow subcycles. This follows from the "class 2 behavior in systems of limited size" argument, with the only wrinkle being that now one has two time steps rather than one that have to be the same, to have the same future. E.g. with a grid only 6 cells wide and initial condition

{0,0,0,0,1,1}
{1,0,1,0,0,1}

- for the previous step and "start" step, you get a cycle with period 24 steps. You can probably find special initials that close as fast as divisor related subcycles allow, if you search for and use the best (few) of the 2^12 initial conditions.

But if you e.g. take a random initial condition 137 cells wide - prime, so there aren't any subcycles to hit randomly - then you have something like 2^274 possible states. You can check for a cycle by scanning for two successive lines that have occurred before. From a random initial, I get none out to 100,000 steps. A million steps runs me out of memory without finding a repetition.

On (2), you can have a trillion cycles within the Planck time and it won't make any appreciable difference, unless the system is limited in width, or you specifically engineer a special initial that cycles. The combinatorial explosion is exponential in the system size. And typically when we are talking about second law processes we are talking about mole numbers of elements or something like it. Do whatever you like on the time side and you won't get within spitting distance... You are only going to see this sort of system "close" for special initial conditions or very limited system sizes.

There are simply vastly more possible arrangements than there are elements - that is the underlying driver. In realistic times, you are only going to visit a tiny subset of those possible arrangements. Instantiated reality is measure zero in overall possibility space, so you can be on transients "forever" - that is the moral. The question is therefore what typical transients look like, not what infinite time behavior looks like. (As Wolfram is fond of pointing out, the universe to date is a transient; ergo dynamics matter.)

I hope this helps.

Thanks for the distinction between terminate and repeat.

I believe the NKS book stated that the illustration on page 442-3 for 122R was 100 cells wide. Perhaps if one wrote the steps to an indexed file and recorded when the record was updated rather than created, a scan of the file would show the repeat. This would not involve memory limitations, only disk space ones.

From this you can probably tell that I haven’t given up on the quest to explore what “infinite” time behavior looks like. Maybe with random initials I’ll just get lucky on the 122R loops.

I’m definitely following the dialectic course here: one foot in the transients; the other in the persistent structures. If one day there is formalism for NKS, it will because of insights into all of the phenomena. Leave no stone unturned.

__________________
L. J. Thaden