BijectiveRules 1.12

documentation notebook

Eric Rowland
https://ericrowland.github.io/packages.html

Introduction

BijectiveRules is a package for studying right bijective and left bijective cellular automaton rules.
This introduction gives an overview of the main features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.

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

<<BijectiveRules`

BijectiveRules uses the same notation as CellularAutomaton.  That is, rules are written in the form {n,k,r}, where n is the rule number, k is the number of colors, and r is the radius (so that 2r+1 is the number of cells on which the rule depends).

For reversible cellular automata, a row with an infinite right tail (“leftful row”) is represented as {foregroundlist,tailcolor}, as in CellularAutomaton.
A row with an infinite left tail (“rightful row”) is represented as {tailcolor,foregroundlist}.

Here we explore 2-color, radius 1 ("elementary") right bijective rules.

RightBijectiveRules[2,1]

This shows which rules can have which backgrounds (white, black, alternating, or either).

Grid[{#,ColorCycles[First[#]]}&/@GatherBy[RightBijectiveRules[2,1],ColorCycles]]

The first class below supports initial conditions with a white background; the second class supports initial conditions with a black background.

({Select[#1,MemberQ[Flatten[ColorCycles[#1]],0]&],Select[#1,MemberQ[Flatten[ColorCycles[#1]],1]&]}&)[RightBijectiveRules[2,1]]

White background initial conditions

Here are the predecessor rows for the 12 right bijective rules which support white background initial conditions.

Grid[Function[n,{n,RightfulPredecessor[n,{0,Prepend[ConstantArray[0,10],1]}]}]/@{85,86,89,90,101,102,105,106,150,154,166,170}]

Here is a little of each history:

GraphicsGrid[Partition[Function[n,ArrayPlot[ReversibleCellularAutomaton[n,{0,Prepend[ConstantArray[0,100],1]},{{-32,32}}]]]/@{85,86,89,90,101,102,105,106,150,154,166,170},4],ImageSize->700]

The following table counts the number of leftmost black cells for a range of 41 rows in the history.

With[{init={0,Prepend[ConstantArray[0,100],1]}},Grid[Function[n,{n,BorderBlockLength/@ReversibleCellularAutomaton[n,init,{{-10,10}}]}]/@{85,86,89,90,101,102,105,106,150,154,166,170}]]

The next table counts the number of leftmost cells on row t that agree with the initial condition.

AgreementLength[lists__?(Depth[#]≥2&)]:=LengthWhile[Transpose[PadRight[List@@@{lists},{Length[{lists}],Max[Length/@{lists}]},Unique[]]],SameQ@@#&]

With[{row=Prepend[ConstantArray[0,100],1]},Grid[Function[n,{n,(AgreementLength[row,#1]&)/@ReversibleCellularAutomaton[n,{0,row},{{-10,10}}]}]/@{85,86,89,90,101,102,105,106,150,154,166,170}]]

Picking out the rows t=(2^n) gives the following sequences.

With[{init={0,Prepend[ConstantArray[0,200],1]}},Grid[Function[n,{n,ConvergenceSequence[n,init,8]}]/@{85,86,89,90,101,102,105,106,150,154,166,170}]]

Black background initial conditions

Here are the predecessor rows for the 12 right bijective rules which support black background initial conditions.

Grid[Function[n,{n,RightfulPredecessor[n,{1,Prepend[ConstantArray[1,10],0]}]}]/@{85,89,101,105,149,150,153,154,165,166,169,170}]

Here is a little of each history:

GraphicsGrid[Partition[Function[n,ArrayPlot[ReversibleCellularAutomaton[n,{1,Prepend[ConstantArray[1,100],0]},{{-32,32}}]]]/@{85,89,101,105,149,150,153,154,165,166,169,170},4],ImageSize->700]

The following table counts the number of leftmost white cells for a range of 41 rows in the history.

With[{init={1,Prepend[ConstantArray[1,100],0]}},Grid[Function[n,{n,(BorderBlockLength[#1,1]&)/@ReversibleCellularAutomaton[n,init,{{-10,10}}]}]/@{85,89,101,105,149,150,153,154,165,166,169,170}]]

The next table counts the number of leftmost cells on row t that agree with the initial condition.

AgreementLength[lists__?(Depth[#]≥2&)]:=LengthWhile[Transpose[PadRight[List@@@{lists},{Length[{lists}],Max[Length/@{lists}]},Unique[]]],SameQ@@#&]

With[{row=Prepend[ConstantArray[1,100],0]},Grid[Function[n,{n,(AgreementLength[row,#1]&)/@ReversibleCellularAutomaton[n,{1,row},{{-10,10}}]}]/@{85,89,101,105,149,150,153,154,165,166,169,170}]]

Picking out the rows t=(2^n) gives the following sequences.

With[{init={1,Prepend[ConstantArray[1,200],0]}},Grid[Function[n,{n,ConvergenceSequence[n,init,8]}]/@{85,89,101,105,149,150,153,154,165,166,169,170}]]

Package symbols

ApplyRule and ApplyRightBijectiveRuleInverse

?ApplyRule

?ApplyRightBijectiveRuleInverse

ApplyRightBijectiveRuleInverse[{86,2,3},{1,0},0]

ApplyRule[{86,2,3},{1,0,1}]

BijectiveQ, LeftBijectiveQ, and RightBijectiveQ

?LeftBijectiveQ

Select[Range[0,255],LeftBijectiveQ]

?RightBijectiveQ

Select[Range[0,255],RightBijectiveQ]

?BijectiveQ

Select[Range[0,255],BijectiveQ[#,2]&]

Select[Range[0,255],Function[n,And@@(BijectiveQ[n,#1]&)/@Range[3]]]

BorderBlockLength

?BorderBlockLength

BorderBlockLength[{1,2,2,3,3,3},1]

BorderBlockLength/@ReversibleCellularAutomaton[86,{0,Prepend[ConstantArray[0,100],1]},{{-10,10}}]

BorderBlockLength/@Reverse/@ReversibleCellularAutomaton[30,{Append[ConstantArray[0,100],1],0},{{-10,10}}]

ColorCycle and ColorCycles

?ColorCycle

?ColorCycles

Rule 30 has a white background, while rule 45 has an alternating background:

ColorCycles[30]

ColorCycles[45]

Rule 150 has either a white background or a black background:

ColorCycles[150]

ColorEquivalentRules

?ColorEquivalentRules

These are the 2-color rules depending on 3 cells that are equivalent to rule 86 under a permutation of colors.

ColorEquivalentRules[86]

This gives the additional rules that are equivalent under a left–right reflection.

ColorEquivalentRules[LeftRightReflection[86]]

ConvergenceSequence and Rule30ConvergenceData

?ConvergenceSequence

ArrayPlot[ReversibleCellularAutomaton[86,{0,Prepend[ConstantArray[0,200],1]},(2^10)][[(2^(Range[0,10]))+1]]]

With[{row=Prepend[ConstantArray[0,200],1]},(LengthWhile[Equal@@@Transpose[{row,#}],#&]&)/@ReversibleCellularAutomaton[86,{0,row},(2^10)][[(2^(Range[0,10]))+1]]]

ConvergenceSequence[86,{0,Prepend[ConstantArray[0,200],1]},10]

Many more terms of this sequence have been computed:

?Rule30ConvergenceData

Rule30ConvergenceData[Range[0,45]]

DependenceStrengths

?DependenceStrengths

Rule 30 is left bijective, since changing the left bit always changes the output:

DependenceStrengths[30]

A cell under rule 0 has no dependence on the previous step:

DependenceStrengths[0]

Rule 105 is bijective in each position:

DependenceStrengths[105]

LeftBijectiveInverse and RightBijectiveInverse

?LeftBijectiveInverse

?RightBijectiveInverse

This is the rule that computes the inverse of rule 86.

RightBijectiveInverse[86]

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

Taking the inverse twice gives a 4-color, radius 1/2 rule that emulates the 2-color, radius 1 rule 86.

RightBijectiveInverse[{457907124,4,(1/2)}]

GraphicsRow[{ArrayPlot[CellularAutomaton[{454958004,4,(1/2)},{{3},0},100]],ArrayPlot[CellularAutomaton[{86,2,{{-2},{-1},{0}}},{{1},0},100]]},ImageSize->700]

LeftBijectiveRules, RightBijectiveRules, and LeftOrRightBijectiveRules

?LeftBijectiveRules

LeftBijectiveRules[2,1]

?RightBijectiveRules

RightBijectiveRules[2,1]

?LeftOrRightBijectiveRules

LeftOrRightBijectiveRules[2,1]

LeftfulPredecessor and RightfulPredecessor

?LeftfulPredecessor

LeftfulPredecessor[30,{{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},0}]

?RightfulPredecessor

RightfulPredecessor[86,{0,{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}]

ReversibleCellularAutomaton is generally faster than LeftfulPredecessor and RightfulPredecessor because it uses CellularAutomaton.

LeftfulSuccessor and RightfulSuccessor

?LeftfulSuccessor

LeftfulSuccessor[30,{{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},0}]

?RightfulSuccessor

RightfulSuccessor[86,{0,{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}]

ReversibleCellularAutomaton is generally faster than LeftfulSuccecessor and RightfulSuccecessor because it uses CellularAutomaton.

LeftRightReflection

?LeftRightReflection

LeftRightReflection[30]

LeftRightReflection[86]

RandomLeftBijectiveRule and RandomRightBijectiveRule

?RandomLeftBijectiveRule

?RandomRightBijectiveRule

RandomRightBijectiveRule[2,1]

RandomRightBijectiveRule[5,3/2]

RightBijectiveQ[%]

ReverseRow

?ReverseRow

ReverseRow[{0,{1,0,0,1,1}}]

ReverseRow[{{1,1,0,0,1},0}]

ReversibleCellularAutomaton

?ReversibleCellularAutomaton

The following evaluations compute some rows in the history of right bijective rule 86.

ReversibleCellularAutomaton[86,{0,{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}},-2]

ReversibleCellularAutomaton[86,{0,{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}},2]

ReversibleCellularAutomaton[86,{0,{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}},{{-2,2}}]

ArrayPlot[ReversibleCellularAutomaton[86,{0,Prepend[ConstantArray[0,100],1]},{{-50,50}}]]

Equivalently, we can consider the history of rule 30, its left–right reflection.

ReversibleCellularAutomaton[30,{{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},0},{{-2,2}}]

Manipulate[ArrayPlot[ReversibleCellularAutomaton[30,{Append[ConstantArray[0,200],1],0},{{t0,t0+length-1}}]],{{t0,-50},-100,100,1},{{length,100},1,200,1},SaveDefinitions->True]