Study backtracking in cellular automata as a multiway system
by Wenjie Zhou
National University of Singapore
by Wenjie Zhou
National University of Singapore
[Abstract: Through the middle row of the known automata, we will generate the array diagrams traced back by the cellular automata rules as a multi-way system. As a result of the backtracking, the cells from the multi-ways system are grayscale. The complexity of the problem is (2^k), and we will study more effective methods to solve it. We are expected to display the results in a discrete manner, which will definitely appear in some black and white cells in a multiway system one has generated.
We define our components in cellular automata as T-cells for which have upper-left, upper-middle, upper-right, and bottom-middle members. We assumed that if the middle column which is upper-middle and bottom-middle members in a T-cell of all components in a rule is closed in addition operation(mod 4), that is {0,0}, {0,1},{1,0},{1,1} must exist the rule of the cellular automata. Then the multiway system is guaranteed to exist and we can do the backtracking for it.
We found Rule 22, 30, 31,90,126,129,170 can be a multiway system and trackable.
Rule 10,17, 54, 250, 255 are not trackable, in which rule 255 middle column of T-cells are not closed under addition. For example, if there any 0’s appeared in the given center column, then we definitely can not get an initial condition through the backtracking function.
We define our components in cellular automata as T-cells for which have upper-left, upper-middle, upper-right, and bottom-middle members. We assumed that if the middle column which is upper-middle and bottom-middle members in a T-cell of all components in a rule is closed in addition operation(mod 4), that is {0,0}, {0,1},{1,0},{1,1} must exist the rule of the cellular automata. Then the multiway system is guaranteed to exist and we can do the backtracking for it.
We found Rule 22, 30, 31,90,126,129,170 can be a multiway system and trackable.
Rule 10,17, 54, 250, 255 are not trackable, in which rule 255 middle column of T-cells are not closed under addition. For example, if there any 0’s appeared in the given center column, then we definitely can not get an initial condition through the backtracking function.
Choose Rule 30 as a primary study rule
Choose Rule 30 as a primary study rule
Learning the patterns from the Cellular Automaton Rule
Learning the patterns from the Cellular Automaton Rule
In[]:=
RulePlot[CellularAutomaton[30]]
Out[]=
We observed that Rule 30 has two pairs of middle columns that are closed in addition (Mod 4), so it should give us the desired output by studying the T-cells.
(*validQuadQ[quad_]:=Not[Xor[quad[[4]],BooleanMinimize[BooleanFunction[30,3]][Sequence@@quad[[;;3]]]]];*)
In[]:=
validQuadQ[quad_]:=Not[Xor[quad[[4]],BooleanMinimize[BooleanFunction[22,3]][Sequence@@quad[[;;3]]]]];
In[]:=
validTFromBM[position_,cells_]:=Simplify[validQuadQ[{cells[position-{1,1}],cells[position-{1,0}],cells[position-{1,-1}],cells[position]}]];notValidTFromBM[position_,cells_]:=Not[validTFromBM[position,cells]];
Determine the position of the cells which can give us the guaranteed output
Determine the position of the cells which can give us the guaranteed output
We are checking every given a cell it’s upper-left,upper-middle ,upper-right, and bottom-middle which can return us the True, False or contradiction as a result.
In[]:=
determine[position_,cells_]:=Module[{invalidator,canbetrue,canbefalse},Switch[cells[position],(*Ifit'salreadyknown,returnthat*)True,True,False,False,_,invalidator=Or[notValidTFromBM[position+{1,1},cells],notValidTFromBM[position+{1,0},cells],notValidTFromBM[position-{1,1},cells],notValidTFromBM[position,cells]];canbetrue=If[SameQ[invalidator/.{cells[position]->True},True],False,True];canbefalse=If[SameQ[invalidator/.{cells[position]->False},True],False,True];Switch[{canbefalse,canbetrue},{True,False},False,{False,True},True,{False,False},"Contradiction",{True,True},"Undetermined",_,"Something went horribly wrong"]]];
In this study, we are using column of length 5 as center column, so the valid positions will be restrained in the number of columns from 1 to 9, rows from 1 to 6.
In[]:=
validPositionQ[{row_,column_}]:=If[row<=0||row>=7||column<=0||column>=10,False,True];
We set the cells and it’s neighbors which value can be found, then drop the keys where the value is already found.
In[]:=
setCell[position_,value_,cells_,neighbors_]:=Module[{newcells,newneighbors,informed},newcells=cells;newcells[position]=value;newneighbors=neighbors;newneighbors=KeyDrop[newneighbors,{position}];informed={{-1,-1},{-1,0},{-1,1},{0,-2},{0,-1},{0,1},{0,2},{1,-1},{1,0},{1,1}};informed=(#+position)&/@informed;If[!KeyExistsQ[newcells,#]&&validPositionQ[#],(newneighbors[#]=First[Lookup[newneighbors,{#},CreateDataStructure["HashSet"]]];newneighbors[#]["Insert",position];)]&/@informed;{newcells,newneighbors}];
We try to update the cells where the positions and their neighbor.
In[]:=
tryUpdate[position_,cells_,neighbors_]:=Module[{determined},determined=determine[position,cells];If[determined==="Contradiction",Return[{cells,"Contradiction"}],If[BooleanQ[determined],setCell[position,determined,cells,neighbors],{cells,neighbors}]]];
Update all cells where has no contradiction occurs.
In[]:=
updateAll[oldcells_,oldneighbors_]:=Module[{currentbatch,cells,neighbors},cells=oldcells;neighbors=oldneighbors;If[neighbors==="Contradiction",Return[{cells,"Contradiction"}],currentbatch=Keys[ReverseSortBy[neighbors,#["Length"]&]];(If[neighbors==="Contradiction",Return[{cells,"Contradiction"}],{cells,neighbors}=tryUpdate[#,cells,neighbors]])&/@currentbatch;If[Length[cells]==Length[oldcells],{cells,neighbors},updateAll[cells,neighbors]]]];
Arrange them in the done cells for each key
In[]:=
doneQ[cells_]:=AllTrue[Flatten[Table[Table[{row,column},{column,row,10-row}],{row,5}],1],KeyExistsQ[cells,#]&];
Split the cells by back tracking for their may has more then one possible values
In[]:=
splitBackTrack[{oldcells_,oldneighbors_}]:=Module[{cells,neighbors,splitposition,splittrue,splitfalse},If[oldneighbors==="Contradiction",Return[{{},{}}],If[doneQ[oldcells],SparseArray@KeyValueMap[#1->#2&,oldcells],{cells,neighbors}=updateAll[oldcells,oldneighbors];If[neighbors==="Contradiction",Return[{{},{}}],splitposition=First[Keys[KeySort[neighbors]]];splittrue=setCell[splitposition,True,cells,neighbors];splitfalse=setCell[splitposition,False,cells,neighbors];Tree[SparseArray@KeyValueMap[#1->#2&,cells],{splitBackTrack[splittrue],splitBackTrack[splitfalse]}]]]]];
Flatten the positions as needed for the results to be averaged weight.
In[]:=
positions=Flatten[Table[Table[{row,column},{column,row,10-row}],{row,5}],1];
Now we can do the back tracking:
In[]:=
backtrack[initial_,size_]:=Module[{cells,neighbors,tree,results,positions},neighbors=<||>;cells=<||>;({cells,neighbors}=setCell[#[[1]],#[[2]],cells,neighbors])&/@initial;tree=splitBackTrack[{cells,neighbors}];results=TreeData/@TreeLeaves[tree];results=DeleteCases[results,{{},{}}];If[Length[results]==0,"Not a valid center column!",positions=Flatten[Table[Table[{row,column},{column,row,10-row}],{row,5}],1];SparseArray[meanposition[#,results]&/@positions]]];
Evaluate the modules
Evaluate the modules
Initiate the middle column and other variables,
Call our functions
Call our functions
Keywords
Keywords
◼
BooleanMinimize[BooleanFunction[30,3]]
◼
RulePlot[CellularAutomaton[30]]
◼
ArrayPlot[CellularAutomaton[]]
Acknowledgment
Acknowledgment
I want to especially thank my mentor Jesse Galefas and our teaching assistants Jesse Friedman, Fez Zaman, and Silvia Hao, who helped me a lot during the coding process. I am very grateful to Mr. Stephen Wolfram for providing us with key ideas in the right direction.I am thankful that I have this wonderful opportunity to do this great project. It also helped me conduct a lot of research, and I started to understand many new things in a New Kind of Science.I really appreciate them.
References
References