If only one color of element ever appears this is the complete condition for a solution—and for r = 2 solutions exist if Apply[Times, d] < 0 and are then of length at least Apply[Plus[##]/GCD[##]&, Abs[d]] . … The undecidability of PCP can be seen to follow from the undecidability of the halting problem through the fact that the question of whether a tag system of the kind on page 93 with initial sequence s ever reaches a halting state (where none of its rules apply) is equivalent to the question of whether there is a way to satisfy the PCP constraint TSToPCP[{n_, rule_}, s_] := Map[Flatten[IntegerDigits[#, 2, 2]] &, Module[{f}, f[u_] := Flatten[Map[{1, #} &, 3u]]; Join[Map[{f[Last[#]], RotateLeft[f[First[#]]]} &, rule], {{f[s], {1}}}, Flatten[ Table[{{1, 2}, Append[RotateLeft[f[IntegerDigits[j, 2, i]]], 2]}, {i, 0, n - 1}, {j, 0, 2 i - 1}], 1]]], {2}] Any PCP constraint can also immediately be related to the evolution of a multiway tag system of the kind discussed in the note below. … The only way is to use the sequence of pairs 2, 3, 3, 2—yet doing this will just produce another BAAB further on.

The stable density after many steps is then given by Solve[3 p (1 - p) 2  p, p] , so that p  1 - 1/ √ 3 or approximately 0.42. The actual density for rule 22 is however 0.35095. … For two steps, one must consider probabilities for all 32 combinations of 5 cells, and for rule 22 the function becomes p (1 - p) 2 (2 + 3p 2 ) , yielding density 0.35012; for three steps it is p (1 - p) 2 (p 4 - 18 p 3 + 41 p 2 - 22 p + 6) yielding density 0.379.

In the limit of infinite size, there is a discrete transition at a density of about 0.592746, with zero probability below the transition to find a connected "percolating" cluster of black cells spanning the lattice, and unit probability above. (For a triangular lattice the critical density is exactly 1/2.) One can also study directed percolation in which one takes account of the connectivity of cells only in one direction on the lattice.

When m = 2 j - 1 is prime, however, even the rightmost digit repeats only with period m - 1 for many values of a . … The reason for this is that n[i + 2]  Mod[65539 2 n[i], 2 31 ]  Mod[6 n[i + 1] - 9 n[i], 2 31 ] so that in computing n[i + 2] from n[i + 1] and n[i] only small coefficients are involved. … The maximal repetition period of 2 n - 1 can be achieved only if Factor[1 + x + x n , Modulus  2] finds no factors.

The rule can be given by specifying a list of cases such as {0, 0, 0}  {1, {1, -1}} , where in each case the second sublist specifies the new relative positions of active cells. With this setup successive steps in the evolution of the system can be obtained from GMAStep[rules_, {list_, nlist_}] := Module[{a, na}, {a, na} = Transpose[Map[Replace[Take[list, {# - 1, # + 1}], rules]&, nlist]]; {Fold[ReplacePart[#, Last[#2], First[#2]]&, list, Transpose[{nlist, a}]], Union[Flatten[nlist + na]]}]

rules 0 and 128 all the cells become white, while in rule 255 all of them become black. … But in other cases, such as rules 2 and 103, it moves to the left or right. … And it turns out that although 24 rules in all yield such nested patterns, there are only three fundamentally different forms that occur.

Labelling each shape and orientation with a different color, the behavior of this system can be reproduced with equal-sized squares using the rule {3  {{1, 0}, {3, 2}}, 2  {{1}, {3}}, 1  {{3, 2}}, 0  {{3}}} starting from initial condition {{3}} .

Tag systems [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 , the following will construct a tag system which emulates it: CAToTS[rules_] := {2, {{s[x_], s[y_]}  {d[x, y], d[x, y]}, {d[w_, x_], d[y_, z_]}  {s[{w, x, y} /. rules], s[{x, y, z} /. rules]}, {s[x_], d[y_, z_]}  {s[0], s[0], s[{0, y, z} /. rules]}, {d[x_, y_], s[z_]}  {s[{x, y, 0} /. rules], s[0], s[0]}}} The initial condition for the tag system that corresponds to a single black cell in the cellular automaton is {s[0], s[0], s[1], s[0], s[0]} .

On row (a) of page 415 the parameter a varies from 1.05 to 1.65, while on row (b) b varies from 0 to 6. The complete surface of the shell is obtained by varying both t and θ in a t {Cos[t] (1 + c (Cos[e] Cos[ θ ] + d Sin[e] Sin[ θ ])), Sin[t] (1 + c (Cos[e] Cos[ θ ] + d Sin[e] Sin[ θ ])), b + c (Cos[ θ ] Sin[e] - d Cos[e] Sin[ θ ])} where c varies from 0.4 to 1.6 on row (c), d from 1 to 4 on row (d) and e from 0 to 1.2 on row (e). … However, in an actual shell material can only be added on the outside of what already exists, and this can be represented by restricting θ to run over only part of the range - π to π .

The right-hand side of the pattern from rule 173R consists three triangles that repeat progressively larger at steps of the form 2 (9 s -1) . Rule 90R has the property that of the diamond of cells at relative positions {{-n,0},{0,-n},{n,0},{0,n}} it is always true for any n that an even number are black.