Cellular automata

In[]:=
SeedRandom[42];​​size=512;​​standardInitialization={{1},0};​​randomInitialization=RandomInteger[1,size];
Rule 110 and 30 are elementary cellular automaton rules introduced by Stephen Wolfram in 1983. The rule defines the binary coloring of cells of subsequent rows of a square grid based on three neighboring cells.
Top rows of the pattern generated by rule 110:
Module[{automaton,centerColumn},​​automaton=CellularAutomaton[110,standardInitialization,size-1];​​ArrayPlot[automaton,Frame->None,ImageSize->600,ColorRules->{0->White,1->Black}]]
Out[]=
Starting from a random initial condition highlights the particle like interactions:
Module[{automaton,centerColumn},​​automaton=CellularAutomaton[110,randomInitialization,2size-1];​​ArrayPlot[automaton[[Range[size,2size]]],Frame->None,ImageSize->600,ColorRules->{0->White,1->Black}]]
Out[]=
It would be quite useful to highlight these particles for further analysis.
How could these particles be identified in general and in a formal way?

Physics analogy

◼
  • The computation required to produce the subsequent rows corresponds to the passage of time.
    • ◼
  • The horizontal axis corresponds to one dimensional space.
    • ◼
  • Coarse-graining by an observer is introduced by collecting microstates over a sliding window both in time and space, simulating a finite sized observer defined by a bit-mask.
    • ◼
  • A notion of measured energy (entropy) is established as the negative log-probability of the microstate in the sliding window.
    • ◼
  • The probabilities need to be “calibrated” for each rule and observer mask on a representative sample. This ensures that subsequent plots will have comparable coloring.
    • ◼
  • The energy values can be used to identify the “particles” moving in front of a background “vacuum” state by coloring them on the plot.
    • In[]:=
    Observe[automaton_,mask_]:=Module[{d,h,w,rows,cols,observations},​​d=Dimensions[mask];h=d[[1]];w=d[[2]];rows=Length[automaton];cols=Length[automaton[[1]]];​​observations=Table[BitAnd[mask,automaton[[i;;i+h-1,j;;j+w-1]]],{i,rows-h+1},{j,1,cols-w+1}];​​observations]​​​​CalibrateEnergy[automaton_,mask_]:=Module[{hole,observations,counts,energyMap,minEnergy,normalizedEnergyMap},​​hole=mask*0;​​observations=DeleteCases[Observe[automaton,mask],hole];​​counts=Counts[Flatten[observations,1]];​​energyMap=Association[KeyValueMap[#1->N[-Log[#2],9]&,counts]];​​minEnergy=Min[Values[energyMap]];​​normalizedEnergyMap=Association[KeyValueMap[#1->#2-minEnergy&,energyMap]];​​Append[normalizedEnergyMap,hole->-Infinity]]​​​​MeasureEnergy[automaton_,mask_,energyMap_]:=Module[{hole,observations,energy},​​hole=mask*0;​​observations=DeleteCases[Observe[automaton,mask],hole];​​energy=Replace[observations,energyMap,{2}];​​energy]​​​​PlotEnergy[automaton_,mask_,energyMap_]:=Module[{observations,hole,energy},​​energy=MeasureEnergy[automaton,mask,energyMap];​​ArrayPlot[energy,ImageSize->600,ColorFunction(If[#==-Infinity,Black,ColorData["TemperatureMap"][#]]&),Background->Gray]]​​​​PatternGrid[energyMap_,observerMask_]:=Module[{patterns,values,items},patterns=SortBy[Most[Keys[energyMap]],energyMap];​​values=Most[energyMap]/@patterns;​​items=Table[Column[{Overlay[{ArrayPlot[observerMask,ColorRules->{0->White,1->LightBlue},Frame->True,ImageSize->{50,50}],ArrayPlot[patterns[[i]],ColorRules->{0->Transparent,1->Black},Frame->False,ImageSize->{50,50}]}],NumberForm[Round[values[[i]],0.001],{5,3}]},Center],{i,Length[patterns]}];​​Grid[Partition[items,8,8,{1,1},{}],Spacings->{2,2}]]​​​​SquareMask[size_]:=Table[1,{i,1,size},{j,1,size}]​​DiamondMask[size_]:=Module[{h},h=(size-1)/2;Table[If[Abs[i]+Abs[j]<=h,1,0],{i,-h,h},{j,-h,h}]]​​​​observerMask=DiamondMask[5];​​​​calibratedEnergies=<|​​30->CalibrateEnergy[CellularAutomaton[30,standardInitialization,512],observerMask],​​110->CalibrateEnergy[CellularAutomaton[110,randomInitialization,1024],observerMask]|>;

    Rule 110

    Standard

    automaton=CellularAutomaton[110,standardInitialization,size-1];​​PlotEnergy[automaton,observerMask,calibratedEnergies[110]]
    Out[]=

    Random

    Patterns

    Rule 30

    Standard

    Random

    Patterns