Chapter 11: The Notion of Computation

Section 6: Emulating Cellular Automata with Other Systems

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 /. {i[r_] :> Table[n + j p -> (Evaluate[Simplify[Prime[r] (# - n) + n + 1]]&), {j, 0, g-1}], d[r_, k_] :> Table[n + j p -> If[Mod[j, Prime[r]]==0, Evaluate[Simplify[(# - n)/Prime[r] + k - 1]]&, (#+1)&], {j, 0, g-1}]}]&, prog]]]}]

The rules for the arithmetic system are represented so that the system from page 122 becomes for example {2, {0 :> (3 #/2 &), 1:>(3(#+1)/2 &)}}. If the register machine starts at instruction n with values regs in its registers, then the corresponding arithmetic system starts with the number n + Table[Prime[i]^reg[[i]], {i, nr}] p - 1 where p = Length[prog]. 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 Stephen Wolfram: A New Kind of Science [citation]