This project seeks to explore a phenomenon first observed by Stephen Wolfram in a Cellular Automata with a characteristic where when given a row of n - 1 gray cells and 1 black cell as an initial condition, it would eventually evolve into an infinite amount of generations of 2 n gray cells (halting), doubling its width . In particular, this article deals with range 1, 3 color Cellular Automata, which still yields vast amounts of interesting and complex results . To do this, the article first eliminates the possibility of two color doubling Cellular Automata by a proof by contradiction and later enumerates through all 199 distinct equivalence classes of such 3 color "doubling" rules for some n (beginning width) and t (number of generations) . The article then goes on to examines the relationships between the halting times and value of n for those 199 equivalence classes, classifying them into groups and diving into the irregular ones for patterns . Additionally, the article finds and analyzes the rules shared by the CA' s, which in turn branches off to finding cellular automata that seem to double for certain n but fail at others . Finally, it also offers a proof of doubling for one of the equivalence classes and offers possible proofs for other equivalence classes .
Introduction
Introduction
What are Cellular Automata? Cellular Automata are formally defined as “mathematical models for complex natural systems containing large numbers of simple identical components with local interactions. They consist of a lattice of sites, each with a finite set of possible values. The value of the sites evolve synchronously in discrete time steps according to identical rules. The value of a particular site is determined by the previous values of a neighbourhood of sites around it.” - Stephen Wolfram. In simple terms, they are simple computational systems made up of discrete cells each representing a specific value/color. The values can be any integer in base n where n is the number of colors or possible values a cellular automata can use. Cellular Automata evolve through generations according to fixed local rules and despite their simplicity, they are known to produce highly complex, and even computationally irreducible behavior at times.
Although there are many types of Cellular Automata, we will be focusing on two and three color ones range 1, meaning that the cells can only in the next generation only depend on their nearest neighbors.
A two color (rule 30) and three color (rule 67543420) Cellular Automata followed by the rules that govern them looks something like this:
Although there are many types of Cellular Automata, we will be focusing on two and three color ones range 1, meaning that the cells can only in the next generation only depend on their nearest neighbors.
A two color (rule 30) and three color (rule 67543420) Cellular Automata followed by the rules that govern them looks something like this:
GraphicsRow[{Labeled[ArrayPlot[CellularAutomaton[{30,2,1},{{1},0},42]],Text[Style["rule 30 (2 color)",Italic]]],Labeled[RulePlot[CellularAutomaton[{30,2,1}]],Text[Style["rules",Italic]]]}]GraphicsRow[{Labeled[ArrayPlot[CellularAutomaton[{67543420,3,1},{{1,2,2,0,1,1},0},42]],Text[Style["rule 67420 (3 color)",Italic]]],Labeled[RulePlot[CellularAutomaton[{67543420,3,1}]],Text[Style["rules",Italic]]]}]
Out[]=
Out[]=
As one might observe, the 2 color one contains 2^3 rules to “fill in” with 2^8 possible options and the 3 color one contains 3^3 rules to “fill in” with 3^27 possible options. Now what do the three color doubling Cellular Automata look like? Well, one of the simpler doubling ones look like this:
In[]:=
GraphicsRow[{formatMyDiagramCA[{5407067979,3,1},{Join[Table[1,20],{2}],0},123,"Rule 5407067979"],formatMyRulesCA[{5407067979,3,1},"5407067979 rules"]}]
As seen in the diagram, when this rule is given an input of a row of n-1 gray cells and 1 black cell (n cells in total), it halts at an infinite amount of generations of 2n gray cells. But by going through more of the equivalence classes, some more seemingly random complicated patterns that lead to doubling show up.
GraphicsRow[formatMyDiagramCA[{#,3},{Join[Table[1,20],{2}],0},243,"Rule 4510289298924"]&/@{4510289298924,6424448193765,5793483343212}]
Note how certain Cellular Automata can take a lot longer to halt than others. The rule of the right has not yet halted while the other two halted pretty early on in the generations.
Enumerating Through all 199 Equivalence Classes
Enumerating Through all 199 Equivalence Classes
This section seeks to search for any “bugs”/breaks in the seemingly doubling cellular automata as the original set was found by searching through all three color rules (3^27) for a somewhat small value of n. To do this, the equivalence classes are enumerated through for large values of n and t.
Before attempting to prove something, it is a good habit to just check a bunch of cases and make sure that it is somewhat true. In order to check all the 199 equivalence classes of the doubling Cellular Automata, I downloaded them from the Wolfram Data Repository.
Enumeration for n ∈ {n ∣ n ∈ ℤ , 1 ≤ n ≤ 81}
Enumeration for n ∈ {n ∣ n ∈ ℤ , 1 ≤ n ≤ 81}
In[]:=
threeColorDoublingCA=ResourceData["Three-Color Cellular Automaton Rules that Double Their Input"]
To check for early on bugs through enumeration, a code was run with n ∈{n ∣ n ∈ ℤ , 1 ≤ n ≤ 81} and t = 500 (a bit smaller than the maximum capacity of my kernel). Due to the long output, it is not shown, but no inconsistencies were found within the 199, leading us to the reasonable assumption that they do in fact double.
Riffle[threeColorDoublingCA,Transpose[Table[ArrayPlot[CellularAutomaton[{rule,3},{Append[Table[1,n],2],0},500]],{n,81},{rule,threeColorDoublingCA}]]]
Despite the long output, below are examples of all the cellular automata at n = 27 run for 300 generations .
In[]:=
GraphicsGrid[Partition[Table[formatMyDiagramCA[{rule,3,1},{Join[Table[1,20],{2}],0},200,ToString[rule]],{rule,threeColorDoublingCA}],27]]
Out[]=
Testing Through Taking Samples at Large Sizes
Testing Through Taking Samples at Large Sizes
A second method of testing whether these seemingly doubling Cellular Automata will break, is by taking small samples at large sizes and checking if the cells in those rows are all grey, still evolving into a halting state, or broken. This task is completed by defining a function and repeatedly using over the Cellular Automata.
In[]:=
takeSliver[rule_,colorNum_,init_,beginning_,end_]:=ArrayPlot[CellularAutomaton[{rule,colorNum},init,end][[beginning;;end]],ColorRules->MapThread[#1->#2&,{Reverse[Range[0,colorNum-1]],Table[GrayLevel[i],{i,0,1,1/(colorNum-1)}]}]]
In[]:=
Table[threeColorDoublingCA->(takeSliver[#,3,{Append[Table[1,2500],2],0},30000,30100]&/@threeColorDoublingCA)[[i]],{i,199}]
Table[threeColorDoublingCA->(takeSliver[#,3,{Append[Table[1,2000],2],0},25000,30100]&/@threeColorDoublingCA)[[i]],{i,199}]
For the majority of the doubling Cellular Automata, the samples are all rows of 2n gray cells, but occasionally, one of them seems to still be growing. This makes sense as a lot of the Cellular Automata can take seemingly exponentially longer when compared to some of the simpler ones; showing the diversity in structures and behaviors within these certain cellular automata. However, they do all still seem to halt, confirming our belief that for n ∈{n ∣ n ∈ ℤ , 1 ≤ n }, t < ∞.
Characterizing Equivalence Classes Into Groups
Characterizing Equivalence Classes Into Groups
This section seek to analyze through all the 199 equivalence classes of the doubling cellular automata in order to characterize them into groups for easier analysis on their structures.
Halt Times
Halt Times
The halting time of a Cellular Automata in the context of these doubling ones is the number of generations between t = 1 and t = k where k is the g=h1379fjnoqrvekd w12req. Considering this definition and the complex patterns of the three color Cellular Automata, which make them very difficult to classify based off patterns, we take a step back and ask “how can we classify the doubling cellular automata based off their halting times?” A wise first step would be to retrieve the graphs of their halting time.
At first, it seems that the the halting time for all the Cellular Automata grow linearly as n takes step of 1, however, by checking each one, a few major classes arise. Most evidently, one, the class rules which seem to grow in a quadratic pattern, two, the linear ones that grow in somewhat of a wandering pattern (deemed “fuzzy”), three, the normal linear ones, and finally, the singular class rule which grows similarly to the Mersenne numbers.
Quadratic Cellular Automata Group
Quadratic Cellular Automata Group
To better visualize the behavior of these automata, we organize the halting times into their respective groups and plot them using ListLinePlot. In each plot, the x-axis represents the initial width n, and the y-axis represents the corresponding halting time. Note that the plots of 144892613592 and 5793483343212 look very similar, with one just shifted up a bit. The same is true with the plots of 6863658437061 and 6863916715200, except they are way smoother and almost in the shape of a perfect parabola.
Due to the rarity of the occurrences of the abnormal class rules and how many linear Cellular Automata there are, these rules might seem to be errors or some possible mistake, but by looking closely at the Cellular Automata generations, it actually makes perfect sense . By zooming into model of the generations of rule 6863658437061 and 6863916715200 , one finds that for every increase of 1 in n, there is a new triangle with side length 4 more than the previous.
Despite the seemingly constant pattern, it is important to recognize that this is only a conjecture proven off of patterns as this essay does not feature a proof that these triangles will always happen and never break.
Random Walk Cellular Automata Group
Random Walk Cellular Automata Group
The chaotic and unpredictable patterns of these cellular automata make it very hard to know which whether these will always double or not, which is very similar to a random walk guided towards some destination. However, a very interesting observation can be made about what happens in rule 451028298924 which somewhat happens in the other rules. We can see that despite the complicated patterns, it can be broken down into two sections with the dividing line being when the checkerboard pattern stops. It is also important to note that because there are many regions in this rule which are only governed by two colors. So by removing all rules that include the color white, we get 8 rules. By adding the outputs of the rules and converting to base 10, we find that they both emulate the two color rule number 122, just each with different initial conditions.
Cellular Automata Group Similar to Mersenne Numbers
Cellular Automata Group Similar to Mersenne Numbers
For the final category of the three color doubling cellular automata, it only contains one rule, 837428508144. Despite it seeming very unneeding of analysis, through the graph and model of the generations, an interesting pattern where the halting time increases very slowly despite a growing n until some point where it jumps to some other number and increases very slowly there for a certain amount of time in some patterns closely related to the powers of 2. To confirm our suspicion, we plot the graph of the halting times of this rule.
note: the plot is scaled but the original plot would should the lines with slope 1
To begin, we break the list of halting times into their periods:
We then notice that we an represent each term within each period k as a sum of terms:
Although this seems to be a dead end with no pattern, by breaking each constant into powers of 2 subtracted by consecutive odd numbers, both of which are recognizable parts, we can convert a list with seemingly no pattern into one that is easy to generalize.
Note: this number line may help visualize the growth pattern for rule 837428508144
Decoding the Common Rules Governing the Equivalence Classes
Decoding the Common Rules Governing the Equivalence Classes
This section aims to explore how the rules shared by all the equivalence classes operate and why they are necessary. It also utilizes these facts to prove that a two color doubling cellular automata doesn’t exist.
Analyzing the Shared Rules Within the Three Color Doubling Cellular Automata
Analyzing the Shared Rules Within the Three Color Doubling Cellular Automata
Below is a column of data showing the frequency with which each three-color rule appears across all 199 equivalence classes. This means that if a rule appears 199 times is present in every class, it suggests that it may play a fundamental role in causing the automata to halt or double. By manually inspecting the data, we find that eight such rules appear in all of the 199 classes, all of which are highlighted and present in the rule plot.
1. ({0,0,0}0)199
2. ({0,0,1}0)199
3. ({0,0,2}0)199
4. ({0,1,1}1)199
5. ({1,0,0}0)199
6. ({1,1,0}1)199
7. ({1,1,1}1)199
8. ({2,0,0}1)199
1. ({0,0,0}0)199
2. ({0,0,1}0)199
3. ({0,0,2}0)199
4. ({0,1,1}1)199
5. ({1,0,0}0)199
6. ({1,1,0}1)199
7. ({1,1,1}1)199
8. ({2,0,0}1)199
As for rule 4 and rule 6, they have reasons of existing similar to that of rule 2 and rule 5. Except this time, the rule helps to maintain the width of the halted state from shrinking. It does this by keeping two posts of gray cells on the both sides, as if it they were to become white, the width would shrink from 2n to 2n-1 or 2n-2 (depending on whether you remove both of the rules or just one). Therefore, rules 4 and 6 are necessary to all the three color doubling cellular automata.
In addition to needing to preserve the halted generations from shrinking or growing, they are also required to maintain their structure. Because the previous rules have already prevented the interactions of any of the white cells with gray cells, this rule only has to deal with the gray cells near the inside of the structure (ones with “depth” one with respect to the sides). it does this by making sure all the gray cells from one generation turn into grey cells in the next.
As for rule 3 and 8, at first, they seem fairly ambiguous. Why do these exist when they don’t seem to be helping the cellular automata halt? Well, a good way to begin tackling this is to look at some example cellular automata first. The examples have been randomly chosen are to be rules 1547713862928, 4541584617225.
Observe that the cellular automata all grow to the right, and never to the left. The fact that growing in both directions will not result in doubling is one that I have not proved yet. However, it most likely cause way too much chaos to clean up. As if the rules were to grow to both sides, it would need double the rules to go halt, versus just growing too one side where they can use the “other half” of the set of rule to diminish it. As a result, prevention of the cellular automata from growing to the left now becomes necessary, which in turn, makes rule 3 necessary too. Rule 3 accomplishes this task as whenever a black cell shows up on the left, the rule 3 inserts a white cell to block it from growing.
In contrast, rule 8 helps force the cellular automata grow from n to 2n, seemingly preventing it from ever halting before 2n. As whenever a black cell is generated on the right, it helps produce a gray cell which then stays put for a few generations until creating another black cell to push it to the right. The fact that this somehow always stops at the width 2n hasn’t been proven yet for all 199, but this rule does seem to be necessary, serving as a universal growth factor.
Proving the impossibility of a 2 color doubling cellular automata with range 1
Proving the impossibility of a 2 color doubling cellular automata with range 1
If we focus back onto the rules 2, 4, 6, and 5, which all serve purposes of maintaining the halting status of a cellular automaton, we can convert them into conditions for 2 color cellular automata :
Is it Possible to Prove That all 199 Equivalence Classes Double for all N?
Is it Possible to Prove That all 199 Equivalence Classes Double for all N?
This section seeks to prove doubling for one of simple linear cellular automata within the equivalence classes and then branch it off into thoughts about how a general proof may be made. It also begins to identify patterns (which a time constraint disallowed me to prove) which might lead to proofs or more discoveries.
Proving Doubling for a Linear Case
Proving Doubling for a Linear Case
The rule which we are aiming to prove is rule 5407067979, the cellular automata who’s time to reach a halting state happens to be the most minimal. Below is the model of the rules governing the cellular automaton as well as the models as n runs from 1 to 20 for 30 generations.
Initially, the pattern of this cellular automata seem to be very simple and easy to prove, however, as patterns get formulated, they seem to break for certain ones. However, through analyzing the patterns of rule 5407067979 as n grows yields the interesting observation that the patterns depend on what n is mod 3. This means, that by splitting this linearly growing rule into three cases, we can prove that it doubles for each and in doing so, show that it doubles for all.
Case one: n ≡ 1 mod 3
Case one: n ≡ 1 mod 3
We begin by letting n = 3k+1 where k ∈ ℕ₀. Then our first row is
note: labeling of every cell have been dropped due to impracticality
Case two: n ≡ 2 mod 3
Case two: n ≡ 2 mod 3
We begin by letting n be equal to 3k+2 = k ∈ ℕ₀. Then our first row is
Now, we perform the identical recursion which was used in the 1mod3 case, but due to the first term in the this period being {2, 0, 0}, we get the following results for the row on top of the first set of stacked white cells:
Case two: n ≡ 0 mod 3
Case two: n ≡ 0 mod 3
We begin by letting n = 3 k where k ∈ ℕ₀ . Then our first row is
Similarly to the previous two cases, the patterns have a period three, but here, it is 0mod 3. As a result, our target row ends in nothing and is just a repeated pattern as shown below
Conclusion
Conclusion
Future Directions
Future Directions
This section aims to provide future directions for any one who might be interested in exploring this same concept.
◼
The obvious path forward would either be
◼
Come up with the general proof that all the 199 equivalence classes double
◼
Go through all 199 equivalence classes and individually prove that they double
◼
Analyzing the purpose of all the rules or determining that they are random
◼
The rules shared among the groups may not be as random as they seem
◼
Exploring the cellular automata which seem to double but break for certain values of n
◼
Do they harbor any significance?
◼
What causes one to break and the other to survive? or is it somewhat random?
◼
Performing similar analyzes or new ones on doubling cellular automata which feature more than 3 colors or a range larger than 1
◼
The Random Walk Cellular Automata rule 4510289298924 seems to almost have an artificially created way of producing 2n. This somewhat relates to Stephen Wolfram’s idea of cellular automata having a purpose or function and vaguely connects to his idea about biological evolution and how some seem to have evolved to be live longer or neat. Does it say anything more about these ideas?
References
References
◼
Berto, F. and Tagliabue, J. (2017). Cellular Automata. Fall 2017 ed. [online] Stanford
Encyclopedia of Philosophy. Available at: https://plato.stanford.edu/entries/cellular-automata/.
Encyclopedia of Philosophy. Available at: https://plato.stanford.edu/entries/cellular-automata/.
◼
Stephen Wolfram (2024), “Why Does Biological Evolution Work? A Minimal Model for Biological Evolution and Other Adaptive Processes,” Stephen Wolfram Writings.https://writings.stephenwolfram.com/2024/05/why-does-biological-evolution-work-a-minimal-model-for-biological-evolution-and-other-adaptive-processes/
◼
Wolfram Research, “Three-Color Cellular Automaton Rules that Double Their Input” from the
Wolfram Data Repository (2017). https://doi.org/10.24097/wolfram.07085.data
Wolfram Data Repository (2017). https://doi.org/10.24097/wolfram.07085.data
◼
Wolfram, S. (1984). Universality and complexity in cellular automata. Physica D: Nonlinear
Phenomena, 10(1-2), pp.1–35. doi:https://doi.org/10.1016/0167-2789(84)90245-8
Phenomena, 10(1-2), pp.1–35. doi:https://doi.org/10.1016/0167-2789(84)90245-8
◼
Wolfram, S. (2002). A New Kind of Science. [online] Wolfram Media, Inc. Available at:
https://www.wolframscience.com/nks/p832--%20intelligence-in-the-universe/ [Accessed 10 Jul. 2025].
https://www.wolframscience.com/nks/p832--%20intelligence-in-the-universe/ [Accessed 10 Jul. 2025].
Acknowledgements
Acknowledgements
I would like to thank my mentor, Henry Gustafson, for his incredible support and guidance throughout this project. His insights and patience has helped me with debugging tricky code and made writing this essay possible and fun. I also want to thank Stephen Wolfram, whose discovery of the doubling cellular automata provided the foundation for my work, opening up a rich space for discovery and a fun two weeks of finding and proving new behaviors. Many thanks as well to Shenghui Yang for his insightful thoughts on my project. Finally, I' d like to thank the entire Wolfram Summer Research Program team for creating a program suited for researching alongside smart people.
Also, thanks to Girish Prasad for helping me with a proof.
Also, thanks to Girish Prasad for helping me with a proof.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Analyzing emergent patterns within doubling cellular automata
by Alex Archerman
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3503093
by Alex Archerman
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3503093