Search NKS | Online
131 - 140 of 210 for Listable
![](/common/images/search/spacer.gif)
LFSR cryptanalysis
Given a sequence obtained from a length n LFSR (see page 975 )
Nest[Mod[Append[#, Take[#, -n] . vec], 2] &, list, t]
the vector of taps vec can be deduced from
LinearSolve[Table[Take[seq, {i, i + n - 1}], {i, n}], Take[seq, {n + 1, 2n}], Modulus 2]
(An iterative algorithm in n taking about n 2 rather than n 3 steps was given by Elwyn Berlekamp and James Massey in 1968.)
The quantity FoldList[Plus, 0, Table[MoebiusMu[i], {i, n}]] behaves very much like a random walk.
Multiway systems based on numbers
One can consider for example the rule n {n + 1, 2 n} implemented by
NestList[Union[Flatten[{# + 1, 2 #}]] &, {0}, t]
In this case there are Fibonacci[t + 2] distinct numbers obtained at step t .
3D class 4 [cellular automaton] rules
With a cubic lattice of the type shown on page 183 , and with updating rules of the form
LifeStep3D[{p_, q_, r_}, a_List] := MapThread[If[ #1 1 && p ≤ #2 ≤ q || #2 r, 1, 0]&, {a, Sum[RotateLeft[ a, {i, j, k}], {i, -1, 1}, {j, -1, 1}, {k, -1, 1}] - a}, 3]
Carter Bays discovered between 1986 and 1990 the three examples {5, 7, 6} , {4, 5, 5} , and {5, 6, 5} .
The magnetic energy of the system is taken to be
e[s_] := -1/2 Apply[Plus, s ListConvolve[ {{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, s, 2], {0, 1}]
so that each pair of adjacent spins contributes -1 when they are parallel and +1 when they are not. … One marginally more complicated case effectively involving 13 neighbors is
IsingEvolve[list_, t_Integer] := First[Nest[IsingStep, {list, Mask[list]}, t]]
IsingStep[{a_, mask_}] := {MapThread[ If[#2 2 && #3 1, 1 - #1, #1]&, {a, ListConvolve[ {{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, a, 2], mask}, 2], 1 - mask}
where
Mask[list_] := Array[Mod[#1 + #2, 2]&, Dimensions[list]]
is set up so that alternating checkerboards of cells are updated on successive steps.
Implementation [of 2D cellular automata]
An n × n array of white squares with a single black square in the middle can be generated by
PadLeft[{{1}}, {n, n}, 0, Floor[{n, n}/2]]
For the 5-neighbor rules introduced on page 170 each step can be implemented by
CAStep[rule_, a_] := Map[rule 〚 10 - # 〛 &, ListConvolve[{{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}, a, 2], {2}]
where rule is obtained from the code number by IntegerDigits[code, 2, 10] .
For the 9-neighbor rules introduced on page 177
CAStep[rule_, a_] := Map[rule 〚 18 - # 〛 &, ListConvolve[{{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}, a, 2], {2}]
where rule is given by IntegerDigits[code, 2, 18] .
One starts by converting the list of cell colors at each step to a polynomial FromDigits[list, x] .
Lengths of [number] representations
(a) n , (b) Floor[Log[2, n] + 1] , (c) Tr[FixedPointList[Max[0, Ceiling[Log[2, #]]] &, n + 2]] - n - 3 , (d) 2 Ceiling[Log[3, 2n + 1]] , (e) Floor[Log[GoldenRatio, √ 5 (n + 1/2)]] .
Pages 818 and 1175 discuss the sequence of all Nand theorems listed in order of increasing complexity.
Given an initial condition {i, list, n} the initial condition for the 2-color Turing machine is
With[{b = Ceiling[Log[2, k]]}, {i, Flatten[IntegerDigits[list, 2, b]], b n}]
![](/common/images/search/spacer.gif)