In base 6, (3/2) n is a cellular automaton with rule {a_, b_, c_}  3 Mod[a + Quotient[b, 2], 2] + Quotient[3 Mod[b, 2] + Quotient[c, 2], 2] (Note that this rule is invertible.)

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.

3n+1 problem as cellular automaton If one writes the digits of n in base 6, then the rule for updating the digit sequence is a cellular automaton with 7 possible colors (color 6 works as an end marker that appears to the left and right of the actual digit sequence): {a_, b_, c_}  If[b  6, If[EvenQ[a], 6, 4], 3 Mod[a, 2] + Quotient[b, 2] /. 0  6 /; a  6] The 3n+1 problem can then be viewed as a question about the existence of persistent structure in this cellular automaton.

(For multiplier m in base k , the relative frequencies of pairs {i, j} are given by Quotient[a i - j - 1 + m, k] - Quotient[m i - j - 1, k] .)

The value of the cell at position n from the end of row t is thus the n th digit of m t , or Mod[Quotient[m t , k n ], k] .

MapIndexed[ #1  First[#2] &, Union[Map[# 〚 1, 1 〛 &, #]]] &[ With[{b = Ceiling[Log[2, k]] - 1}, Flatten[Table[ {Table[{Table[{{m, i, n, d}, c}  {{m, Mod[i, 2 n - 1 ], n - 1, d}, Quotient[i, 2 n - 1 ], 1}, {n, 2, b}, {i, 0, 2 n - 1}], Table[{ {m, i, 1, d}, c}  {{m, -1, 1, d}, i, d}, {i, 0, 1}], Table[ {{m, -1, n, d}, c}  {{m, -1, n + 1, d}, c, d}, {n, b - 1}], {{m, -1, b, d}, c}  {{0, 0, m}, c, d}}, {d, -1, 1, 2}], Table[{{i, n, m}, c}  {{ i + 2 n c, n + 1, m}, c, -1}, {n, 0, b - 1}, {i, 0, 2 n - 1}], With[{r = 2 b }, Table[ If[i + r c ≥ k, {}, Cases[rule, ({m, i + r c}  {x_, y_, z_})  {{i, b, m}, c}  {{x, Mod[y, r], b, z}, Quotient[y, r], 1})]], {i, 0, r - 1}]]}, {m, s}, {c, 0, 1}]]]] Some of these states are usually unnecessary, and in the main text such states have been pruned.

(h) Mod[Quotient[s, 2 n ], 2] extracts the digit associated with 2 n in the base 2 digit sequence of s .

When m itself divides k , the cellular automaton rule is {_, b_, c_}  m Mod[b, k/m] + Quotient[c, k/m] ; in other cases the rule can be obtained by composition.

The evolution of the arithmetic system is given by ASEvolveList[{n_, rules_}, init_, t_] := NestList[(Mod[#, n] /. rules)[#] &, init, t] Given a value m obtained in the evolution of the arithmetic system, the state of the register machine to which it corresponds is {Mod[m, p] + 1, Map[Last, FactorInteger[ Product[Prime[i], {i, nr}] Quotient[m, p]]] - 1} Note that it is possible to have each successive step involve only multiplication, with no addition, at the cost of using considerably larger numbers overall.

From various number-theoretical results many relations can readily be encoded as integer equations: (a  0 ∨ b  0) ↔ a b  0 (a  0 ∧ b  0) ↔ a + b  0 a < b ↔ b  a + c + 1 a  Mod[b, c] ↔ (b  a + c d ∧ a < c) a  Quotient[b, c] ↔ (b  a c + d ∧ d < c) a  Binomial[b, c] ↔ With[{n = 2 b + 1}, (n + 1) b  n c (a + d n) + e ∧ e < n c ∧ a < n] a  b! ↔ a  Quotient[c b , Binomial[c, b]] a  GCD[b, c] ↔ (b c > 0 ∧ a d  b ∧ a e  c ∧ a + c f  b g) a  Floor[b/c] ↔ (a c + d  b ∧ d < c) PrimeQ[a] ↔ (GCD[(a - 1)!… The simplest known way of doing this (see note below ) involves a degree 8 equation with 60 variables: a  b c ↔ α [d, 4 + b e, 1 + z] ∧ α [f, e, 1 + z] ∧ a  Quotient[d, f] ∧ α [g, 4 + b, 1 + z] ∧ e  16 g(1 + z) λ [a_, b_, c_] := Module[{x}, 2 a + x 1  c ∧ (Mod[b - a, c]  0 ∨ Mod[b + a, c]  0)] α [a_, b_, c_] := Module[{x}, x 1 2 - b x 1 x 2 + x 2 2  1 ∧ x 3 2 - b x 3 x 4 + x 4 2  1 ∧ 1 + x 4 + x 5  x 3 ∧ Mod[x 3 , x 1 2 ]  0 ∧ 2x 4 + x 7  b x 3 ∧ Mod[-b + x 8 , x 7 ]  0 ∧ Mod[-2 + x 8 , x 1 ]  0 ∧ x 8 - x 11  3 ∧ x 12 2 - x 8 x 12 x 13 + x 13 2  1 ∧ 1 + 2 a + x 14  x 1 ∧ λ [a, x 12 , x 7 ] ∧ λ [c, x 12 , x 1 ]] (This roughly uses the idea that solutions to Pell equations grow exponentially, so that for example x 2  2y 2 + 1 has solutions With[{u = 3 + 2 √ 2 }, (u n + u -n )/2] .)