Search NKS | Online
71 - 80 of 98 for Flatten
![](/common/images/search/spacer.gif)
Extended versions of (b) and (c) can be obtained from
Flatten[{IntegerDigits[1468, 2], Table[ IntegerDigits[102524348, 2], {n}], IntegerDigits[v, 2]}]
where n is a non-negative integer and v is one of
{1784, 801016, 410097400, 13304, 6406392, 3280778648}
Note that in most cases multiple copies of the same structure can travel next to each other, as seen on page 290 .
Block cellular automata
With a rule of the form {{1, 1} {1, 1}, {1, 0} {1, 0}, {0, 1} {0, 0}, {0, 0} {0, 1}} the evolution of a block cellular automaton with blocks of size n can be implemented using
BCAEvolveList[{n_Integer, rule_}, init_, t_] := FoldList[BCAStep[{n, rule}, #1, #2]&, init, Range[t]] /; Mod[Length[init], n] 0
BCAStep[{n_, rule_}, a_, d_] := RotateRight[ Flatten[Partition[RotateLeft[a, d], n]/.rule], d]
Starting with a single black cell, none of the k = 2 , n = 2 block cellular automata generate anything beyond simple nested patterns.
(One can have lists instead of strings, replacing StringJoin by Flatten .)
… 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.
Sequences of 0's and 1's that have the same property are {1, 0, 1, 0} , {1, 0, 0, 1, 0, 0, 1, 0, 0} or in general Flatten[Table[{1, Table[0, {n - 1}]}, {n}]] .
Arithmetic systems [emulating register machines]
Given the program for a register machine with nr registers in the form on page 896 , an arithmetic system which emulates it can be obtained from
RMToAS[prog_, nr_] := With[{p = Length[prog], g = Product[Prime[j], {j, nr}]}, {p g, Sort[Flatten[MapIndexed[ With[{n = First[#2] - 1}, #1 /.
For all initial conditions this depth seems at first to increase linearly, then to decrease in a nested way according to
FoldList[Plus, 0, Flatten[Table[ {1, 1, Table[-1, {IntegerExponent[i, 2] + 1}]}, {i, m}]]]
This quantity alternates between value 1 at position 2 j and value j at position 2 j - j + 1 .
Given a list of string specifications, a step in the evolution of the multiway system corresponds to
Select[Union[Flatten[Outer[Plus, diff, list, 1], 1]], Abs[#] # &]
Register machines [from cellular automata]
Given the program for a register machine in the form used on page 896 , the rules for a cellular automaton that emulates it can be obtained from
g[i[1], p_, m_] := {{_, p, _} p + 1, {_, 0, p} m + 2, {_, _, p} m + 3}
g[i[2], p_, m_] := {{_, p, _} p + 1, {p, 0, _} m + 5, {p, _, _} m + 6}
g[d[1, q_], p_, m_] := {{m + 2 | m + 3, p, _} q, {m + 1, p, _} p, {0, p, _} p + 1, {_, m + 2 | m + 3, p} m + 1}
g[d[2, q_], p_, m_] := {{_, p, m + 5 | m + 6} q, {_, p, m + 4} p, {_, p, 0} p + 1, {p, m + 5 | m + 6, _} m + 4}
RMToCA[prog_] := With[{m = Length[prog]}, Flatten[ {MapIndexed[g[#1, First[#2], m] &, prog], {{0, 0 | m + 1, m + 3} m + 2, {0, m + 1, _} 0, {0, 0, m + 1} 0, {_, _, x : (m + 1 | m + 3)} x, {_, m + 1 | m + 3, _} m + 2, {m + 6, 0 | m + 4, 0} m + 5, {_, m + 4, 0} 0, {m + 4, 0, 0} 0, {x : (m + 4 | m + 6), _, _} x, {_, m + 4 | m + 6, _} m + 5, {_, x_ , _} x}}]]
If m is the length of the register machine program, then the resulting cellular automaton has m + 7 possible colors for each cell.
In this book such offset lists are always taken to be in the order given by Sort , so that for range r rules in d dimensions the order is the same as Flatten[Array[List, Table[2r + 1, {d}], -r], d - 1] .
Ulam systems
Having formulated the system around 1960, Stanislaw Ulam and collaborators (see page 877 ) in 1967 simulated 120 steps of the process shown below, with black cells after t steps occurring at positions
Map[First, First[Nest[UStep[p[q[r[#1], #2]] &, {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, #] &, ({#, #} &)[{{{0, 0}, {0, 0}}}], t]]]
UStep[f_, os_, {a_, b_}] := {Join[a, #], #} &[f[Flatten[ Outer[{#1 + #2, #1} &, Map[First, b], os, 1], 1], a]]
r[c_]:= Map[First, Select[Split[Sort[c], First[#1] First[#2] &], Length[#] 1 &]]
q[c_, a_] := Select[c, Apply[And, Map[Function[u, qq[#1, u, a]], a]] &]
p[c_]:= Select[c, Apply[And, Map[Function[u, pp[#1, u]], c]] &]
pp[{x_, u_}, {y_, v_}] := Max[Abs[x - y]] > 1 || u v
qq[{x_, u_}, {y_, v_}, a_] := x y || Max[Abs[x - y]] > 1 || u y || First[Cases[a, {u, z_} z]] y
These rules are fairly complicated, and involve more history than ordinary cellular automata.
![](/common/images/search/spacer.gif)