Search NKS | Online
261 - 270 of 310 for Nest
![](/common/images/search/spacer.gif)
If the curve has a nested form, which appears to be the case in some combinatorial optimization problems, then this scheme can be expected to be at least somewhat effective.
And presumably at some level this is the result of the nested patterns in which erosion occurs.
It is notable that not even nested shapes are common, though they appear in cross-sections of rope (see page 874 ), as well as in address decoder trees on chips—and have recently been used in broadband antennas.
In general NestList[s[r, #]&, i, 2] ⟶ {i, s[r, i], s[r, s[r, i]]} , etc.
And with this setup, t steps of evolution can be found with
SSSEvolveList[rule_, init_s, t_Integer] := NestList[(# /. rule)&, init, t]
Note that as an alternative to having s be Flat , one can explicitly set up rules based on patterns such as s[x___, 1, 0, y___] s[x, 0, 1, 0, y] .
These values can be found using the so-called Lucas-Lehmer test Nest[Mod[# 2 - 2, 2 n - 1] &, 4, n - 2] 0 , and in all cases n itself must be prime.
And in a first approximation these rules can usually be thought of as specifying that every sentence must be constructed from various independent nested phrases, much as in a context-free grammar (see above ). … (One obvious general deviation from the context-free model is that in practice subordinate clauses can never be nested too deep if a sentence is expected to be understood.)
One-element-dependence tag systems [emulating TMs]
Writing the rule {3, {{0, _, _} {0, 0}, {1, _, _} {1, 1, 0, 1}}} from page 895 as {3, {0 {0, 0}, 1 {1, 1, 0, 1}}} the evolution of a tag system that depends only on its first element is obtained from
TS1EvolveList[rule_, init_, t_] := NestList[TS1Step[rule, #] &, init, t]
TS1Step[{n_, subs_}, {}] = {}
TS1Step[{n_, subs_}, list_] := Drop[Join[list, First[list] /. subs], n]
Given a Turing machine in the form used on page 888 the following will construct a tag system that emulates it:
TMToTS1[rules_] := {2, Union[Flatten[rules /.
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}]
In example (c), the elements are again correlated: the growth is by an average of ( √ 5 - 1)/2 ≃ 0.618 elements at each step, and the first elements on alternate steps form the same nested sequence as obtained from the substitution system {1 {1, 0}, 0 {1}} .
![](/common/images/search/spacer.gif)