Notes

Chapter 11: The Notion of Computation

Section 6: Emulating Cellular Automata with Other Systems


History [of arithmetic system emulation]

The correspondence between arithmetic systems and register machines was established (using a slightly different approach) by Marvin Minsky in 1962. Additional work was done by John Conway, starting around 1971. Conway considered fraction systems based on rules of the form

FSEvolveList[fracs_, init_, t_] := NestList[First[Select[fracs #, IntegerQ, 1]]&, init, t]

With the choice

fracs = {17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1}

starting at 2 the result for Log[2, list] is as shown below, where Rest[Log[2, Select[list, IntegerQ[Log[2, #]]&]]] gives exactly the primes.

(Compare the discussion of universality in integer equations on page 786.)


From Stephen Wolfram: A New Kind of Science [citation]