An Analysis of Growth Rates in One-Dimensional Cellular Automata

Overview

One-dimensional cellular automata have been studied by looking at morphisms and properties of growth; however, no proof or demonstration has been made to explain these conjectured patterns and growth rates. The purpose of my experiment was thus to demonstrate logically why some of the growth of cellular automata occur the way they do. Specifically, I was interested in rule 2230's "power of 2" growth, where row widths alternated between increasing by 2 and not changing (increasing by 0) in powers of two. Using Java, I was able to program the cellular automaton in question -- rule 2230 -- giving the pictographic representation of the rule. By looking at the individual cases within the rule, I conjectured and then proved that the graph could be left justified by making a slight adjustment to the rule. This then allowed me to show the transition between columns, which gave way to the pattern of growth. This leftward justification only depended on 2 cases, so the same proof applies to 2^14 = 16384 rules. A possible application of this project is to find an automaton whose growth rate can be proved and apply the proof to a two-dimensional automaton, such as Conway's Game of Life, that can be mapped onto the one-dimensional automaton.

Competition history

• ISEF 2019 Mathematics · Entry MATH029

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.