Search NKS | Online
341 - 350 of 1022 for Rule
![](/common/images/search/spacer.gif)
Because of the reversibility of the underlying rule, every collision must be able to occur equally well when its initial and final states are interchanged.
Thus, for example, rule 30 on page 27 corresponds to the list {0, 0, 0, 1, 1, 1, 1, 0} . (The numbering of rules is discussed on page 53 .) In general, the list for a particular rule can be obtained with the function
ElementaryRule[num_Integer] := IntegerDigits[num, 2, 8]
Given a rule together with a list representing the state a of a cellular automaton at a particular step, the following simple function gives the state at the next step:
CAStep[rule_List, a_List] := rule 〚 8 - (RotateLeft[a] + 2 (a + 2 RotateRight[a])) 〛
A list of states corresponding to evolution for t steps can then be obtained with
CAEvolveList[rule_, init_List, t_Integer] := NestList[CAStep[rule, #]&, init, t]
Graphics of this evolution can be generated using
CAGraphics[history_List] := Graphics[ Raster[1 - Reverse[history]], AspectRatio Automatic]
And having set up the definitions above, the Mathematica input
Show[CAGraphics[CAEvolveList[ ElementaryRule[30], CenterList[103], 50]]]
will generate the image:
The description just given should be adequate for most cellular automaton simulations.
Then, for example, the rule for the Turing machine shown on page 78 can be given as
{{1, 0} {3, 1, -1}, {1, 1} {2, 0, 1}, {2, 0} {1, 1, 1}, {2, 1} {3, 1, 1}, {3, 0} {2, 1, 1}, {3, 1} {1, 0, -1}}
where the left-hand side in each case gives the state of the head and the value of the cell under the head, and the right-hand side consists of a triple giving the new state of the head, the new value of the cell under the head and the displacement of the head.
With a rule given in this form, a single step in the evolution of the Turing machine can be implemented with the function
TMStep[rule_List, {s_, a_List, n_}] /; (1 ≤ n ≤ Length[a]) := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a 〚 n 〛 }, rule]]
The evolution for many steps can then be obtained using
TMEvolveList[rule_, init_List, t_Integer] := NestList[TMStep[rule, #]&, init, t]
An alternative approach is to represent the complete state of the Turing machine by MapAt[{s, #}&, list, n] , and then to use
TMStep[rule_, c_] := Replace[c, {a___, x_, h_List, y_, b___} Apply[{{a, x, #2, {#1, y}, b}, {a, {#1, x}, #2, y, b}} 〚 #3 〛 &, h /. rule]]
The result of t steps of evolution from a blank tape can also be obtained from (see also page 1143 )
s = 1; a[_] = 0; n = 0;
Do[{s, a[n], d} = {s, a[n]} /. rule; n += d, {t}]
For additive rules like rule 90 and rule 150 every possible configuration of the initial block leads to a different configuration for the patch, so that h tx = 2r = 2 . … For rule 30, h μ tx < 1.155 , and there is some evidence that its true value may actually be 1. For rule 18 it appears that h μ tx = 1 , while for rule 22, h μ tx and for rule 54 h μ tx .
Implementation [of network substitution rules]
For many practical purposes the best representation for networks is the one given on page 1031 . … The rule at the top of page 509 must therefore be written out as
and this corresponds to the Mathematica rule
u[i1_ v[i2_, i3_, i4_], i3_ v[i1_, i5_, i6_], i4_ v[i1_, i7_, i8_]] u[i1 v[i2, new[1], new[2]], new[1] v[i1, new[2], i3], new[2] v[i1, new[1], i4], i3 v[new[1], i5, i6], i4 v[new[2], i7, i8]]
(Strictly there also need to be additional rules to cover where for example nodes 3 and 4 are actually the same.) With rules in this form the network update is simply
NetStep[rule_, net_]:= Block[{new}, net /. rule /. new[n_] n + Apply[Max, Map[First, net]]]
Note that just as we discussed for strings on page 1033 the direct use of /. here corresponds to a particular scheme for applying the update rule.
Implementation [of hexagonal cellular automata]
One can treat hexagonal lattices as distorted square lattices, updated according to
CAStep[rule_List, a_] := Map[rule 〚 14 - # 〛 &, a + 2 ListConvolve[{{1, 1, 0}, {1, 0, 1}, {0, 1, 1}}, a, 2], {2}]
where rule = IntegerDigits[code, 2, 14] . On this page the rule used is code 16382; on page 371 it is code 10926.
(In analogy with cellular automata, this rule can be labelled {35,57} where the first number refers to colors, and the second displacements.) With a rule given in this form, each step in the evolution of the mobile automaton corresponds to the function
MAStep[rule_, {list_List, n_Integer}] /; (1 < n < Length[list]) := Apply[{ReplacePart[list, #1, n], n + #2}&, Replace[Take[list, {n - 1, n + 1}], rule]]
The complete evolution for many steps can then be obtained with
MAEvolveList[rule_, init_List, t_Integer] := NestList[MAStep[rule, #]&, init, t]
(The program will run more efficiently if Dispatch is applied to the rule before giving it as input.)
For the mobile automaton on page 73 , the rule can be given as
{{1, 1, 1} {{0, 0, 0}, -1}, {1, 1, 0} {{1, 0, 1}, -1}, {1, 0, 1} {{1, 1, 1}, 1}, {1, 0, 0} {{1, 0, 0}, 1}, {0, 1, 1} {{0, 0, 0}, 1}, {0, 1, 0} {{0, 1, 1}, -1}, {0, 0, 1} {{1, 0, 1}, 1}, {0, 0, 0} {{1, 1, 1}, 1}}
and MAStep must be rewritten as
MAStep[rule_, {list_List, n_Integer}] /; (1 < n < Length[list]) := Apply[{Join[Take[list, {1, n - 2}], #1, Take[list, {n + 2, -1}]], n + #2}&, Replace[Take[list, {n - 1, n + 1}], rule]]
[No text on this page]
Complex behavior in the rule 110 cellular automaton starting from a random initial condition.
But what about other rules? The facing page and the one that follows show patterns produced by two-dimensional cellular automata with a sequence of different rules.
The underlying rules for the cellular automaton used in the picture below are precisely reversible. … The specific cellular automaton used here is rule 122R.
![](/common/images/search/spacer.gif)