CellularAutomatonData 1.00

documentation notebook

Charles Brummitt and Eric Rowland
https://ericrowland.github.io/packages.html

Introduction

CellularAutomatonData is a source of data on boundaries of one-dimensional cellular automata.
This introduction gets you started with a few features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.

To use CellularAutomatonData, first you will need to load the package by evaluating the following cell. (If you need help, see loading a package.)

<<CellularAutomatonData`

Querying the data

The primary symbol is CellularAutomatonData, which works like built-in Mathematica data symbols such as CountryData and ParticleData.
The first argument is a cellular automaton, specified as {rule,initial condition} to parallel CellularAutomaton.

For example, the following retrieves the growth rate of the 2-color rule number 30 depending on 3 cells, begun from a single black cell on a constant white background.
This automaton grows linearly at a rate of 2 cells per step:

CellularAutomatonData[{{30,2,1},{{1},0}},"GrowthRate"]

For example, the following retrieves the growth rate of the 2-color, radius 3/2 rule number 1273 begun from a single black cell on a constant white background.

CellularAutomatonData[{{1273,2,(3/2)},{{1},0}},"GrowthRate"]

Here is what this automaton looks like in the first 100 steps:

ArrayPlot[CellularAutomaton[{1273,2,(3/2)},{{1},0},100]]

These are all the properties available, although no automaton has values for all properties:

CellularAutomatonData["Properties"]

The boundary word of a cellular automaton is the difference sequence of its row lengths.
Here is the beginning of the difference sequence for rule 30 begun from a single black cell:

Differences[(Position[#1,1][[-1,1]]-Position[#1,1][[1,1]]&)/@CellularAutomaton[{30,2,1},{{1},0},30]]

The eventual period length is 1:

CellularAutomatonData[{{30,2,1},{{1},0}},"BoundaryWordPeriodLength"]

Some automata have boundary words that are not eventually periodic but that are described by fixed points of morphisms:

CellularAutomatonData[{{39780,2,(3/2)},{{1},0}},"BoundaryWordPeriodLength"]

CellularAutomatonData[{{39780,2,(3/2)},{{1},0}},"BoundaryWordMorphism"]
CellularAutomatonData[{{39780,2,(3/2)},{{1},0}},"BoundaryWordCoding"]

FixedPoint[StringReplace[#1,{"A"->"ABC","B"->"DAB","C"->"CECE","D"->"CECD","E"->"CECE"}]&,"A",3]
Join@@(Characters[%]/. {"A"->{2},"B"->{2},"C"->{1},"D"->{0},"E"->{-1}})

Differences[(Position[#1,1][[-1,1]]-Position[#1,1][[1,1]]&)/@CellularAutomaton[{39780,2,(3/2)},{{1},0},36]]=={2,2,1,0,2,2,1,-1,1,-1,1,-1,1,0,2,2,1,0,2,2,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1}

Still other cellular automata have boundaries that do not exhibit reducibility.
For these automata there is data on best-fit curves to the sequence of row lengths.

Grid[CellularAutomatonData[{{7419,2,(3/2)},{{1},0}},"BestFits"],Dividers->All]

Accessing the raw data

If you’d rather operate on the raw data instead of using CellularAutomatonData, you can get it using the following function, where the first argument is the number of colors and the second argument is the number of cells the rule depends on.

CellularAutomatonData`Private`data[2,2]

Access those growth rates through CellularAutomatonData:

CellularAutomatonData[{{0,2,(1/2)},{{1},0}},"GrowthRate"]
CellularAutomatonData[{{1,2,(1/2)},{{1},0}},"GrowthRate"]
CellularAutomatonData[{{1,2,(1/2)},{{0},1}},"GrowthRate"]
⋮
CellularAutomatonData[{{8,2,(1/2)},{{0},1}},"GrowthRate"]
CellularAutomatonData[{{10,2,(1/2)},{{1},0}},"GrowthRate"]
CellularAutomatonData[{{10,2,(1/2)},{{0},1}},"GrowthRate"]

For each class of equivalent automata, the raw data only contains data for one representative.  Consequently, not all rule numbers are present:

First/@CellularAutomatonData`Private`data[2,2]

For missing rules, CellularAutomatonData determines the minimal equivalent rule number and pulls the data from that rule:

CellularAutomatonData[{{4,2,(1/2)},{{1},0}},"GrowthRate"]

Count the automata with eventually periodic boundaries:

Cases[Join@@Thread/@CellularAutomatonData`Private`data[2,4],HoldPattern[Rule][_,_->{___,"BoundaryWordPeriodLength"->_,___}]]//Length

Count the automata with morphic boundaries:

Cases[Join@@Thread/@CellularAutomatonData`Private`data[2,4],HoldPattern[Rule][_,_->{___,"BoundaryWordMorphism"->_,___}]]//Length

Count the automata with irreducible boundaries:

Cases[Join@@Thread/@CellularAutomatonData`Private`data[2,4],HoldPattern[Rule][_,_->{___,"BestFits"->_,___}]]//Length

Those three classes partition the automata:

24287+81+720
Length[Join@@Thread/@CellularAutomatonData`Private`data[2,4]]

Package symbols

CellularAutomatonData

?CellularAutomatonData

Rule 106 begun from two black cells grows like (Sqrt[t]):
(This automaton is exceptional in that nearly all automata for which CellularAutomatonData has data are begun single-cell initial conditions.)

CellularAutomatonData[{{106,2,1},{{1,1},0}},"GrowthExponent"]

Survey the growth rates of the 256 automata with 2 colors depending on 3 cells, begun from a single black cell:

Tally[Table[CellularAutomatonData[{{n,2,1},{{1},0}},"GrowthRate"],{n,0,(2^(2^3))-1}]]

For automata depending on 4 cells there is more variety:
The integers and rational numbers are exact growth rates for reducible boundaries, and the numeric values are approximate growth rates for irreducible boundaries.

Tally[Table[CellularAutomatonData[{{n,2,(3/2)},{{1},0}},"GrowthRate"],{n,0,1000}]]

Run them all:

Tally[Table[CellularAutomatonData[{{n,2,(3/2)},{{1},0}},"GrowthRate"],{n,0,(2^(2^4))-1}]]//AbsoluteTiming

$ExponentlessAutomatonInitialCondition and $ExponentlessAutomatonRule

?$ExponentlessAutomatonInitialCondition

?$ExponentlessAutomatonRule

These two symbols contain the rule and initial condition for a cellular automaton with no limiting growth exponent.

Here is the beginning of the evolution of this automaton:

ArrayPlot[CellularAutomaton[$ExponentlessAutomatonRule,$ExponentlessAutomatonInitialCondition,100]]

The first thousand rows:

ArrayPlot[CellularAutomaton[$ExponentlessAutomatonRule,$ExponentlessAutomatonInitialCondition,1000],Frame->False,PixelConstrained->1]

The rule consists of 60 cases:

$ExponentlessAutomatonRule//Length

On the initial condition hand, the initial condition is fairly simple:

$ExponentlessAutomatonInitialCondition