Registered: Feb 2004
Posts: 172

Has anyone studied the properties of sorted elementary 1D CA output samples?

Example data (viewed as binary numbers):

000010000 = 1
000000100 = 1
000100101 = 100101
011100010 = 11100010
000000000 = 0

Sorted:
1,1,100101,11100010


It would be interested to see rule 30 sorted after being interpreted numerically (first by trimming left and right zeros). Obviously in the above experiment all the numbers would be odd.

I would appreciate some links to studies along these lines of experimentation if anyone has seen such madness (particularly interested in the elem. 256 CAs).

Some of the elementary CAs would increase in magnitude at every iteration yet I still think it worth the time to visualize the sort to see what happens on the "inside" of the numbers.

Thanks,

__________________
P h i l i p . R . D u t t o n

Last edited by Philip Ronald Dutton on 07-19-2007 at 09:57 PM

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

We can readily investigate the question by writing our own function based on the CellularAutomaton function, like this.


SortedCA[rl_, init_, steps_] := 
 Module[{rawdata = 
CellularAutomaton[rl, init, steps], trimmed},
  trimmed = Flatten[#] & /@ 
(Drop[Drop[Split[#], 1], -1] & /@ rawdata);
  IntegerDigits[Sort[FromDigits[#, 2] &
 /@ trimmed], 2]  ]


Then e.g. one can store the results in a variable, data -

data = SortedCA[30, {{1}, 0}, 20]

And we can ArrayPlot the result (note that the modern, 6.0 version of ArrayPlot happily accepts ragged lists - if you are using 5.1 you may need to PadRight with zeros etc) -

ArrayPlot[data]


Some preliminary comments looking at them - they are interesting.

The following show complex patterns from the simplest initial condition - rules 30, 45, 73, 75, 86, 89, 101, 110, 124, 135, 137, 149, 193.

The following are slow growers but potentially interesting - 169, 225.

The following show various sorts of nesting, occasionally intricate - 18, 22, 26, 60, 82, 90, 102, 105, 126, 129, 146, 150, 153, 154, 161, 165, 167, 181, 182, 195, 210, 218.

The following show regular patterns but structured enough that they might do something non-trivial with more complex initial conditions - 54, 57, 62, 70, 78, 92, 94, 99, 109, 118, 131, 145, 150, 158, 214.

Of course, one can also generalize the idea beyond the ECAs.

My method of stripping the zeros above is kind of hacky and might give trouble in some cases. Some patterns will also just die out, "coughing" when you try to convert an empty list to a number and back, and the like. So the code could be cleaned up, made more robust and general.

I hope this helps.

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 172

Jason would you mind putting a few pictures up? I can't run mathematica.

Thanks!

__________________
P h i l i p . R . D u t t o n

Last edited by Philip Ronald Dutton on 07-19-2007 at 10:27 PM

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 172

Perhaps the following might need to be posted in "ways of thinking" but it is here anyway. ( Actually, I just did this. Now there is a new thread in the ways of thinking category )

This thread's discussion has made me more fond of the odd numbers. If you view the CA output as the number line then you do not need a notion of a zero position. I say this because, using my trim method above, all interpretations of the binary numbers will be odd numbers.

For a moment, consider the number of 2 which is 10 in binary. On the CA output, the 10 will always have an infinite number of "zero" cells on both sides simply because the grid width is arbitrarily undefined in CA.


If there is an arbitrary width in the CA then who will dare say where the zero position lies while trying to interpret output as binary numbers.

There seems to be something to think about regarding this zero object. I guess that mapping the traditional number line to CA changes the properties of the zero object. On the traditional number line, the zero is definitely forced to take position. With CA mapped number line, the zero is not positional. Also, the notion of "even number" is completely distorted- perhaps destroyed- in this view.

So, in one fell swoop, the zero position is gone, the even numbers are gone, but why should that matter? Why do we expect the number line properties to persist when mapping or partial mapping to another system?

__________________
P h i l i p . R . D u t t o n

Last edited by Philip Ronald Dutton on 07-20-2007 at 12:08 AM

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 172

This discussion of sorting output has obvious implications for the nature of the CA algorithm. What would it mean if there was a CA that did not produce a particular known mathematical sequence of numbers (as you sit and watch each step) but which did eventually produce all the numbers of the sequence? In other words, why do we demand that CA's or other simple programs produce our beloved sequences in direct time-step with the sequence itself (indeed this is a rhetorical question).

Anyway, in terms of the above statement, sorted output will need to be investigated to some degree.

__________________
P h i l i p . R . D u t t o n

Last edited by Philip Ronald Dutton on 07-19-2007 at 10:55 PM

Report this post to a moderator | IP: Logged