Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« Phi and pi calculators | Main | First c/5 greyship, and a new c/3 »

2011 January 10

Engineered Objects
Turing machines

This is the fourth article in a projected series of twenty or so, covering the last couple of years of Life discoveries. After this profusion of old news, LifeNews will return to its former state of publishing recent discoveries. Or so we hope...

Approximately one decade after implementing his original Turing machine in GoL, Paul Rendell has built a universal version. Universal Turing machines are those capable of emulating any other Turing machine, depending only on the initial input on the tape.

image

A particularly small universal Turing machine (henceforth abbreviated to UTM) is the 7-state 4-symbol machine by Minsky. There even exists a UTM with only two states and three symbols, discovered by Stephen Wolfram. However, the initial 'program' must be infinite, so this is of relatively little practical importance. Indeed, Rendell decided that the program should be as compact and intuitive as possible, and fit within the limitation of his architecture.

Paul Rendell's UTM has 13 states and 8 symbols, fitting comfortably within the (16,8) limitation of his Life architecture. There are actually 16 logical states, but they can be compressed into 13 actual states, by allowing a particular state to serve two distinct, non-interfering purposes.

A more detailed description of Rendell's UTM can be found in Chapter 26 of Game of Life Cellular Automata.

Despite the machine being universal, the Life pattern, strictly speaking, is not. For a Turing machine to be universal, it must have access to an unlimited storage tape; otherwise, it is a weaker machine known as a linear-bounded automaton. There are two approaches to creating an unlimited storage tape in GoL. One is to write into empty space, as used in Adam P. Goucher's irrational number calculators (see previous post). Paul Rendell decided on a more impressive and ambitious approach: to build a puffer that extends the stacks, faster than they can be used by the Turing machine!

The stack constructor consists of a number of orthogonal rakes, travelling in two perpendicular directions, which incrementally extend the tapes via glider syntheses. The rakes insert the gliders into convoys using the standard kickback reaction.

image
One of 333 identical rakes in the stack constructor

As universal Turing machines can emulate any other Turing machine, they can also be programmed to emulate themselves. An example of a universal Turing machine (henceforth abbreviated to UTM) is given in The Emperor's New Mind, by Roger Penrose. Penrose's machine is rather complex, with a self-interpreting program of 5495 bits! Compare this with John Tromp's Binary Lambda Calculus, which has a self-interpreter of only 210 bits.

The state transition table of Rendell's UTM is displayed below:

image