Search NKS | Online
21 - 30 of 98 for Flatten
![](/common/images/search/spacer.gif)
And after n steps the positions of all tips generated are given simply by
Nest[Flatten[Outer[Times, 1 + #, b]] &, {0}, n]
If the rules for a one-element-dependence tag system are given in the form {2, {{0, 1}, {0, 1, 1}}} (compare page 1114 ), the initial conditions for the Turing machine are
TagToMTM[{2, rule_}, init_] := With[{b = FoldList[Plus, 1, Map[Length, rule] + 1]}, Drop[Flatten[{Reverse[Flatten[{1, Map[{Map[ {1, 0, Table[0, {b 〚 # + 1 〛 }]} &, #], 1} &, rule], 1}]], 0, 0, Map[{Table[2, {b 〚 # + 1 〛 }], 3} &, init]}], -1]]
surrounded by 0 's, with the head on the leftmost 2 , in state 1 .
[Converting from CAs with] more colors
Given a rule that involves three colors and nearest neighbors, the following converts each case of the rule to a collection of cases for a rule with two colors:
CA3ToCA2[{a_, b_, c_} d_] := Union[Flatten[Table[Thread[ Partition[Flatten[{l, a, b, c, r} /. coding], 11, 1] 〚 {2, 3, 4} 〛 (d /. coding)], {l, 0, 2}, {r, 0, 2}], 2]]
coding = {0 {0, 0, 0}, 1 {0, 0, 1}, 2 {0, 1, 1}}
The problem of encoding cells with several colors by blocks of black and white cells is related to standard problems in coding theory (see page 560 ).
The rules for the multiway system can then be given for example as
{"AAB" "BB", "BA" "ABB"}
The evolution of the system is given by the functions
MWStep[rule_List, slist_List] := Union[Flatten[ Map[Function[s, Map[MWStep1[#, s] &, rule]], slist]]]
MWStep1[p_String q_String, s_String] := Map[StringReplacePart[s, q, #] &, StringPosition[s, p]]
MWEvolveList[rule_, init_List, t_Integer] := NestList[MWStep[rule, #] &, init, t]
An alternative approach uses lists instead of strings, and in effect works by tracing the internal steps that Mathematica goes through in trying out possible matchings. With the rule from above written as
{{x___, 0, 0, 1, y___} {x, 1, 1, y}, {x___, 1, 0, y___} {x, 0, 1, 1, y}}
MWStep can be rewritten as
MWStep[rule_List, slist_List] := Union[Flatten[Map[ReplaceList[#, rule] &, slist], 1]]
The case shown on page 206 is
{"AB" "", "ABA" "ABBAB", "ABABBB" "AAAAABA"}
starting with {"ABABAB"} .
The following generates explicit lists of n -input Boolean functions requiring successively larger numbers of Nand operations:
Map[FromDigits[#, 2] &, NestWhile[Append[#, Complement[Flatten[Table[Outer[1 - Times[##] &, # 〚 i 〛 , # 〚 -i 〛 , 1], {i, Length[#]}], 2], Flatten[#, 1]]] &, {1 - Transpose[IntegerDigits[Range[2 n ] - 1, 2, n]]}, Length[Flatten[#, 1]] < 2 2 n &], {2}]
The results for 2-step cellular automaton evolution in the main text were found by a recursive procedure.
{dr[r_, n_] d[r, n + First[#2]], dm[r_, z_] d[r, z /. adrs]})&, Flatten[segs]]]
TMCompile[_ z:{_, _, 1}] := f[z, {1, 2}]
TMCompile[_ z:{_, _, -1}] := f[z, {2, 1}]
f[{s_, a_, _}, {ra_, rb_}] := Flatten[{i[3], dr[ra, -1], dr[3, 3], i[ra], i[ra], dr[3, -2], If[a 1, i[ra], {}], i[3], dr[rb, 5], i[rb], dr[3, -1], dr[rb, 1], dm[rb, {s, 0}], dr[rb, -6], i[rb], dr[3, -1], dr[rb, 1], dm[rb, {s, 1}]}]
A blank initial tape for the Turing machine corresponds to initial conditions {1, {0, 0, 0}} for the register machine. … Given the list of successive configurations of the register machine, the steps that correspond to successive steps of Turing machine evolution can be obtained from
(Flatten[Partition[Complement[#, #-1], 1, 2]]&)[ Position[list, {_,{_,_,0}}]]
The program given above works for Turing machines with any number of states, but it requires some simple extensions to handle more than two possible colors for each cell.
Implementation [of finite automata for nested patterns]
Given the rules for a substitution system in the form used on page 931 a finite automaton (as on page 957 ) which yields the color of each cell from the digit sequences of its position is
Map[Flatten[MapIndexed[#2 - 1 Position[rules, #1 _] 〚 1, 1 〛 &, Last[#], {-1}]] &, rules]
This works in any number of dimensions so long as each replacement yields a block of the same cuboidal form.
Representing the strings by lists, one can write rules in the form
{{1, 1, s___} {s, 1, 0}, {1, s___} {s, 1, 0, 1}}
so that the evolution is given by
MWTSEvolve[rule_, list_, t_] := Nest[Flatten[Map[ReplaceList[#, rule] &, #], 1] &, list, t]
This yields a chord such as
Play[Evaluate[Apply[Plus, Flatten[Map[Sin[1000 # t] &, N[2 1/12 ]^Position[list, 1]]]]], {t, 0, 0.2}]
A sequence of such chords can sometimes provide a useful representation of cellular automaton evolution.
Numbering scheme [for Turing machines]
One can number Turing machines and get their rules using
Flatten[MapIndexed[{1, -1} #2 + {0, k} {1, 1, 2} Mod[Quotient[#1, {2k, 2, 1}], {s, k, 2}] + {1, 0, -1} &, Partition[IntegerDigits[n, 2 s k, s k], k], {2}]]
The examples on page 79 have numbers 3024, 982, 925, 1971, 2506 and 1953.
![](/common/images/search/spacer.gif)