[sorted 1D CA output] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


sorted 1D CA output

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


Posted by: Philip Ronald Dutton

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,


Posted by: Jason Cawley

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.


Posted by: Philip Ronald Dutton

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

Thanks!




Posted by: Philip Ronald Dutton

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?






Posted by: Philip Ronald Dutton

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.




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