Search NKS | Online
911 - 920 of 1022 for Rule
![](/common/images/search/spacer.gif)
Yet most of the systems in this book involve just simple discrete elements with definite rules.
And as mentioned on page 1077 , going back to the 1950s some image processing systems have been based on particular families of 2D cellular automaton rules.
Note that the excluded pairs of digits are in exact correspondence with the positions of which squares are 0 in the underlying rules for the substitution systems.
Such systems are like cellular automata on networks, except for the fact that when they are set up each node has a rule that is randomly chosen from all 2 2 s possible ones with s inputs.
Axel Thue considered versions with two-way rules (analogous to semigroups, as discussed below) in 1912, leading to the name semi-Thue systems sometimes being used for general multiway systems.
Discreteness in space
Many systems with continuous underlying rules generate discrete cellular structures in space.
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. Assuming that the upper string is never shorter than the lower one, the rules for the relevant tag system are given simply by
Apply[Append[#2, s___] Prepend[#1, s] &, p, {1}]
In the case of example (e) the existence of a solution of length 24 can then be seen to follow from the fact that MWTSEvolve[rule, {{"B"}}, 22] contains {"B","A"} .
And even though for example elaborate symmetry rules have been devised, nothing like cellular automaton rules appear to have ever arisen. The results in this book now show that such rules can capture the essence of many complex processes that occur in nature—so that even though they lack historical context such rules can potentially provide a basis for forms of ornament that are familiar as idealizations of nature. … The triangles are all equilateral, with the result that at a given step several different sizes of triangles occur—though the basic structure of the pattern is still the same as from the rule 90 cellular automaton.
[Cryptographic] properties of rule 30
Rule 30 can be written in the form p ⊻ (q ∨ r) (see page 869 ) and thus exhibits a kind of one-sided additivity on the left.
In the most direct approach, one takes a string and at each step just applies the underlying rules or axioms of the multiway system. But as soon as one knows that there is a path from a string u to a string v , one can also imagine applying the rule u v to any string—in effect like a lemma.
![](/common/images/search/spacer.gif)