Math Games

2D Turing Machines

Ed Pegg Jr., June 7, 2004

Fifty years ago today, on June 7th, 1954, Alan Turing ate half an apple that had drops of cyanide on it. You can read about him at MacTutor Archives, or the Alan Turing site.  Alan had a tendancy to keep dangerous chemicals in his refrigerator, according to some accounts, so his death may have been an accident.

Alan developed the Turing Machine.  A Turing machine consists of a moving head, which can be in multiple states, and a tape, which can have multiple colors.  {{1,0}->{2,1,-1}, {1,1}->{3,1,1}, {2,0}->{3,1,-1}, {2,1}->{2,1,-1}, {3,0}->{4,1,-1}, {3,1}->{5,0,1}, {4,0}->{1,1,1}, {4,1}->{4,1,1}, {5,0}->{7,1,-1}, {5,1}->{1,0,1}} is a sample Turing Machine, with rules describing how to react to any given state/color combination. Expressed another way, this particular machine looks like this:

An example is of what the machine looks like when run is shown below. The tape starts out as a string of zeros, which soon becomes ones and zeros. The state and position of the head are the first and last number.  To the left, I show the first 1400 steps of this machine.  It continues to run for 47176870 steps before halting.  At the moment, this Busy Beaver discovered in 1990 by Marxen and Buntrock is the longest lived 5 state Turing Machine that reaches a halting state.  Whether this is the is the longest possible 5-state, 2-color halting TM is an unsolved problem.

{{1,{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},15},
{2,{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},14},
{3,{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},13},
{4,{0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},12},
{1,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},13},
{3,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},14},
{5,{0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},15},
{1,{0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},16},
{2,{0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},15},
{3,{0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},14},
{4,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},13},
{4,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},14},
{4,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},15},
{4,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},16},
{4,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},17},
{1,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},18},
{2,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},17},
{2,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},16},
{2,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},15},
{2,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},14},
{2,{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},13}}

Turing Machines need not be constrained to a tape.  In 1985, Christopher Langton considered a Turing machine that would move around on a grid.  The squares of the grid could change color, just like the tape.  The moving head has a state and position, as before.  Also, the direction is stored.  In the simplest two cases, the moving head always changes the color of the underlying cell, and the state never changes.  Also, whenever the underlying cell is turned from white to black, the direction turns to the right.  In Langton's Ant, when the color changes from white to black, the direction turns to the left.  In the Binary Counter, which seems to be my own discovery, the direction doesn't change.

              
Figure 1.  The two simplest interesting 2D Turing machines -- Langton's Ant, and the Binary Counter.

Langton didn't have a sufficiently powerful computer when he first investigated his rule. James Propp had one of the nicer mid-1980's computers, and wrote the simple program to see the first item in Figure 2, below.  He called the eventual resolution a "highway".  Rudy Rucker explored them further, and called the 2D Turing machines "turmites".  After a million steps, the Binary Counter looks like this: . I saw the behavior of this turmite for over a month before I finally realized what it was doing - counting in binary. If the number of colors is increased to ten, decimal counting results.  If the starting position isn't perfectly blank, the Binary Counter turns into a Binary Mess -- this is the most random-looking patterning I've seen within a turmite.

The figures below show a sample of turmites that build highways. The turmites on the left is now called Langton's ant. After 9977 steps, it resolves and starts making a highway with period length 104. The second turmite shows a 2-state 2-color rule that is essentially equivalent to Langton's ant.

Figure 2.  Turmites which make highways.

Highways with other possible orientations are illustrated above. In the third image, the highway gets thicker as it lengthens.

Figure 3. Other highways.

Growth around the edges is frequently seen. The fourth image illustrates a turmite which will grow even within a field of sparse random data. These spirals are quite common. The second turmite in the second row constructs a golden rectangle.

Figure 4. Spiral patterns in 2D Turing Machines.

Chaotic behavior of many different types can happen. For example, the fourth turmite in the first row displays a behavior in which it counts incrementally.

Figure 5.  Chaotic Behavior of varying types.

The number of completely different behaviors that are possible within turmites is incredible.  Here are some more behaviors.

Figure 6.  A variety of patterns formed by turmites.

Turmites don't halt, but they can get trapped in cycles, highways, or various nested behaviors (such as counting). For many of the simplest turmites, it is unknown whether they will resolve.  Here is an unusual turmite produced by the Visions of Chaos program.  Notice the cellular automaton-like structures.

Figure 7.  Cellular automaton like structures within a 2D Turing machine.

It is possible to extend Turing's creation into higher dimensions.  In three dimensions, the moving head can store its state and its last two differing directions.  L. Bunimovich looked at 3D Turing machines in 1996.  H. Hamann extended the study in 2003 (and offers free software to study them).  In 3-space, turmites seem to form highways even more frequently than in 2-space.  Some of the more interesting 3D rules can be seen at Hamann's site. Unsolved question: Does every 3D ant eventually build a highway?

Three of my previous columns touch on Turing machines:  Paterson's Worms Revisited, Multi-state Mazes, and WireWorld Multiplication. As a puzzle, consider the 5-state Turing machine at the start of this column.  In one step, you may choose to not change the underlying color.  How quickly can the machine be halted?  If nothing else, learn this: don't keep dangerous chemicals in your refrigerator.

Mathematica Code:

Many of the pages at mathworld.wolfram.com have extensive notebooks.  Code used for this column can be found at the Turmites entry. Code for the Busy Beaver Turing machine is available from NKS Online Downloadable Programs.

References:

Leonid Bunimovich, "Many Dimensional Lorentz Cellular Automata and Turing Machines," Int Jour of Bifurcation and Chaos, 6 (1996), 1127-1135.

Heiko Hamann, "Definition and Behavior of Langton's Ant in Three Dimensions," Complex Systems, 3 (2003), 263-268.

Christopher Langton, "Studying Artificial Life with Cellular Automata," Physica D, 22 (1986), 120-149.

MacTutor History of Mathematics. "Alan Turing." http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Turing.html.

James Propp, "Further Ant-ics," Mathematical Intelligencer, 16 (1994), 37-42.

Paul Rendell, "A Turing Machine implemented in Conway's Game of Life," http://rendell.server.org.uk/gol/tm.htm.

Softology, Visions of Chaos, http://www.softology.com.au/voc.htm.

Eric W. Weisstein et al. "Turmite." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Turmite.html.

Stephen Wolfram, History of Turing machines, A New Kind of Science, http://www.wolframscience.com/nksonline/page-930c-text.

Zillions of Games, Turing Machine, http://www.zillions-of-games.com/cgi-bin/zilligames/submissions.cgi/21399?do=show;id=10.

Math Games archives.

Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.

Ed Pegg Jr. is the webmaster for mathpuzzle.com. He works at Wolfram Research, Inc. as the administrator of the Mathematica Information Center.