[periodic rule] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1

periodic rule
(Click here to view the original thread with full colors/images)

Posted by: Jack Hsu

hi,

Does periodic (class 2) must contain a row that repeats it self (at least once)?
What are the criterias for periodic rule?
I know that rule 73 is periodic. What makes it periodic?
Does a periodic rule has to be periodc for every initial step?

thank u a lot

Jackee

Posted by: Jason Cawley

A class 2 rule rapidly becomes periodic from typical random initial conditions. Typical class 2s are much simpler than rule 73, which is a borderline case. It may in fact be a class 4 rule, and might be universal.

Class 2 behavior is forced in all rules if the width of the initial array is small enough. The reason is the total number of possible states of the system is limited to colors ^ width, and the sequence is deterministic. So if the same state is hit at any time, the rule must hit the same following state, and so cycle. If the number of steps is greater than the number of possible states, this must happen at some point in that number of steps - you can't fit n+1 objects into n holes. This subject is discussed in chapter 6 of the NKS book, in the section titled "systems of limited size and class 2 behavior" see 255.

For modest numbers of steps, though, this issue rapidly disappears as the width rises above a tiny level, since the total number of available states rises exponentially with increasing width. A 2-color pattern 150 cells wide has more possible states than there are particles in the universe - you aren't going to run out in any practical number of steps. But when the pattern is narrow, one readily hits cycles, sooner than this limit. Because many patterns are not reachable by a given rule, the width has divisors that make subcycles possible, etc.

Rule 73 is an interesting case. It often quickly goes to a pattern that repeats every 2 or 3 steps. But it also divides into regions separated by vertical black stripes (1s), with those simple repetition patterns in many of them - but not in all. Sometimes these more elaborate patterns are "transients", and die out to one of the small regular periodic patterns the rule supports. But occasionally, a wider and more elaborate pattern, 20 wide or so, appears between vertical bars. The pattern within frequently does repeat, but the period can be considerably longer.

The overall pattern can only be said to repeat exactly, when the exact same line occurs at step t and at step t + x. If there are 10 different "pipes", that requires all of them to hit "in phase". Which might make it look a bit longer when you have one large cycle, because it may need to "go around" several times e.g. before you repeat a whole step. You can have one cycle in a more complex "pipe" with a period of 30, and it may require 4 of those cycles to hit "in phase" with those cycling with period 2 or 3, for example.

So what is the reasoning supporting the generalization, rule 73 typically gives periodic behavior, despite the occasionally more complicated sections? First, from typical random initials you are going to get dividers. Those arise whenever you have 2 1s after each other with zeros around them. They will break the pattern up into finite regions. The smallest of these will cycle rapidly. The wider ones often will, because that is the most common behavior of the rule. The occasional wider ones that don't cycle rapidly, still face the "systems of limited size" issue.

When instead one forces the initial condition to avoid the block dividers - no patterns with a run of an even number of 1s - rule 73 looks class 3. Wolfram speculates (on page 699 ) that this feature of rule 73 might be used to control information spread. Particle like local patterns on rule 73s usual periodic backgrounds might then be used to carry information. This might support a universality construction for rule 73, which would be a highly significant NKS result if found.

Here is a useful Mathematical helper function for these sorts of questions, findCycle. It expects CellularAutomaton data - a list of lists, which it looks for repeats within. It returns the cycle length in steps, the whole actual cycle, and the length of any transient before the cycle -

findCycle[x_List] :=
With[{a = Flatten@Position[Reverse[x], Last[x], {1}, 2, Heads -> False]},
If[Length[a] == 2,
With[{q = Rest@Take[x, -Reverse[a]]},
{Subtract @@ Reverse[a], q,
If[Length[#] == 0, 0, Length[x] - Part[#, 1, 1] + 1] &@
Position[Reverse@MapThread[SameQ,
{x, PadLeft[q, Length[x], q]}, 1], False, {1}, 1]}], {}]]

Then a sample use and output would be something like -

findCycle[CellularAutomaton[54, IntegerDigits[4568, 2, 10], 20]]

{4, {{1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{1, 1, 0, 1, 1, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 0, 0, 1, 0, 1, 0},
{0, 1, 1, 1, 0, 1, 1, 1, 1, 1}}, 5}

Then you can get things like sets of cycle lengths using findCycle[xxx][[1]], lengths of transients with findCycle[xxx][[3]], all the unique cyclic sequences in some data set by first mapping findCycle over a bunch of CA evolutions, asking for [[2]] of each and then taking a Union, etc.

I hope this is useful.

Posted by: Lawrence J. Thaden

Jason...

findCycle is very useful. Surely I speak for many in saying so.

But was it your intention to have the first step of the cycle in the last place of the second item in the list of what is returned, where the first item is cycle length and the third item is transient length?

Also, it would be nice to see some elegant code that compares cycles from two different CAs for equivalence, where equivalence is defined as having the same rows and columns although offset from each other with respect to row and column alignment.

To take this one step further, what if you were to come up with code that detected a cycle while the CA is running, not after the fact? It would seem more efficient than having to scan the data a second time. Wouldn’t you agree?

Posted by: Lawrence J. Thaden

Since Jason is not responding, I’m going to venture into an area reserved for the “code warriors” and suggest a correction to his findCycle routine. After all, to paraphrase Wolfram: If we don’t get it right, all who use it won’t get it right.

In findCycle the choice of Rest removes the first item in a list. Jason should have used Most which removes the last item in the list under consideration. Then to compensate for this correction, in finding the transient length, we subtract the length of the cycle (Length[q]) instead of adding 1.

Here is the corrected code:

correctedFindCycle[x_List] :=
With[{a = Flatten@Position[Reverse[x], Last[x], {1}, 2, Heads -> False]},
If[Length[a] == 2,
With[{q = Most@Take[x, -Reverse[a]]},
{Subtract @@ Reverse[a], q,
If[Length[#] == 0, 0, Length[x] - Part[#, 1, 1] - Length[q]] &@
Position[Reverse@MapThread[SameQ,
{x, PadLeft[q, Length[x], q]}, 1], False, {1}, 1]}], {}]]

test={{0,0,0,0,0},{1,1,1,1,1},{2,2,2,2,2},{3,3,3,3,3},{4,4,4,4,4},{5,5,5,5,5},{1,1,1,1,1}};

findCycle[test]
{5,{{2,2,2,2,2},{3,3,3,3,3},{4,4,4,4,4},{5,5,5,5,5},{1,1,1,1,1}},1}

correctedFindCycle[test]
{5,{{1,1,1,1,1},{2,2,2,2,2},{3,3,3,3,3},{4,4,4,4,4},{5,5,5,5,5}},1}

Posted by: Jesse Nochella

Well, one way to find cycles while you are running, provided you have a step function to work with is use something like NestWhileList, here's some code that returns it in the format expressed here:

cycleFind[f_, expr_] := With[{list = NestWhileList[f, expr, UnsameQ,
All]}, {Length@#[[2]], #[[2]], Length@#[[1]]} &@
Split[list, (#1~UnsameQ~list[[-1]] &)]]

CAcycleFind[rnum_, init_] := With[{
list = NestWhileList[First@CellularAutomaton[
rnum, #, 1, {-1,All}] &, init, UnsameQ, All]}, {Length@#[[2]], #[[2]],
Length@#[[1]]} &@Split[list, (#1~UnsameQ~list[[-1]] &)]]

Mathematica makes this pretty easy to do. There's more issues with cellular automata, such as the fact that step functions like the one I used do not incorporate backgrounds the same way over time as CellularAutomaton does. So if you want to find cycles inside growing rules as they evolve, there's more to do.

Posted by: Lawrence J. Thaden

Thanks Jesse. That will get me started.

Posted by: Jason Cawley

Sorry I was away from this thread for so long. Lawrence, you are right that the original doesn't look for the first instance of the cycle and so can return the middle term in any "phase". It just looks at the last line - if you are already on a cycle that line must appear somewhere above. Find the first place it does and count the difference in steps - that is your cycle length. Because it uses this procedure to get the cycle itself, it gives the resulting cycle with whatever "phase" the last line of the evolution happened to be, first.

Your replacement, on the other hand, doesn't appear to me to get the transient length consistently right. Look for example at

test2 = Table[RotateRight[Range[10],i], {i,1,20}]

Or at

test3 = CellularAutomaton[54,{1, 0, 0, 1, 0, 0, 0, 0, 0, 0},20]

The last gives a "transient" length of 16 with the "corrected" version, when the correct figure is 0 (the first step appears again within the evolution, at step 5 - ergo, there is no transient).

If you want the phase of the cycle to be correct, with the first element of the returned 2nd position, equal to the first step in the original, you could get the transient length first in a "with", and then use the original data to get the cycle itself in its "original" form aka phase, with (conceptually) -

Take[Drop[original, transientlength], cyclelength]

That is, start with the original, drop the transient steps from the begining, take the first cycle-length of steps. The whole function would thus become -

findCycle[x_List] :=
With[{a = Flatten@Position[Reverse[x], Last[x], {1}, 2, Heads -> False]},
If[Length[a] == 2,
With[{q = Rest@Take[x, -Reverse[a]]},
    With[{transientlength =
       If[Length[#] == 0, 0, Length[x] - Part[#, 1, 1] + 1] &@
Position[Reverse@MapThread[SameQ,
{x, PadLeft[q, Length[x], q]}, 1], False, {1}, 1]},
{Subtract @@ Reverse[a],
      Take[Drop[x, transientlength],
Subtract @@ Reverse[a]], transientlength}]], {}]]

Ugly because of all the With's, but gets the correct transient length (as the original did) and the correct cycle phase (as yours did).

Posted by: Jesse Nochella

period[{a___, x_, b___, x_, c___}] := {Length@{x, b, x}, {x, b, x}, Length@{a}}

Works. In less code than an equally functional explanation of what it does. Which probably means that it's fast, and effecient too.

Makes me smile.

Posted by: Jason Cawley

Very nice. A much more Mathematica way of doing it. But a minor correction - you want the cycle length to exclude the repeat, and the cycle likewise. So you just drop the second x -

period[{a___, x_, b___, x_, c___}] := {Length@{x, b}, {x, b}, Length@{a}}

The only other issue is what happens when there is no cycle. (Try period[Range[10]] e.g.) As this is, it returns the original symbolic form because the pattern is not matched. But that can be dealt with by using your version, moving the patterns over to the right hand side, and using the pattern function Switch.

period[lst_] :=
Switch[lst, {a___, x_, b___, x_, c___}, {Length@{x, b}, {x, b},
Length@{a}}, _, {} ]

That says, take any list. If it matches Jesse's pattern, then return the relevant bits from out of that pattern. If the first pattern does not match, it goes to the next. Which in this case is a single blank, which matches anything. In that case, return the next item in the Switch argument list - the empty list.

A much cleaner piece of code.

Posted by: Lawrence J. Thaden

Jason and Jesse...

It appears that the ugly findCycle is much faster than the more elegant period code.

Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings