[Golly-test] Langton's ant: correction, inverse, examples

[Dean H. <dea...@ya...>]

First, a correction:  On 10/6 I sent a rule file, "edges.table", which was supposed to kill all cells which have the same state as their 4 neighbors.  Unfortunately it doesn't work for states >= 16.  I had added line breaks in the middle of a "var" definition to make it more readable, and Golly only looked at the first line, without giving any error messages.  A corrected version is attached.  (I didn't notice the problem at first, since most of my Langton's ant rules had length <= 16, so there could only be one cell in a larger state, namely the ant.)


Second, a Langton's ant CA is reversible, if there's only one ant.  I.e. if you know generation n+1 you can figure out what generation n must be.  I've written a Python script called "Langtons-Inverse-gen.py" which creates a .table file for the inverse.  This is my first Python program; I basically copied Tim's script and made appropriate modifications.

As an example, run Tim's script "Langtons-Ant-gen.py" and enter a rule string, say LRR.  This creates a single ant.  Advance the pattern some number of generations, say 100.  Then run my script, and enter the same rule string.  The pattern is unchanged, but the generation number is reset to 0.  Advance the pattern 100 more generations and you'll get back the original ant.  It's kind of fun to watch.  (It's also useful, for figuring out exactly when some event occurred.)

Note that the inverse ant for a given rule string is equivalent to a normal ant for the reversed rule string.  However, the states and orientation are different, so you can't just use Tim's script to create the inverse.


Finally, here are a few more examples of Langton's ant rules that I find interesting:

LLRRRLRRRRRRRL :  Earlier I mentioned LLRRRLRRRRR, which produces fractal-like structures, but overwrites them with chaotic regions.  Many variants, obtained by adding L's and R's to the end of the rule string, also grow the fractals.  I've tried to find one which grows them predictably forever, but I've failed.  This rule is the best that I've found.  After behaving somewhat chaotically for 30,304,612 gens, it seems to settle down, producing fractals in all 4 quadrants.  I've run it for 8.9*10^11 gens, and it shows no sign of going chaotic again.  But the fractals are complicated; I see no hope of giving a complete definition of their shape, and I can't guarantee that they'll grow forever.

LLRLLLRRRRR :  This spends most of its time being chaotic up to about gen 202,119,800, visiting cells an average of about 190 times each.  After that it grows steadily at 1/4 cell per generation, becoming predictable around gen 1.932*10^9.  It fills the plane with a square of cells in state 4, except for some stripes along the diagonals.

LRRLLLLRLRRRLLL :  Up to about gen 1.039*10^10, this fills a large region with state 4 (at 1/4 cell per gen), with brief episodes of chaos.  After that, the ant crawls back, along some horizontal and vertical striped paths, to a chaotic region at the origin.  At this point, Golly's simulation slows down, and I've only run it for about 3*10^9 more gens, during which time it looks very chaotic.  But it doesn't behave like a typical random walk; it stays much closer to the origin than it should.  So there must be some structure to the chaos that I don't understand.

LRRRLRLLLLRRLLRLLLL :  This ant fills much of the plane with cells of state 6; the shape of the region varies unpredictably.  It also fills some regions with a checkerboard pattern of states 6 and 8, and others with more complex spatially periodic patterns.  It produces many diagonal highways through the cells of state 6, so usually it escapes fairly quickly from chaotic regions and gets back to the boundary.  (It's somewhat similar to LRRRRRLLR in that regard.)  But not always; for example, around gens 1.32351*10^9 to 1.47568*10^9 it goes chaotic at the intersection of 3 checkerboard regions (about 430 units east and 1900 north of the origin) and doesn't escape until the chaotic region grows to meet a neighboring state-6 region.  I've run this for more than 3*10^12 gens, and it's still fascinating.  My guess is that, asymptotically, the time spent in chaotic parts divided by the total time approaches zero.

Dean Hickerson