Paterson’s Worms
Paterson's worms are a type of finite automaton which exhibit some complex and beautiful behavior from a very simple set of rules. Wikipedia has an overview (slightly out of date); the French version has more current results. I heard about it when Ed Pegg Jr. mentioned it in the 9/15/03 update to MathPuzzle; later he wrote an article on it for the MAA, which got discussed on Slashdot. I'm indebted to Sven Kahrkling for a nice writeup of the results which has since disappeared from the web.
The basic idea is that a worm travels around a triangular (isometric) grid, never retracing its path. At each step, the worm looks around at the 5 adjacent points (the one it just came from is not considered) and sees a particular configuration of taken and open paths. It makes a decision as to which of the open paths to take, and this becomes a rule: every time from then on that the worm sees that same configuration of open and taken paths, it must go the same way as before. All of this is from the worm’s point of view – directions are not absolute but relative to the worm’s direction of travel, i.e. your choices are hard left (120 degrees), soft left (60 degrees), straight ahead, soft right, and hard right. A worm finishes if it reaches a point where there are no open paths; if you think about it you’ll realize that this can only happen at the starting point, and that a worm must return there three times to fill all the paths (it dies on its third return).
As it turns out there are exactly 412 distinct sets of rules, discarding the obvious symmetry of whether the first turn is left or right. That’s many fewer than you’d guess from all the combinations of rules, but many rule sets are equivalent because their worms die before using all the rules. Pictures of all 412 and details of their fates are in this table. 336 are known to finish, 73 are known to be infinite, 2 are almost certain (but not proven) to be infinite, and one remains undecided.
Thanks to a clever algorithm from Tomas Rokicki, based on Hashlife, (his results are here) the computation of a worm's path has been sped up by many orders of magnitude over a simple approach. Below are some results discovered in 20032004, and a few other of my favorites. The meaning of the "rule" column and details on the pictures are with the full list of worms.
Pattern number  Rule  Length / Lower Bound  Pictures (click for larger version)  Comments  Pattern number  Rule  Length / Lower Bound  Pictures (click for larger version)  Comments  
061  1042015  Unknown  lower bound 5.2 * 10^19 

This is the one worm which remains truly undecided. Random swirls like those shown to the left give way to irregular triangles after several billion steps. After more than 10^19 steps, it still shows no sign of falling into any repetitive behavior. 
060  1042010  918,339 
This was the longest known worm prior to 2003. Very similar turbulent structure to #061... but then it ends. 

062  1042020  57,493,855,205,939 

This is the longest worm known to finish. For the first 57,493,855,199,226 steps it is identical to worm 063.  063  1042022  57,493,855,205,905  Only a closeup picture of the center for this one. All other pictures are all the same as for 062  the difference between them is all in the last pixel.  
156  1252121  Almost certainly infinite  lower bound 2.2 * 10^16 

This worm is almost certainly infinite, but a proof would be quite difficult. It builds beautiful fractallike hexagons of everincreasing size. Very similar to worm 323.  323  1525115  Almost certainly infinite  lower bound 4.5 * 10^15 

Very similar to worm # 156, this also builds recursive hexagons. 

185  1420224  16,811,365,528 

The thirdlongest worm. Same as #232, rotated 180 degrees. 
232  1450224  16,811,365,528 

Same as worm #185, rotated 180 degrees. 

379  2014142  3,563,608,205 

Same as worm #402, rotated 120 degrees. 
402  2454142  3,563,608,205 

Same as worm #379, rotated 120 degrees. 

392  2145142  87,996,218 

The closeup picture of this one is neat  although it's mostly a completely filled grid, due to rounding errors in the drawing of the lines there's still a ghost of a Sierpiński triangle pattern visible. 
055  1040512  569,804 
This one has a delicate spider web structure. 

184  1420221  Infinite 
Some early irregular behavior led to this one initially being classified as 'undecided', but Tom Rokicki proved that it does settle into a repeating pattern and is infinite. He also showed that it is the same as worm #231 after the 13th step. 
231  1450221  Infinite 
Same as worm #184 after the 13th step. 

334  1525511  83,618 
A complex structure of overlapping hexagons. 
289  1505111  52,549 
A nice spiderwebby design with near symmetry. 
Pictures for the worms #061 and #062 were created with the new algorithm, and so some of the jagged edges are artifacts of its storage scheme – precise image data cannot be kept at all points. Thanks to Fractint for a nice selection of color palettes. Movies are encoded with Xvid. Higher resolution versions are available via email.
Worm Cubes
For the sixth Gathering for Gardner (G4G6) I created about 200 clear acrylic cubes with pictures of the worms layered inside them to give as an exchange gift to all the other participants.
If you’re interested you can see more pictures and a description of the process.
You can find me at chaffin@gmail.com.