Paterson's Worms Revisited

Ed Pegg Jr (ed@mathpuzzle.com)

Initialization

Note: This code could be made vastly more efficient by saving data and acting upon saved data.  Anyone who improves this code should write to me at edp@wolfram.com

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,  
          WormRules  =  {{15, 23, 27, 29, 30}, {5, 4, 2, 1, 
                0}}, 
WormPath  =  {1}},  
        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]]

Text and Explanation

Worms eat sediment, delineating some sort of path.  The 21 November 1969 issue of Science had computer simulations of a few of these worms, in comparison with various fossilized tracks.  The fossilized slimetrails enthralled John Conway and Mike Paterson.  Mike started drawing algorithmic doodles for worms on 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. 

Worm {1,0,4,0,1,5}, pictured below, dies after 57 steps.  Note the bold numbers and blue lines -- 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, based on the given configuration.  The first rule is for a node where none of the other 5 paths have been eaten yet.  All worms that start 0 will go in a straight line, and will never need to make a further decision.  All worms that start 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 rules are added.  It starts with the Black path making a hexagon, then Red, Blue, Yellow, Green, Magenta.  On each turn, the worm disdains an eaten path.  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 the diagram, 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}.

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.

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}]}]];

Some worms will travel in infinite patterns, while others will eventually reach a node where all the paths have been eaten, and die there.  For 30 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.  Due to computer limitations, the study of these worms was abandoned.

32 years later, in October of 2003, Benjamin Chaffin figured out how to run 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.  You can see the results he has on the other worms at his webpage, http://wso.williams.edu/~bchaffin/patersons_worms/.

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.

Show[Graphics[DrawWormPath[{1, 0, 5, 1}]]];

Show[Graphics[DrawWormPath[{1, 5, 2, 5, 4, 1, 2}]]]