Search NKS | Online
61 - 70 of 272 for Length
![](/common/images/search/spacer.gif)
The tetrahedron network from page 476 is for example given in this representation by
{1 {2, 3, 4}, 2 {1, 3, 4}, 3 {1, 2, 4}, 4 {1, 2, 3}}
The list of nodes reached by following up to n connections from node i are then given by
NodeLists[g_, i_, n_] := NestList[Union[Flatten[# /. g]] &, {i}, n]
The network distance corresponding to the length of the shortest path between two nodes is given by
Distance[g_, {i_, j_}] := Length[NestWhileList[ Union[Flatten[# /. g]] &, {i}, !
A fixed interval of time for the clock—as indicated by the length of the darker gray regions—corresponds to a progressively longer interval of time at rest. … If these were parallel, one would inevitably get not just pure time dilation, but a mixture of it and length contraction.
And indeed, as I will discuss at length in the next chapter , I believe that in general there is a close connection between universality and the appearance of complex behavior.
… But with initial condition (e) of length 8 the pictures show
Rules for symbolic systems known as combinators, first introduced in 1920, and proved universal by the mid-1930s.
With a list s of possible symbols, c[s, n] gives all possible expressions with LeafCount[expr] n :
c[s_, 1] = s; c[s_, n_] := Flatten[ Table[Outer[#1[#2] &, c[s, n - m], c[s, m]], {m, n - 1}]]
There are a total of Binomial[2n - 2, n - 1] Length[s] n /n such expressions. When Length[s] 1 the expressions correspond to possible balanced sequences of opening and closing brackets (see page 989 ).
Implementation [of tag systems]
With the rules for case (a) on page 94 given for example by
{2, {{0, 0} {1, 1}, {1, 0} {}, {0, 1} {1, 0}, {1, 1} {0, 0, 0}}}
the evolution of a tag system can be obtained from
TSEvolveList[{n_, rule_}, init_, t_] := NestList[If[Length[#] < n, {}, Join[Drop[#, n], Take[#, n] /. rule]]&, init, t]
An alternative implementation is based on applying to the list at each step rules such as
{{0, 0, s___} {s, 1, 1}, {1, 0, s___} {s}, {0, 1, s___} {s, 1, 0}, {1, 1, s___} {s, 0, 0, 0}}
There are a total of ((k r + 1 - 1)/(k - 1)) k n possible rules if blocks up to length r can be added at each step and k colors are allowed.
Implementation [of cyclic tag systems]
With the rules for the cyclic tag system on page 95 given as {{1, 1}, {1, 0}} , the evolution can be obtained from
CTEvolveList[rules_, init_, t_] := Map[Last, NestList[CTStep, {rules, init}, t]]
CTStep[{{r_, s___}, {0, a___}}] := {{s, r}, {a}}
CTStep[{{r_, s___}, {1, a___}}] := {{s, r}, Join[{a}, r]}
CTStep[{u_, {}}] := {u, {}}
The leading elements on many more than t successive steps can be obtained directly from
CTList[rules_, init_, t_] := Flatten[Map[Last, NestList[CTListStep, {rules, init}, t]]]
CTListStep[{rules_, list_}] := {RotateLeft[rules, Length[list]],Flatten[rules 〚 Mod[Flatten[Position[list, 1]], Length[rules], 1] 〛 ]}
Proof lengths in logic
As discussed on page 1170 equivalence between expressions can always be proved by transforming to and from canonical form. … In practice it is usually extremely difficult to find the absolute shortest proof of a given logic theorem—and the exact length will depend on what axiom system is used, and what kinds of steps are allowed. … The picture below shows in each of the axiom systems from page 808 the lengths of the shortest proofs found by a version of Waldmeister (see page 1158 ) for all 582 equivalences (see page 818 ) that involve two variables and up to 3 Nand s on either side.
Network constraint systems
Cases (a), (f) and (p) allow all networks that do not contain respectively cycles of length 1 (self-loops), cycles of length 3 or less, and cycles of length 5 or less.
If a particular part of an organism always grows, say, in a simple straight line, then it is fairly easy to imagine that natural selection could succeed in picking out the optimal length for any given environment. … Fourth, if random mutations can only, say, increase or decrease a length, then even if one mutation goes in the wrong direction, it is easy for another mutation to recover by going in the opposite direction.
So given a particular elementary cellular automaton one can then ask what other elementary cellular automata it can emulate using blocks up to a certain length.
… But at least with blocks up to length 25, rule 30 for example is not able to emulate any non-trivial rules at all.
![](/common/images/search/spacer.gif)