Paterson's Worms Revisited

Ed Pegg Jr

Worms eat sediment, delineating some sort of path.  The 21 November 1969 issue of Science had computer simulations of worms, side by side with images of actual worm trail fossils.  The ancient slimetrails enthralled John Conway and Mike Paterson.  Mike started drawing algorithmic doodles for worms eating from an isometric grid (sometimes during lectures). His simple rules led to simple patterns for some worms, but many other doodles wound up being decidedly non-simple.

Mike Beeler, who worked in the MIT Artificial Intelligence Laboratory, became interested in "Paterson's Worms", and came up with a method of rendering their patterns on the cutting-edge green CRTs of the era.  In 1973, Martin Gardner wrote a column: "Fantastic patterns traced by programmed worms."  Inspired by this, Sven Kahrkling developed a web page about isometric worms.

Sven's Worm {1,0,4,2,0,1,5}
Figure 1.  Step 31847646 of Worm {1,0,4,2,0,1,5} by Sven Kahrkling

I should explain how these rules work.  Worm {1,0,4,0,1,5}, pictured below, starts life on a triangular grid, with food on every gridline.  It munches the lines, and chooses where to go based on the lines of food remaining.  On the 57th step, it wanders into a node where no food lines are left, and dies of starvation.  Note the bold numbers and blue lines -- 1 0 4 0 1 5.

How the worm turns
Figure 2.  An explanation of Worm {1,0,4,0,1,5}

In the numbered area, illustrating the rules, the worm can be thought of as the red line, with its head on the center point.  The black lines indicate edges that have already been eaten.  The blue line is the direction the worm will travel in.  The first situation a worm encounters is an empty node, where none of the other 5 paths have been eaten yet.  From this, all worms with a rule starting "1" will make a gentle turn to the right, initially, and will eat a hexagon during the first 6 steps.  For the 7th step, a new configuration is reached.  In the accompanying worm path, the colors change as new configurations are encountered.  It starts with the Black path making a hexagon, then a Red path , Blue, Yellow, Green, and finishing with a Magenta path.  On each turn, the worm disdains an eaten path. 

As a different approach, consider the 28 step life of Worm {1,0,5,1}. Black is the first "new" configuration.  The configuration with five foodpaths happens many times, and direction {1} is always chosen.  The next new configuration is Red, where direction {0} is chosen. In the Green configuration, which will be encountered a few more times, direction {5} is always chosen.  In the Magenta configuration, which only occurs once, direction {1} is taken.  In the Blue configuration, there is no choice.  The worm rule {1,0,5,1} represents the direction chosen for a given configuration, in the order in which those configurations appear.

Worm rule, step by step
Figure 3.  An explanation of Worm {1,0,5,1}

Worms {1,0,4,0,1,5}, {1,0,4,0,1,0,1}, {1,0,4,0,1,0,2}, and {1,0,4,0,1,0,5} all begin in the same way, but they all lead different lives after the 38th step. (Code for this figure is given below)

Four sibling worms
Figure 4.  Four worms with the same initial start.

The four worms above all stop, or die, once they hit a spot where all gridlines have been eaten.  Other worms will travel in infinite patterns, in spiraling hexagons, diamonds or triangles.  Worm {1, 5, 2, 5, 4, 1, 2} is one that makes an intricate trail.

Worm {1, 5, 2, 5, 4, 1, 2}
Figure 5.  A "shoot grower"

For 32 years, the ultimate fate of 11 worms remained unknown: {1,0,4,2,0,1,5}, {1,0,4,2,0,2}, {1,2,5,2,1,2,1}, {1,4,2,0,2,2,1}, {1,4,2,0,2,2,4}, {1,4,5,0,2,2,4}, {1,4,5,0,2,2,1}, {1,5,2,5,1,1,5}, {2,0,1,4,1,4,2}, {2,1,4,5,1,4,2}, {2,4,5,4,1,4,2}.  All of these worms were run for millions of steps, with no end in sight.

In October 2003, Benjamin Chaffin came up with a method for running the more intransigent worms.  As one of the designers of the Pentium 4 chip, he likes finding new methodologies for optimization.  One of his hobbies involves watching how complex dynamics can arise from humble beginnings.

Benjamin: "Solving these required a lot of memory. Each edge is represented by a single bit, with a little wastage to keep my grid square for better performance. I basically have my own paging system, keeping a small number of blocks from a large grid resident at any one time. The resident blocks are memory-mapped to their associated swapfiles, which allows the OS to page in only the parts of the file I touch, rather than reading the whole file into memory when I open it. The Linux filesystem also supports sparse files, so swapfiles only consume the amount of disk space needed by their non-zero data. When disk space gets low I gzip all nonresident swapfiles. Currently my grid is about 1.57 million points on a side; I've run {1,0,4,2,0,2} until it hit the edge (737 billion steps), and {1,0,4,2,0,1,5} is still running at 622 billion."

Within the world Benjamin programmed, worm {2,1,4,5,1,4,2} was the first to fall, after 87996218 steps.  Worms {2,0,1,4,1,4,2} and {2,4,5,4,1,4,2} both needed 3563608205 steps, and wound up making the same pattern, rotated 120 degrees.  Worms {1,4,2,0,2,2,4} and {1,4,5,0,2,2,4} required 16811365528 steps, and made the same pattern, rotated 180 degrees.  An uncompressed version of the {1,4,2,0,2,2,4} worm requires a 100×80 meter LCD screen.

Worm {2,1,4,5,1,4,2}  {2,0,1,4,1,4,2}  {1,4,2,0,2,2,4}
Figure 6. The final states of worms {2,1,4,5,1,4,2}, {2,0,1,4,1,4,2}, and {1,4,2,0,2,2,4}.

As of 22 October 2003, here is the status of Benjamin's computations, with links to images he made with Fractint color palettes.  At Benjamin's site, he has stored many other pictures, data, and movies.

Worm

Lower bound

Population

Comments

{1,0,4,2,0,1,5}

846,957,938,098

???

Random swirls give way to massive triangles.

{1,0,4,2,0,2}

737,767,471,115

???

Grows by irregular contours

{1,2,5,2,1,2,1}

1,165,934,582,199

Probably infinite

Recursive hexagons, looks infinite.

{1,4,2,0,2,2,1}

50,235,144,327

Probably infinite

Hexagon, grows by contours, looks infinite.

{1,4,2,0,2,2,4}

–

16,811,365,528

 

{1,4,5,0,2,2,1}

76,186,350,426

Probably infinite

Hexagon, grows by contours, very similar to {1,4,2,0,2,2,1}.

{1,4,5,0,2,2,4}

–

16,811,365,528

Same as {1,4,2,0,2,2,4}, rotated 180 degrees.

{1,5,2,5,1,1,5}

2,968,339,131,924

Probably infinite

Recursive hexagons, very similar to {1,2,5,2,1,2,1}.

{2,0,1,4,1,4,2}

–

3,563,608,205

 

{2,1,4,5,1,4,2}

–

87,996,218

 

{2,4,5,4,1,4,2}

–

3,563,608,205

Same as {2,0,1,4,1,4,2}, rotated 120 degrees.

Thirty years ago, Martin Gardner asked various questions.  "What happens when barriers are suitably placed? What happens when two or more worms of the same or different species interact?  Are there interesting paths or patterns in three dimensions and higher dimensions?"  So far as I know, no-one answered Martin's questions. 

In 1985, 2D Turing Machines, or Turmites, were investigated by Christopher Langton, Jim Propp, and Rudy Rucker.  Turmites, Turing Machines, and Paterson's Worms have many similarities, in that their behavior on a given step is programmed.  In 2001, I had Ken Krugler's version of Turmites installed on my PDA, and I spent many spare moments watching thousands of different patterns.  The Turmite page at Mathworld contains some of the more interesting patterns I noticed, such as binary counting, and circular spirals. In keeping with his topic of programed paths, Martin Gardner's original column discussed the Logo language. I highly recommend NetLogo, and the chapter about Logo in The Mathematical Explorer.

The ultimate fate of worms {1,0,4,2,0,1,5} and {1,0,4,2,0,2} still seems to be out of reach.  With any luck, they'll be resolved before 2033.

References:

Chaffin, Benjamin.  Paterson’s Worms.  http://wso.williams.edu/~bchaffin/patersons_worms/
Gardner, Martin. Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, 1986.
Kahrkling, Sven.  Worm Paths.  http://www.accessv.com/~sven/worms/
Pegg, Ed Jr.  Turmites.  http://mathworld.wolfram.com/Turmite.html
Rasmussen et al., Discoidal Impressions and Trace-Like Fossils More Than 1200 Million Years Old,  Science 2002 296: 1112-1115
Wolfram, Stephen.  A New Kind of Science. Champaign, IL: Wolfram Media, p. 930, 2002.

Mathematica Code:

A notebook for this column is available at the Mathematica Information Center.

Extra details (see figure):  The possible paths are {5,4,2,1,0}, since path 3 has just been eaten (except at the start). From these choices, let a "1" indicate an eaten path, and let "0" indicate an uneaten path.  Convert the result to a binary number.  For example, in the third rule in figure 2, paths 0 and 2 have been eaten, giving {0,0,1,0,1}, or 00101, the binary for 5.  In sequence pictured above, the converted configurations are {0,2,5,18,12,14}, and the paths taken are {1,0,4,0,1,5}.  In configuration 31, all the paths are eaten, and the worm dies.  In configurations {30,29,27,23,15}, only one path is left, and the worm must travel in direction {0,1,2,4,5}.

Note: This code could be made vastly more efficient by saving data and acting upon saved data.

WormGrid[wp_] := With[{gg = Table[{Cos[a], -Sin[a]}, {a, 0, 5 Pi/3, Pi/3}]}, FoldList[Plus, {0, 0}, Map[gg[[# + 1]] &, Mod[FoldList[Plus, 0, wp], 6]]]];

WormBinary[wp_] := FromDigits[Map[If[#, 1, 0] &, Map[MemberQ[Map[Sort, Partition[WormGrid[wp], 2, 1]], #] &, Map[Sort[Take[WormGrid[Append[wp, #]], -2]] &, {5, 4, 2, 1, 0}]]], 2];

DrawWormPath[worm_] :=
  Module[{Worm = worm, WormPath = {1},
    WormRules = {{15, 23, 27, 29, 30}, {5, 4, 2, 1, 0}}},
    Do[
      wb = WormBinary[WormPath];
      If[wb == 31, Break[]];
      If[MemberQ[WormRules[[1]], wb],
        WormPath = Append[WormPath,
          WormRules[[2, Position[WormRules[[1]], wb][[1, 1]]]]],
        WormPath = Append[WormPath, First[Worm]];
        WormRules = {Append[WormRules[[1]], wb],
            Append[WormRules[[2]], First[Worm]]};
        Worm = Drop[Worm, 1] ], {n, 1, 1000}];
    Graphics[Line[WormGrid[WormPath]], AspectRatio -> Automatic]]

Show[GraphicsArray[{DrawWormPath[{1, 0, 4, 0, 1, 5}],
        DrawWormPath[{1, 0, 4, 0, 1, 0, 1}],
        DrawWormPath[{1, 0, 4, 0, 1, 0, 2}],
        DrawWormPath[{1, 0, 4, 0, 1, 0, 5}]}]];
Comments are welcome.  Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.

Ed Pegg Jr. is the webmaster for mathpuzzle.com.  He maintains the Infocenter for Wolfram Research.