[Emulating Elementary Rule 110 Behavior] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Emulating Elementary Rule 110 Behavior
(Click here to view the original thread with full colors/images)
Posted by: Lawrence J. Thaden
Each of the following 243 three color rule numbers exactly reproduce elementary two color rule number 110 behavior.
Every group of three rule numbers is 243 rules distant from the next group of three.
Within each group the rule numbers are 9 rule numbers apart.
Adding And[(-1 -p), (-1 -q), r] modulo 3 to each rule within a group gives the next rule number.
Adding And[(-1 -p), (q + 1), r] modulo 3 to the first rule within a group gives the first rule number of the next group.
Rulenumbers = (FoldList[Plus, #, Table[9, {2}]]&/@FoldList[Plus, 3188241986853, Table[243, {80}]]);
This shows the distribution of the rule numbers: ListPlot[Flatten[rulenumbers]];
This generates a table of the graphs. It uses Richard Philips NiceCaptionedRaster code.
graphs = Table[NiceCaptionedRaster[CellularAutomaton[{rulenumbers[[i, j]], 3, {{-1}, {0}, {1}}}, {{1}, 0}, 128], 5, rulenumbers [[i, j]], "PixelsPerCell"->1], {i, 81},{j, 3}];
This displays the graphs in 81 rows, three graphs to a row: Show[GraphicsArray[graphs]];
Finding these “gems” clustered like this reminds me of how diamonds are found clustered in a geological pipe.
Posted by: Lawrence J. Thaden
I had thought that there were only 243 three color rules emulating ECA rule 110. Moreover, I had thought that the first three color rule to emulate ECA rule 110 was rule 3188241986853.
But when I started looking from the beginning of three color rules, I found that the first three color rule that emulates ECA rule 110 is rule 590601. The last three color rule is 7625593666371.
How many rules are there in between? I do not know, but it is well over 43 million. In fact I checked out rules ranging from 590601 through rule 282425717865 and found 43046721 rules that emulate ECA rule 110.
And this did not even reach to rule 3188241986853, the one originally posted.
Here is the code to generate the 43 million rules:
FoldList[Plus, #, Table[3^2, {3^1 - 1}]]&/@
FoldList[Plus, #, Table[3^5, {3^4 - 1}]]&/@
FoldList[Plus, #, Table[3^11, {3^1 - 1}]]&/@
FoldList[Plus, #, Table[3^14, {3^9 - 1}]]&/@
FoldList[Plus, 590601, Table[3^23, {3^1 - 1}]]
Posted by: Lawrence J. Thaden
What the FoldList syntax in the previous post implies is this:
There is a pattern as to where ECA rule 110 behavior emulation is allowed within three space.
It can’t just be found anywhere you please.
This is analogous to Neil Bohr’s discovery that electrons orbit the nucleus of the atom in an orderly arrangement.
One way to look at the pattern is to focus on the gaps between where ECA rule 110 behavior emulation is allowed in three space.
In terms of number of rules the pattern of gaps can be stated this way:
In order of frequency of occurrence gap sizes are 9, 225, 157689, and 4409217.
Starting with rule number 590601 the gaps run in series as {9, 9, 225}.
There are 81 of these before a different gap size occurs. Namely, 157689.
This pattern then repeats itself once.
Then there are 81 occurrences of {9, 9, 225} followed, this time, by a gap of 4409217 instead of the gap of 157689.
In all there are 118098 gaps of size 157689 and 59048 gaps of size 4409217.
But this only takes us out to the 43046720th gap. More than likely the pattern keeps repeating until the end of three space. Or perhaps there is one more, larger gap.
Rather than continue documenting these gaps throughout the remainder of three space, I plan on testing the other rules from their first emulated occurrences in three space to see if this pattern is common to all ECA emulation or not.
Posted by: Lawrence J. Thaden
It appears that the pattern of gaps referred to is a common behavior for ECA emulation.
Each first occurrence of a three space ECA emulator rule number is the starting point for this pattern.
The starting points are unique, but the pattern is common.
I have selected the 110 unique ECA rule numbers and tested out the pattern on the first 77 of them so far.
The first of the attached figures shows the distribution in two space of these 110 ECA rule numbers.
The second shows the first occurrence of the three space emulators of the first 77 ECA rule numbers.
This is as far as I have gotten in checking the pattern out.
But even though the second figure is incomplete, it appears that it will have four groups of four subgroups.
Here are the numbers of rules by subgroup in each set of four groups found so far:
1. {4, 6, 5, 8}
2. {8, 8, 10, 8}
3. {6, 8, _, _}
4. {_, _, _, _}
The third figure shows the pattern.
As stated in the previous post:
Each group of three has a gap of 4409217 rule numbers before the next group of three.
Within each group of three there is a gap of 157689 rule numbers separating each of the three subgroups.
Each subgroup consists of 81 sets of {9, 9, 225} gaps.
Although not yet tested over entire three space for any one of the ECA emulators, it appears that this pattern repeats itself throughout three space for each of the 110 unique ECA emulators.
I have not attempted to locate the first occurrences of all ECA emulators in three space. Only those that are unique. That is, those not having multiple rule numbers with the same behavior.
When I have finished identifying the first occurrences in three space of the remaining 33 emulators of unique ECA rule numbers, I will post a complete list of them.
Edited Addition:
Now that all 110 first instances of the unique ECA emulators have been identified, here are all the numbers of rules by subgroup in each set of four groups:
1. {4, 6, 5, 8}
2. {8, 8, 10, 8}
3. {6, 8, 6, 9}
4. {5, 4, 9, 6}
See the middle figure in the attached graph which has been updated.
Posted by: Lawrence J. Thaden
The attached graph is a table of pairs of rule numbers.
The top number in each pair is one of the 110 unique ECA rule numbers.
The bottom number is the first instance of a three space rule number which emulates the behavior of the ECA rule on the top.
Each of the three space rule numbers is the first of millions that has behavior emulating the corresponding ECA rule.
All of these millions of rule numbers have the same distribution pattern in three space. (See the previous post.)
I have verified the pattern for all 110 emulators.
However, I have not verified that it repeats throughout all of three space for each of the emulators.
But for the first unique ECA, rule 7, I have verified that the pattern repeats 6561 times. And this extends from rule 31 through rule 94138769641.
Posted by: Lawrence J. Thaden
Attached is a graph plotting the pairs of ECA rule numbers and their three space emulators that were listed in the table in the previous post.
Posted by: Lawrence J. Thaden
Attached is a table listing 81 pairs of three space rule numbers that are emulators of ECA 110.
They mark the first and last rule numbers of sets of 14348907 emulators of ECA 110. The top number of each pair is the first rule number of the set and the bottom is the last.
After each pair there is a gap of 4409217 rule numbers before the next pair begins.
The 14348907 emulators in each set span 94138769610 rule numbers. This represents 6561 replications of the pattern set forth in a previous post.
All of these rule numbers have been verified as emulators of ECA 110.
In fact, that there are no rule numbers before the first number in the table (590601) and no rule numbers after the last number (7625593666371) has also been verified.
However, the rule numbers between the start and end of each set of 14348907 have not been verified.
If they all can be verified, the total number of three space rule numbers emulating ECA 110 will be established as 1162261467.
But this is not to say that there are not others that were overlooked using this search procedure.
To generate anyone of the sets of 14348907 rule numbers emulating ECA 110, assign the first number of a pair to the symbol startwith using the following code:
rnset = Flatten[(FoldList[Plus, #, Table[3^2, {3^1 - 1}]] &/@
FoldList[Plus, #, Table[3^5, {3^4 - 1}]] &/@
FoldList[Plus, #, Table[3^11, {3^1 - 1}]] &/@
FoldList[Plus, startwith, Table[3^14, {3^9 - 1}]])];
You can then verify for yourself that these three space rule numbers actually emulate ECA 110 behavior.
Here is the code that I have been using:
If[(CellularAutomaton[{#, 3, {{-1}, {0}, {1}}}, {{1}, 0}, 128] != searchforca),
Do[Print[#]; Abort[],{1}]] & /@ Take[rnset, {from, to}];
I assign a beginning index number and ending index number to the symbols from and to in the code:
Take[rnset, {from, to}];
This breaks up the set of 14348907 rule numbers into manageable sections.
The symbol searchforca is assigned the result of:
CellularAutomaton[{110, 2, {{-1}, {0}, {1}}}, {{1}, 0}, 128];
The Abort command executes only if verification fails. That is, if ever there is found a rule number in the range that does not emulate ECA 110 behavior.
Forum Sponsored by Wolfram Research
© 2004-2009 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