Turing machines [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 , the following will construct a Turing machine which emulates it: CAToTM[rules_] := {{q[a_, b_], c : (0 | 1)}  {q[b, c], {a, b, c} /. rules, 1}, {q[_, _], x}  {p[0], 0, -1}, {p[a_], b : (0 | 1)}  {p[b], a, -1}, {p[_], x}  {q[0, 0], 0, 1}} Given a list of initial cell colors for the cellular automaton, the initial tape for the Turing machine consists of Join[{0, 0}, list, {0, 0}] surrounded by x 's, with the head of the Turing machine on the first 0 in state q[0, 0] .

At any particular step in its evolution, a network system can be thought of a little like an electric circuit, with the nodes of the network corresponding to the components in the circuit, and the connections to the wires joining these components together.

In the 3D pictures in the lower part of the page , networks that arise on successive steps are shown stacked one on top of the other, with the nodes involved in each replacement joined by gray lines.

Correspondence systems Given a list of pairs p with {u, v} = Transpose[p] the constraint to be satisfied is StringJoin[u 〚 s 〛 ]  StringJoin[v 〚 s 〛 ] Thus for example p = {{"ABB", "B"}, {"B", "BA"}, {"A", "B"}} has shortest solution s = {2, 3, 2, 2, 3, 2, 1, 1} . (One can have lists instead of strings, replacing StringJoin by Flatten .) … With r string pairs and n = StringLength[StringJoin[p]] there are 2 n Binomial[n - 1, 2r - 1] possible constraints (assuming no strings of zero length), each being related to at most 8 r!

The second row of pictures illustrates what happens if points closer than distance 1/ √ 2 are joined.

Based on this LE[list_] := Module[{n = Length[list], i = Max[MapIndexed[ #1 - #2 &, PrimePi[list]]] + 1}, CRT[PadRight[ list, n + i], Join[Array[Prime[i + #] &, n], Array[Prime, i]]]] will yield a number x that can be decoded into a list of length n using essentially the so-called Gödel β function Mod[x, Prime[Rest[NestList[NestWhile[# + 1 &, # + 1, Mod[x, Prime[#]]  0 &] &, 0, n]]]]

In 1948 Jan Łukasiewicz found the single axiom version {((a  (b  a))  (((( ¬ c)  (d  ( ¬ e)))  ((c  (d  f))  ((e  d)  (e  f))))  g))  (h  g)} equivalent for example to {(( ¬ a)  (b  ( ¬ c)))  ((a  (b  d))  ((c  b)  (c  d))), a  (b  a)} It turns out to be possible to convert any axiom system that works with modus ponens (and supports the properties of  ) into a so-called equational one that works with equivalences between expressions by using Module[{a}, Join[Thread[axioms  a  a], {((a  a)  b)  b, ((a  b)  b)  (b  a)  a}]] An analog of modus ponens for Nand is {x, x, ⊼ (y ⊼ z)}  z , and with this Jean Nicod found in 1917 the single axiom {(a ⊼ (b ⊼ c)) ⊼ ((e ⊼ (e ⊼ e)) ⊼ ((d ⊼ b) ⊼ ((a ⊼ d) ⊼ (a ⊼ d))))} which was highlighted in the 1925 edition of Principia Mathematica . In 1931 Mordechaj Wajsberg found the slightly simpler {(a ⊼ (b ⊼ c)) ⊼ (((d ⊼ c) ⊼ ((a ⊼ d) ⊼ (a ⊼ d))) ⊼ (a ⊼ (a ⊼ b)))} Such an axiom system can be converted to an equational one using Module[{a}, With[{t = a ⊼ (a ⊼ a), i = #1 ⊼ (#2 ⊼ #2) &}, Join[Thread[axioms  t], {i[t ⊼ (b ⊼ c), c]  t, i[t, b]  b, i[i[a, b], b]  i[i[b, a], a]}]]] but then involves 4 axioms.

The sequence on step t can be obtained from Nest[Join[#, 1 - #] &, {1}, t - 1] . … (c) (Fibonacci-related sequence) The sequence at step t can be obtained from a[t_] := Join[a[t - 1], a[t - 2]]; a[1] = {0}; a[2] = {0, 1} .

[Sequences with] flat spectra Any impulse sequence Join[{1}, Table[0, {n}]] will yield a flat spectrum.

If one does allow dangling connections to be joined within a single template, the results are similar to those discussed so far.