Further Results in Arithmetical CA

Johan Veerman

Pontificia Universidad Católica del Perú

Overview

The Principle of Computational Equivalence states that, beyond a certain (low) threshold, systems show complex behavior with equivalent (universal) computational capabilities.

Can we make simple computational systems calculate mathematical functions? 
In Chapter 11 of the NKS book it was shown that we can. We show some extensions of this idea.

One of the purposes behind this work is to understand how simple systems in general could be "programmed" to perform simple calculations. The final goal of this purpose would be to understand how natural systems compute.

The other purpose is to open new paths that would lead to alternative computational architectures. Making an Arithmetic Logic Unit (ALU) based on a simple system such as cellular automata (CA) will be a first step towards this goal.

Two methods: specific construction and searches in rule spaces.

Outline:

1.- Some constructions
2-. Binary operations
3.- Some search results
4.- A couple of tools for analysis
5.- Brief discussion

Some constructions

Specific constructions - serial

Bottom-up approach: serial constructions are easier to program.
But we are making a parallel system work serially, therefore:
Too many colors or states are needed.
They take too many steps to compute.

serialAddition[{a_, b_, c_}] :=
Switch[{a, b, c},{0,0,a4},a5,{0,a5,0},a5,{a1,1,0},a6,{a1,a5,0},0,{a2,a5,0},a5,{a5,0,0},0,{a1,1,_},a2,{a3,0,_},a1,{_,0,a6},a2,{_,1,a2},a4,{a1,_,_},a1,{a3,_,_},a3,{a5,_,_},a3,{_,_,a2},a2,{_,_,a4},a4,{_,1,_},1,{_,a3,_},1,{_,a4,_},1,{_,a5,_},1,{_,a6,_},a5,{_,_,_},0]
sa=CellularAutomaton[{serialAddition[#] &, {}, 1}, {{1,1,a1,1,1,1}, 0}, 43]/. 0 -> ".";
serialSubtraction[{a_, b_, c_}] :=
Switch[{a, b, c},{s1,1,0},s3,{s1,1,_},s2,{s1,s4,_},0,{_,1,s2},s1,{s1,_,_},s1,{_,_,s2},s2,{_,_,s3},s2,{_,s3,_},s4,{_,s4,_},s4,{_,1,_},1,{_,_,_},0]
ss=CellularAutomaton[{serialSubtraction[#] &, {}, 1}, {{1,1,1,1,s1,1,1,1}, 0}, 43]/. 0 -> ".";
serialMultiplication[{a_, b_, c_}] :=
Switch[{a, b, c},{0,1,m2},m5,{0,1,m3},m4,{1,x2,m2},m5,{1,x2,m3},m4,{m1,1,0},s1,{m4,x1,0},m5,{m4,x1,x2},m5,{m7,x1,x2},m5,{m1,0,_},m1,{m1,1,_},m2,{m4,x1,_},m4,{m7,1,_},m7,{m7,x1,_},m4,{m7,x2,_},m9,{m9,0,_},m1,{m9,x2,_},m9,{_,0,m5},m7,{_,0,m6},m7,{_,0,m8},m7,{_,1,m2},m3,{_,1,m3},m3,{_,1,m5},m8,{_,1,m6},m8,{_,1,m8},m8,{_,1,s1},s2,{_,x1,m6},m6,{_,x2,m2},m3,{_,x2,m3},m3,{_,x2,s1},s2,{_,x2,s2},s2,{_,_,m2},m2,{_,_,m5},m6,{_,_,s1},s1,{_,m3,_},x1,{_,m4,_},x1,{_,m5,_},x2,{_,m6,_},x1,{_,m7,_},1,{_,m8,_},1,{_,m9,_},x2,{_,s2,_},1,{_,x1,_},x1,{_,x2,_},x2,{_,1,_},1,{_,_,_},0]
sm=CellularAutomaton[{serialMultiplication[#] &, {}, 1}, {{1,1,1,m1,1,1}, 0}, 43]/. 0 -> ".";
serialDivision[{a_, b_, c_}] :=
Switch[{a, b, c},{0,1,d4},d7,{0,d3,0},x2,{0,d3,1},x2,{0,d3,x1},x2,{d1,1,0},d3,{d2,1,0},d3,{d7,x2,0},d8,{d1,1,_},d2,{d1,x2,_},d5,{d5,0,_},e1,{d5,1,_},e2,{d5,x1,_},d6,{d5,x2,_},d5,{d7,1,_},e3,{d8,0,_},1,{e2,0,_},e1,{e2,1,_},e2,{e3,0,_},1,{e3,1,_},e3,{_,0,d3},d4,{_,0,d6},d4,{_,1,d3},d3,{_,1,d4},d1,{_,1,e1},e1,{_,x2,d3},d3,{_,x2,d6},d6,{_,x2,e1},d3,{d1,_,_},d1,{d2,_,_},d2,{d7,_,_},d7,{_,_,d4},d4,{_,d2,_},1,{_,d3,_},x1,{_,d5,_},x2,{_,d6,_},x2,{_,e1,_},1,{_,e2,_},1,{_,e3,_},1,{_,x1,_},x1,{_,x2,_},x2,{_,1,_},1,{_,_,_},0]
sd=CellularAutomaton[{serialDivision[#] &, {}, 1}, {{1,1,1,1,d1,1,1}, 0}, 43]/. 0 -> ".";
Style[TableForm[{TableForm[sa],TableForm[ss],TableForm[sm],TableForm[sd]},
TableDirections->Row,TableSpacing->5,TableAlignments->Bottom],Small]

Specific constructions - parallel

Based on what we have learnt from serial constructions, but are more difficult to program.
Significantly less states are used.
Computations are carried out in few steps.
Same kinds of behavior used in serial constructions are used in parallel ones.

parallelAddition[{a_, b_, c_}] :=
Switch[{a, b, c},{0,0,a3},1,{a1,1,_},a1,{_,1,a1},1,{_,1,a2},a3,{_,_,a1},a2,{_,_,a2},a2,{_,_,a3},a3,{_,0,_},0,{_,1,_},1,{_,a1,_},0,{_,a2,_},0,{_,a3,_},1,{_,_,_},0]
pa=CellularAutomaton[{parallelAddition[#] &, {}, 1}, {{1,1,1,1,1,a1,1,1,1,1,1,1}, 0},31]/. 0 -> ".";
parallelSubtract[{a_, b_, c_}] :=
Switch[{a, b, c},{s1,0,_},0,{_,0,s1},s2,{_,1,s2},0,{s1,_,_},s1,{_,_,s2},s2,{_,1,_},1,{_,_,_},0]
ps=CellularAutomaton[{parallelSubtract[#] &, {}, 1}, {{1,1,1,1,1,1,1,1,s1,1,1,1,1,1,1}, 0},31]/. 0 -> ".";
parallelMultiplication[{a_, b_, c_}] :=
Switch[{a, b, c},{0,1,m3},m4,{0,x,m3},m4,{1,x,m3},m4,{c1,m5,m3},c1,{c1,x,m1},c1,{c1,x,m2},c2,{c1,x,m3},c1,{m1,1,0},m2,{m4,m5,m3},c1,{m4,x,m3},c1,{m6,x,m3},m4,{c1,c2,_},c2,{c1,m5,_},m4,{c1,x,_},m4,{m1,1,_},m1,{m4,m5,_},m4,{m4,m7,_},m6,{m4,x,_},m4,{_,0,m1},m1,{_,0,m2},m2,{_,0,m4},1,{_,0,m6},1,{_,1,m1},m3,{_,1,m3},m3,{_,1,m5},m6,{_,1,m6},m6,{_,c1,c1},c1,{_,c1,m4},m5,{_,c1,m5},c1,{_,m3,c1},m5,{_,m3,c2},m5,{_,m3,m2},c2,{_,m3,m4},m5,{_,m3,m5},m5,{_,m4,m5},m5,{_,m5,c1},m5,{_,m5,m3},m4,{_,m5,m4},m5,{_,m5,m5},m5,{_,m6,m4},m6,{_,m6,m5},m6,{_,m6,m6},m6,{_,x,c1},m5,{_,x,c2},m5,{_,x,m1},m3,{_,x,m3},m3,{_,x,m4},m5,{_,x,m5},m5,{_,x,m6},m6,{_,c1,_},m3,{_,c2,_},m7,{_,m3,_},x,{_,m4,_},x,{_,m5,_},x,{_,m6,_},1,{_,m7,_},m7,{_,x,_},x,{_,1,_},1,{_,_,_},0]
pm=CellularAutomaton[{parallelMultiplication[#] &, {}, 1}, {{1,1,1,1,m1,1,1,1,1}, 0},31]/. 0 -> ".";
Style[TableForm[{TableForm[pa],TableForm[ps]},TableDirections->Row,TableSpacing->5],Small]

Style[TableForm[pm,TableSpacing->1],Small]

Binary operations

16 states: particles:[base_]=2+5 base+(base^base)
Steps: radiusSteps[r_] := 2*Ceiling[Length[input2]/r] + Floor[Length[input2]/r] + 1
Input at the right side is entered backward.
Performs computation at maximal speed.

particles[base_]:=2+5 base+(base^base)
numbPart=Table[particles[i],{i,2,10}];
sizeInput=Ceiling[Table[Log[i,1000000000],{i,2,10}]//N];
TableForm[Transpose[{Table[i,{i,2,10}],numbPart,3 sizeInput}],TableSpacing->2,TableHeadings->{None,{"Base","States","Steps"}}]

Addition

binaryAddition[{a_, b_, c_}] :=
Switch[{a, b, c},{a0,0,0},aa,{a1,0,0},aa,{aa,i0,_},a0,{aa,i1,_},a1,{a0,i0,_},a0,{a0,i1,_},a1,{a1,i0,_},a0,{a1,i1,_},a1,{_,0,a0},a0,{_,0,a1},a1,{_,0,c0},i1,{_,0,c1},i1,{_,0,p0},o0,{_,0,p1},o0,{_,0,q0},o1,{_,0,q1},o1,{_,0,aa},aa,{_,i0,a0},o0,{_,i0,a1},o1,{_,i1,a0},o1,{_,i1,a1},c0,{_,i0,c0},i1,{_,i1,c0},c1,{_,i0,c1},i1,{_,i1,c1},c1,{_,i0,p0},o0,{_,i0,p1},o0,{_,i1,p0},o1,{_,i1,p1},o1,{_,i0,q0},o1,{_,i0,q1},o1,{_,i1,q0},c0,{_,i1,q1},c0,{_,o0,aa},h0,{_,o1,aa},h1,{_,i0,h0},h0,{_,i0,h1},h0,{_,i1,h0},h1,{_,i1,h1},h1,{_,o0,h0},h0,{_,o0,h1},h0,{_,o1,h0},h1,{_,o1,h1},h1,{_,o0,a0},p0,{_,o0,a1},q0,{_,o1,a0},p1,{_,o1,a1},q1,{_,o0,p0},p0,{_,o0,p1},p0,{_,o0,q0},q0,{_,o0,q1},q0,{_,o1,p0},p1,{_,o1,p1},p1,{_,o1,q0},q1,{_,o1,q1},q1,{_,i0,_},i0,{_,i1,_},i1,{_,o0,_},o0,{_,o1,_},o1,{_,p0,_},o0,{_,p1,_},o1,{_,q0,_},o0,{_,q1,_},o1,{_,c0,_},o0,{_,c1,_},i0,{_,h0,_},i0,{_,h1,_},i1,{_,_,_},0]
BAinitCond[inp1_,inp2_]:=Join[IntegerDigits[inp1,2]/.{0->i0,1->i1},{aa},Reverse[IntegerDigits[inp2,2]/.{0->i0,1->i1}]]
Style[Manipulate[BAinit=BAinitCond[i,j];
TableForm[CellularAutomaton[{binaryAddition[#] &, {}, 1}, {BAinit, 0},40]/.{ 0 ->".",i0->0,i1->1,aa->Style["aa",Red],a0->Style["a0",Red],a1->Style["a1",Red],p0->Style["p0",Blue],p1->Style["p1",Blue],q0->Style["q0",Magenta],q1->Style["q1",Magenta],c0->Style["c0",Purple],c1->Style["c1",Purple],o0->Style["o0",Green],o1->Style["o1",Green],h0->Style["h0",Orange],h1->Style["h1",Orange]}, TableSpacing->1],{i,1000,2000,10},{j,3000,4000,10}],Small]

Subtraction

binarySubtraction[{a_, b_, c_}] :=
Switch[{a, b, c},{s0,0,0},ss,{s1,0,0},ss,{ss,i0,_},s0,{ss,i1,_},s1,{s0,i0,_},s0,{s0,i1,_},s1,{s1,i0,_},s0,{s1,i1,_},s1,{_,0,s0},s0,{_,0,s1},s1,{_,i0,s0},o0,{_,i0,s1},c0,{_,i1,s0},o1,{_,i1,s1},o0,{_,i0,p0},o0,{_,i0,p1},o0,{_,i0,q0},c0,{_,i0,q1},c0,{_,i1,p0},o1,{_,i1,p1},o1,{_,i1,q0},o0,{_,i1,q1},o0,{_,o0,s0},p0,{_,o0,s1},q0,{_,o1,s0},p1,{_,o1,s1},q1,{_,o0,p0},p0,{_,o0,p1},p0,{_,o0,q0},q0,{_,o0,q1},q0,{_,o1,p0},p1,{_,o1,p1},p1,{_,o1,q0},q1,{_,o1,q1},q1,{_,i0,c0},c1,{_,i1,c0},i0,{_,i0,c1},c1,{_,i1,c1},i0,{_,o0,ss},h0,{_,o1,ss},h1,{_,i0,h0},h0,{_,i0,h1},h0,{_,i1,h0},h1,{_,i1,h1},h1,{_,o0,h0},h0,{_,o0,h1},h0,{_,o1,h0},h1,{_,o1,h1},h1,{_,0,ss},ss,{_,i0,_},i0,{_,i1,_},i1,{_,o0,_},o0,{_,o1,_},o1,{_,p0,_},o0,{_,p1,_},o1,{_,q0,_},o0,{_,q1,_},o1,{_,c0,_},o1,{_,c1,_},i1,{_,h0,_},i0,{_,h1,_},i1,{_,_,_},0]
BSinitCond[inp3_,inp4_]:=Join[IntegerDigits[inp3,2]/.{0->i0,1->i1},{ss},Reverse[IntegerDigits[inp4,2]/.{0->i0,1->i1}]]
Style[Manipulate[BSinit=BSinitCond[i,j];
TableForm[CellularAutomaton[{binarySubtraction[#] &, {}, 1}, {BSinit, 0},40]/.{ 0 ->".",i0->0,i1->1,ss->Style["ss",Red],s0->Style["s0",Red],s1->Style["s1",Red],p0->Style["p0",Blue],p1->Style["p1",Blue],q0->Style["q0",Magenta],q1->Style["q1",Magenta],c0->Style["c0",Purple],c1->Style["c1",Purple],o0->Style["o0",Green],o1->Style["o1",Green],h0->Style["h0",Orange],h1->Style["h1",Orange]}, TableSpacing->1],{i,3000,4000,10},{j,1000,2000,10}],Small]

Some search results

The method

CA rule spaces of k ≥ 3 can be unmanageable for exhaustive searches. We therefore tried to devise a method to narrow down the rule space. For our example, searches of subtraction rules where made with k = 3 and r = 1, where the size of the rule is given by (k^( 2 r + 1)), which gives us a rule with 27 "bits" of size. The space we need to search contains (k^27)rules (over 7 x (10^12)). Therefore, "freezing" as many of these bits as we can exponentially decreases the rule space.

1. First we fix any initial assumptions as, for example, "background and input don't interact", which is the same as fixing rule 204 of the ECA in a rule space where k = 3.

We "freeze" 8 bits of the rules, reducing our search space to  (k^19)rules.

2. At this point, any other initial assumptions about some bits of the rule can be included. We call them "frozen bits".

3. We then make a random search in the reduced CA rule space for rules that meet the following criteria: they give a desired result encoded in the same way as the initial condition and they have to halt.

4. After these rules are found (say, 30 rules), they are passed through some filters. Basically, they are tried out with many different initial conditions and results. To follow our example, let's say that from 30 randomly found rules only 10 pass these tests.

5. These rules are then compared, bit by bit, to see which of them are repeated in all -or most-of the rules. These bits of the rule are turned into frozen bits, thus reducing the CA rule space further.

6. Repeat steps 3 to 5 until the CA rule space is reduced enough for an exhaustive search.

A search made for subtraction rules

As an example, nearly a thousand rules were found using the method described above in less than 1 hour.
With and exhaustive search, less than a hundred rules where found in about ten hours.

Out of a sample of 974 rules found, those with the same pattern behavior were filtered, leaving 71 with effectively different patterns, shown below.

All four classes of behavior are found inside the area performing the computation.

subtractionRules={69738168204,69738181326,164139633918,165172748661,165172761783,166464163413,255857848191,255986988354,257005767312,257134900914,258153681330,258297168942,259186796073,259215493887,259315934049,259330279311,259445076399,259459430409,260349050979,260363413737,260377755354,260478202806,260492545152,260607335679,260607344427,260621685315,260621687502,353329979274,353588246478,354492240741,354621374343,447473151540,536981640696,536995983042,537239907900,538158244509,538273035765,538273042326,539306163630,539550087759,540454062339,540597552138,540712349955,540712356516,541616325993,541616331096,541616332554,541616333283,541745470530,541745477820,541759820166,541874619441,541888960329,541888962516,542778588189,542792948031,542907725436,542907732726,543036868515,634597247727,635888649357,636921770661,728998713441,731194096212,819411177177,819683799849,821864827152,822883605381,823141895184,824175000450,824175007011,824175009927,824189350086,824189365395,825208129044,825222480138,825351620301,825351624675,825466402809,825466417389,1013494485969,1101840713658,1103132108727,1104423516918,1105313141862,1105327487124,1105442275464,1105442288586,1105456627287,1105456631661,1105571428749,1105585771824,1105585774011,1105585778385,1106475403329,1106475406245,1106489761713,1106604552240,1106618888754,1106733684384,1106748028917,1107637660422,1107766800585,1107766804959,1107766807146,1107766813707,1107781148034,1107781163343,1107895945122,1107910296945,1200618575595,1294890901146,1296182296215,1296182309337,1384270243578,1384399377180,1384399383741,1386594773073,1386723906675,1386838690641,1386838697202,1387871827254,1388000954295,1388000965230,1388904946371,1389034076328,1389048423048,1389163215762,1390067195445,1390067210025,1390081557474,1390196342169,1390196348001,1390325481603,1390325488164,1390339833426,1481885857170,1483048125198,1483177265361,1578611832696,1578611845818,1666828920222,1666972415853,1667991175128,1669024302993,1669268233683,1670172210450,1670172215553,1670172217740,1670301357903,1670301361548,1670315713371,1670430502440,1670430504627,1670444844786,1671348819366,1671348834675,1671463609893,1671592750056,1671592763907,1672496737758,1672640227557,1672755020271,1672755021000,1672755027561,1764315393651,1764444540375,1765606788720,1766639916585,1766639923146,1858716846243,1859879107710,1859879120832,1860783095412,1861041369177,1950291578007,1950420724731,1951697770164,1951712113239,1952601758595,1952601760782,1952616107502,1952730887823,1952745241104,1952745243291,1952745249852,1952860027257,1952860032360,1953764009127,1953764020062,1953778358034,1953893153664,1953907502571,1954022299659,1954022301846,1954036642734,1954926269865,1954940619501,1955055410028,1955055415131,1955055417318,1955184557481,1955184563313,2046744923571,2049198599790,2140888102398,2231558846460,2231558859582,2232850248090,2232979388253,2232979394814,2232979401375,2235045630861,2235045643983,2235160430136,2235160434510,2236193551440,2236193556543,2236193558001,2236337032491,2236451825934,2236466181402,2236466185776,2237355811449,2237484958173,2237614098336,2237628442869,2329174466613,2330465868243,2330595001845,2331498989547,2331757269873,2424738180672,2424738187233,2425900442139,2425900448700,2513988389502,2515150650969,2515279784571,2515279797693,2516298556239,2517460818435,2517475169529,2517475176090,2517589957869,2517589970991,2517604307505,2517604314066,2517719104593,2517719113341,2517733449855,2517733456416,2518637430996,2518881360228,2518881375537,2518895711322,2518895717883,2519785341369,2519799705585,2519914487364,2519914496112,2519928830439,2519928843561,2520043630443,2520057985911,2611862276859,2611890986337,2612895404724,2613024549261,2613038898897,2705876328645,2706005455686,2706005462247,2708071704855,2708329991742,2793060286119,2795270017068,2795370452856,2795384809053,2795399157960,2796417932544,2796532720884,2796690548655,2797580180889,2797694983809,2797852816683,2798728105113,2798742454020,2798857237257,2798871595641,2798885942361,2798986386168,2799000735804,2799904712571,2799904716945,2799904719132,2800019497266,2800019504556,2800019506743,2800148648364,2800435622859,2801052624402,2801052630963,2801181758733,2801181766752,2801196115659,2801310898167,2801310905457,2801325245616,2802214886598,2802214889514,2802243585870,2802243587328,2802344017284,2802344022387,2802344026032,2802358378584,2802473166924,2802473170569,2802487507083,2802487520205,2895454074807,2896358055948,2896616342835,2989338973308,2990630388060,3080009730492,3080138870655,3081157629201,3081430259163,3081430272285,3082319891397,3082319906706,3082449046869,3082578171723,3082578177555,3083482152864,3083482161612,3083496510519,3083496514893,3083611294485,3083754797406,3084644414331,3084644423079,3084658765425,3084902694657,3178787598990,3179045885877,3270735395046,3271768509789,3271768522911,3272930777817,3272930784378,3273189064704,3358191978108,3360516501042,3361406139108,3362453609319,3363587165682,3364878576060,3364878576789,3364892916948,3364892919135,3364892923509,3364892925696,3365007720597,3365022063672,3365294695821,3365911688616,3365911691532,3365926051374,3366040831695,3366040837527,3366055191537,3366169971129,3366169976232,3366184318578,3367073957373,3367088312841,3367203098994,3367203105555,3367217446443,3367332245718,3461346275634,3461346282195,3553035797925,3553164924966,3553294071690,3555360320859,3643964815752,3644997930495,3646016702163,3646145842326,3647178963630,3647178964359,3647193315453,3647308111083,3647322462177,3647322466551,3647437252704,3648341225097,3648341240406,3648470380569,3648484730205,3648599506152,3648599507610,3648599514171,3648599519274,3648613861620,3648613870368,3649503493125,3649503493854,3649517844948,3649517851509,3649632627456,3649646978550,3649761766890,3649776131835,3742613544087,3743646671952,3743646678513,3835594468008,3836627595873,3837789857340,3838048137666,3927556613700,3928446238644,3929608515420,3929622849747,3929622862869,3929737656312,3929751992097,3929881138821,3930770763765,3930785124336,3930899904657,3930899908302,3930899911218,3930914251377,3931043400288,3931043406849,3931933038354,3932062176330,3932062179246,3932076519405,3932191305558,4023751678938,4024913946966,4024913953527,4025043093690,4120219387260,4120348527423,4120477667586,4208694755112,4208823895275,4210890137883,4211019264924,4211134055451,4211148405087,4211148411648,4211162767116,4212038046069,4212038049714,4212052386228,4212052388415,4212052401537,4212167186232,4212310666554,4213200305349,4213200314097,4213214647695,4213343794419,4213458584946,4213458593694,4213472941143,4214362568274,4214376917910,4214491700418,4214491706250,4214506051512,4214620839852,4214635198236,4306439506680,4308505751475,4308634885077,4400582687694,4401486655713,4401615808998,4402778068278,4490995144869,4491124278471,4492415680101,4492415686662,4493434451769,4493434456143,4493563605054,4494596713236,4494596720526,4494725855586,4495629835269,4495644184176,4495644190737,4495773324339,4495773326526,4495888124343,4496792111316,4496806460952,4496921249292,4496921251479,4496935592367,4497050390184,4497050392371,4497064732530,4497064739091,4591064414997,4591193555160,4685078466783,4773424687911,4773682961676,4773682968237,4774845223143,4775878337886,4775878344447,4776897124863,4776911472312,4777026250446,4777026256278,4777040605914,4777155389880,4777155392067,4777169746077,4778059387059,4778188513371,4778202860820,4778317651347,4779221639778,4779221641965,4779221648526,4779350781399,4779365124474,4779479928123,4872460843296,4873493962413,4966604009001,4967507990142,5057145626022,5058293524731,5059326652596,5059326661344,5059455792759,5059455795675,5059584927090,5059584939483,5059599275997,5059599278184,5060618048394,5060632403862,5060632406049,5060632410423,5060747190744,5061651178446,5061651184278,5061665525166,5061780315693,5061794658768,5061909451482,5061909452211,5061909455856,5061909458043,5153469830694,5153469837984,5154632092161,5154632100909,5154646454190,5154761233053,5154761239614,5154890379777,5156052628122,5247613016811,5248789633017,5250066671160,5250066673347,5338556383545,5341756185432,5341756192722,5341770546003,5341784889807,5341784892723,5341784894181,5341784894910,5341899685437,5342014463571,5342014471590,5342028819039,5342918445441,5342918446170,5342918454189,5342918457105,5342918461479,5342918462208,5342932806741,5343047584146,5343047586333,5343047596539,5343047597997,5343061946904,5343076291437,5343176725038,5343176726496,5343176728683,5343176731599,5343205425039,5343205432329,5344080705450,5344080706179,5344080715656,5344095064563,5344095066750,5344095068937,5344109422218,5344209846342,5344209855090,5344209858735,5344209860922,5344224205455,5344338994524,5344338996711,5344339001814,5344353344889,5436157641669,5437319909697,5530171693455,5531463081963,5620713284232,5620971577680,5622004685862,5622019041330,5622133839147,5623037807166,5624200081755,5624314872282,5624329221918,5625347980464,5625362332287,5625362345409,5625477127917,5625491470263,5625606269538,5626510244118,5626639389384,5626639395945,5626782887202,5718730668678,5719491172413,5719749452739,5720653433880,5720782574043,5720911701084,5805914627610,5812730356977,5812730363538,5812859498598,5813634351240,5813763491403,5903401107600,5904305095302,5905453000572,5905467350208,5905725637095,5906615255478,5906615256207,5906615257665,5906615268600,5906744396370,5906758747464,5906873548926,5906873551113,5907906660024,5907906664398,5907906666585,5907906670959,5907906672417,5908035799458,5908035804561,5908035811122,5908179287799,5908939779141,5908939791534,5908939793721,5909068920762,5909083276959,5909327200359,6000772797792,6000887587590,6002178976098,6003097320726,6003341237565,6003341244126,6095030753295,6095030766417,6096193014762,6097226149188,6097484422953,6185572363755,6185701510479,6185844999549,6186734625222,6187896880128,6187896886689,6188011683777,6189044796333,6189044797791,6189044806539,6189059159091,6189073499250,6189073501437,6189073504353,6189173948160,6189188290506,6189303073014,6189303076659,6189303088323,6189317421921,6189317435043,6190207062174,6190221413997,6190235762904,6190336200150,6190336208898,6190479692865,6191369317809,6191369322912,6191369323641,6191369325099,6191369330931,6191369332389,6191383671090,6191383678380,6191398030203,6191498470365,6191627598135,6191627606154,6191627611257,6191641954332,6191656302510,6283187970786,6283446264234,6284350232253,6284479378977,6284479385538,6377331156174,6377589429939,6378622557804,6379913952873,6470312066973,6470455556772,6470570347299,6471474335730,6471474341562,6471488686824,6471617824800,6471732617514,6471746958402,6472636590636,6472650946104,6472765732986,6472765746108,6472894878981,6472909232991,6472909235178,6473798853561,6473927993724,6473942354295,6474071483523,6565875787593,6565875800715,6566779775295,6568200310527,6660018966420,6660922954122,6662085209028,6662343495915,6751593691623,6751722844908,6752755966212,6752999896902,6753014233416,6753903864921,6753903871482,6753918214557,6754033013832,6754047370029,6754162154724,6755066140239,6755195281860,6755209616187,6755209629309,6755209631496,6756228390771,6756228403164,6756357530205,6756357544056,6756371886402,6756486675471,6756486677658,6756501030939,6842250102816,6843426713190,6844560276843,6844588976115,6845722538310,6845751237582,6846884801235,6848047043748,6848061411609,6848176183911,6848176188285,6848176197033,6849209305215,6849223672347,6849338458500,6850371572514,6850371585636,6850500719967,6850629851382,6936378934194,6936393282372,6939865717137,6939894416409,6941056677876,6942190222575,6942190227678,6942190235697,6942190237155,6942218939343,6943352484042,6943352497164,6943366847529,6943481624205,6943610764368,6944514746967,6944514751341,6944773030209,7029388549368,7030665595530,7030679943708,7031698721937,7031813506632,7031827856268,7031827856997,7031842205904,7032875333769,7032975768099,7034008895964,7034138029566,7034166728109,7035171153057,7035171157431,7035185507796,7035199838478,7035199855245,7036333404318,7036333416711,7036347759786,7036347762702,7036362116712,7036362118170,7036462543752,7036606044486,7037495668701,7037495678178,7037495679636,7037510012505,7037510028543,7037524363599,7037624814696,7037639152668,7037653503762,7037653513239,7037753953401,7037753956317,7037753957046,7038657925065,7038657926523,7038657931626,7038657933813,7038657936000,7038657940374,7038787065228,7038787073976,7038787077621,7038787080537,7038801420696,7038801424341,7038801425799,7038815771790,7038815772519,7038916217784,7038930569607,7038944911953,7130476593351,7130605720392,7130605726953,7131767994981,7132801116285,7224878045943,7226040307410,7315290516240,7315548783444,7315548790005,7316581911309,7317600676416,7317615039174,7317744166215,7317744179337,7318762944444,7318777302828,7318892091168,7319021218209,7319021220396,7319021225499,7319021226957,7319021227686,7319021231331,7319021232060,7319021233518,7319035567845,7319939562108,7320068695710,7320183480405,7320183481863,7320183489153,7321087461546,7321101810453,7321216601709,7321230959364,7321345750620,7412906123271,7414197524901,7507049295537,7507049302098,7507307575863,7508211563565,7508469850452,7509373818471,7509502965195,7597978319925,7599140581392,7600159353060,7600302842859,7601192483112,7601192489673,7601321629836,7601450756877,7601465110887,7602354736560,7602354744579,7602369092028,7602483878181,7602483878910,7602483885471,7602483889116,7602483889845,7602498227817,7602498232191,7602613025634,7602613031466,7602613032195,7603516998027,7603517006775,7603531360056,7603646152770,7603775284185,7603775291475};
input1=30;input2=25;
initCond=Flatten[{Table[1,{input1}],2,Table[1,{input2}]}];
steps=3 input2;
differentSR=Flatten[Take[Union[Table[{subtractionRules[[i]],CellularAutomaton[{subtractionRules[[i]],3,1},{initCond,0},steps]},{i,Length[subtractionRules]}],SameTest->(#1[[2]]==#2[[2]]&)],All,1]];
ListAnimate[ArrayPlot[CellularAutomaton[{#,3,1},{initCond,0},steps],PlotLabel->#]&/@differentSR]

A couple of tools for analysis

Cartography

Only some of the bits of the rule are used for a specific calculation.
We can measure how far are the rules from each other in an ((k )^(2 r + 1))- dimensional space with k-long axes.
One method to do this is to produce pair separation histograms.

rulesLongForm=Map[IntegerDigits[#,3,27]&,subtractionRules];
euclideanDist=Sort[Flatten[Table[Norm[rulesLongForm[[i]]-rulesLongForm[[j]]]//N,{i,1,Length[subtractionRules]-1},{j,i+1,Length[subtractionRules]}]]];
manhattanDist=Sort[Flatten[Table[Norm[rulesLongForm[[i]]-rulesLongForm[[j]],1]//N,{i,1,Length[subtractionRules]-1},{j,i+1,Length[subtractionRules]}]]];
<<"Histograms`";
Histogram[euclideanDist,PlotLabel->"Euclidean Distance",AxesLabel->{"Distance","Number of pairs"},BarStyle->Red,ImageSize->700]

Histogram[manhattanDist,PlotLabel->"Manhattan Distance",AxesLabel->{"Distance","Number of pairs"},BarStyle->Red,ImageSize->700]

Bit activity

Two types of measurements:
Activity of all bits of the rule in each step.
Activity of each bit of the rule in time.

input1=15;input2=11;
initCond=Flatten[{Table[1,{input1}],2,Table[1,{input2}]}];
colors=3;radius=1;
steps=3 input2;
Manipulate[ListPlot[Table[Count[Partition[CellularAutomaton[{differentSR[[r]],3},{initCond,0},steps,{All,{-steps,steps}}][[s]],2 radius+1,1],IntegerDigits[i,colors,2 radius+1]],{i,0,(colors^(2 radius+1))-1}],Joined-> True,AxesOrigin->{1,0},PlotRange->{0,30},PlotLabel->differentSR[[r]]],{s,1,steps,1},{r,1,Length[differentSR],1}]

Manipulate[ListPlot[Transpose[Table[Count[Partition[CellularAutomaton[{differentSR[[r]],3},{initCond,0},steps,{All,{-steps,steps}}][[j]],2 radius+1,1],IntegerDigits[i,colors,2 radius+1]],{j,steps},{i,0,(colors^(2 radius+1))-1}]][[s]],Joined->True,AxesOrigin->{0,0},PlotRange->{0,25},PlotLabel->differentSR[[r]]],{s,1,(colors^(2 radius+1)),1},{r,1,Length[differentSR],1}]

Brief discussion

Floating point CA will lead to CA - ALU.

CA probably not the best system to perform arithmetical calculations.

How to construct or search for the best system?

Comparing with natural systems.

What sort of computations is nature doing around us?

Can we program nature?