The color of a particular cell is then found by evolving for a number of steps equal to the length of these input digit sequences. And this means for example that the outcome of a million steps of evolution for either of the cellular automata on the left is now determined by just 20 steps of evolution, where 20 is the length of the base 2 digit sequence of the number 1,000,000.

If the rules for a multiway system always increase string length then it is inevitable that any given string that is ever going to be generated must appear after only a limited number of steps. But if the rules can both increase and decrease string length the story is quite different, as the picture on the facing page illustrates.

Among the 256 elementary rules, the total numbers that have conserved quantities involving at most blocks of lengths 1 through 10 are {5, 38, 66, 88, 102, 108, 108, 114, 118, 118} . Rules that show complicated behavior usually do not seem to have conserved quantities, and this is true for example of rules 30, 90 and 110, at least up to blocks of length 10. … To identify any such quantity with certainty, it turns out to be enough to look at the k b + 2r - 1 states where no block of length b + 2r - 1 appears more than once (and perhaps even just some fairly small subset of these).

With this setup, a network consisting of just one node is {{1, 1}} and a 1D array of n nodes can be obtained with CyclicNet[n_] := RotateRight[ Table[Mod[{i - 1, i + 1}, n] + 1, {i, n}]] With above connections represented as 1 and the below connections as 2 , the node reached by following a succession s of connections from node i is given by Follow[list_, i_, s_List] := Fold[list 〚 #1 〛 〚 #2 〛 &, i, s] The total number of distinct nodes reached by following all possible succession of connections up to length d is given by NeighborNumbers[list_, i_Integer, d_Integer] := Map[Length, NestList[Union[Flatten[list 〚 # 〛 ]] &, Union[list 〚 i 〛 ], d - 1]] For each such list the rules for the network system then specify how the connections from node i should be rerouted. … With rules set up in this way, each step in the evolution of a network system is given by NetEvolveStep[{depth_Integer, rule_List}, list_List] := Block[ {new = {}}, Join[Table[Map[NetEvolveStep1[#, list, i] &, Replace[NeighborNumbers[list, i, depth], rule]], {i, Length[list]}], new]] NetEvolveStep1[s : {___Integer}, list_, i_] := Follow[list, i, s] NetEvolveStep1[{s1 : {___Integer}, s2 : {___Integer}}, list_, i_] := Length[list] + Length[ AppendTo[new, {Follow[list, i, s1], Follow[list, i, s2]}]] The set of nodes that can be reached from node i is given by ConnectedNodes[list_, i_] := FixedPoint[Union[Flatten[{#, list 〚 # 〛 }]] &, {i}] and disconnected nodes can be removed using RenumberNodes[list_, seq_] := Map[Position[seq, #] 〚 1, 1 〛 &, list 〚 seq 〛 , {2}] The sequence of networks obtained on successive steps by applying the rules and then removing all nodes not connected to node number 1 is given by NetEvolveList[rule_, init_, t_Integer] := NestList[(RenumberNodes[#, ConnectedNodes[#, 1]] &)[ NetEvolveStep[rule, #]] &, init, t] Note that the nodes in each network are not necessarily numbered in the order that they appear on successive lines in the pictures in the main text.

Distribution of behavior [in mobile automata] The pictures below show the distributions of transient and of period lengths for the 65,318 mobile automata of the type described here that yield ultimately repetitive behavior.

As another example, the Global Positioning System (GPS) works by having 24 satellites each transmit maximal length sequences from different length 10 LFSRs.

= {}, AllNet[k], q = ISets[b = Map[Table[ Position[d, NetStep[net, #, a]] 〚 1, 1 〛 , {a, 0, k - 1}]&, d]]; DeleteCases[MapIndexed[#2 〚 2 〛 - 1  #1 &, Rest[ Map[Position[q, #] 〚 1, 1 〛 &, Transpose[Map[Part[#, Map[ First, q]]&, Transpose[b]]], {2}]] - 1, {2}], _  0, {2}]]] DSets[net_, k_:2] := FixedPoint[Union[Flatten[Map[Table[NetStep[net, #, a], {a, 0, k - 1}]&, #], 1]]&, {Range[Length[net]]}] ISets[list_] := FixedPoint[Function[g, Flatten[Map[ Map[Last, Split[Sort[Part[Transpose[{Map[Position[g, #] 〚 1, 1 〛 &, list, {2}], Range[Length[list]]}], #]], First[#1]  First[#2]&], {2}]&, g], 1]], {{1}, Range[2, Length[list]]}] If net has q nodes, then in general MinNet[net] can have as many as 2 q -1 nodes. … To obtain such trimmed networks one can apply the function TrimNet[net_] := With[{m = Apply[Intersection, Map[FixedPoint[ Union[#, Flatten[Map[Last, net 〚 # 〛 , {2}]]]&, #]&, Map[List, Range[Length[net]]]]]}, net 〚 m 〛 /. Table[(a_  m 〚 i 〛 )  (a  i), {i, Length[m]}]]

The number of sequences s n of length n that can actually occur is given by Apply[Plus, Flatten[MatrixPower[m, n]]] where the adjacency matrix m is given by MapAt[(1 + #) &, Table[0, {Length[net]}, {Length[net]}], Flatten[MapIndexed[{First[#2], Last[#1]} &, net, {2}], 1]] For rule 32, for example, s n turns out to be Fibonacci[n + 3] , so that for large n it is approximately GoldenRatio n . … If one associates with each possible sequence of length n a number Sum[a i 2 -i , {i, n}] , then the set of sequences that actually occur at a given step form a Cantor set (see note below ), whose Hausdorff dimension turns out to be exactly h .

[No text on this page] Examples of Turing machines with 3 and 4 states in which the maximum number of steps before a computation is finished grows at least exponentially with the length of the input.

But as we saw there, certain underlying rules have the A multiway system in which strings of any length can be generated—but in which only specific sequences of lengths actually occur on any path.