A Single Ant Cell, 40 by 40 WireWorld Cells
Our hero the ant moves on a 2D grid that extends to infinity. His/her moves are simple, enter a square and exit either to the left or the right. All the squares start out empty, but our hero leaves ant droppings if he/she enters an empty square. The rules are very simple.
This could be described as a 4-start, 2D Turing machine with two symbols, but why bother? It's just too simple to explain in English.
From the rules you might not expected very spectacular result, but as usual you really should expect the unexpected. The ant first seems to be making symmetric patterns, then not so symmetric, then random, and finally, voila. After about 10000 moves, he/she turns into a construction engineer and starts building a highway that extends to the stars.
The highway leaves the approximately 50 by 50 area of massive droppings and goes to the SW, SE, NW, and NE, depending upon the direction at time 0. It appears he/she builds the highway even if there were random droppings at the start of the trek.
The WireWorld implementation of Langton's Ant does not contain a central control mechanism, as does my Unary Multiplier. Instead, the logic to control the ant's path and the state of the square is contained within each square. The ant is simulated as an electron that moves from square to square. The state of each square is maintained as a single latch, one per square.
The direction is specified simply by the movement of the ant election. There are four directions
And there are two symbols.
The logic operation that is performed is
Each ant square is made up of four 20 by 20 WireWorld square areas. This basic element is rotated 90, 180 , and 270 degrees, then packed into a 40 by 40 square. Each of the ant squares contain an exact copy of the 40 by 40.
The latch has a loop length of 28 and is flipped by an incoming ant electron. The electron may enter from one of four directions, and so there are four XOR's within the latch. The latch loop length can be made smaller, however, I found that because of the surrounding logic constraints smaller loops did not translate into less overall area.
There are eight AND gates per square, two for each incoming direction.
Much of the concern in the design was in making small cross elements. You will find many crosses. None of them are the normal 3-XOR type. Much latitude was taken in coming up with the crosses since there are never two electrons crossing each other at the same time.
I settle on a 40 by 40 square so that a integer multiple of squares would fit into the board sizes available in MCell. I'm certain the design could fit into something smaller than 40 by 40.
The following layout is a single ant square. The latch is off and the ant electron is entering from the South. The electron will make it through the AND gate to the right and leave the square going to the East. The latch will be set. After the latch is set the electron will be stopped from going to the West.
If the latch had been on, the East going electron would be stopped, the latch reset, and electron then allowed to exit to the West.
The MCell Source Code. You'll need Mirek's Cellabration to run it.
When I started designing the ant I was hopeful that enough ant squares would fit into MCell so that the highway could be started. The highway needs about 50 by 50 ant squares before it begins. With a 40 by 40 WireWorld square per ant square, a total area of 2000 by 2000 would be needed. Too big for MCell.
It is probably possible to find an small initial set of non-blank squares that would start the highway and fit into MCell. I'll leave this for another day.
I have tried three different sizes, 5 by 5, 10 by 10, and 25 by 25. If wrapping is turned off, the ant eventually leaves the universe, and the machine essentially stops, but with wrapping on you can make the ant run forever. When the number of squares becomes finite, eventually you repeat the sequence. Don't hold your breath. Especially for the 25 by 25 this takes a very long time.
I'll show the 5 by 5 here and give the mcl's for all.
You might want to make the electron head white and everything else black for better viewing.
The MCell 5 by 5, the 10 by 10, and the 25 by 25.
Since the original design I've found a better cross. It's the one used by Mark Owen in his computer. It makes the layout a little easier and a little prettier. I have kept the single ant square 40 x 40, again to fit into Mcell and allow wrapping. The inner loop is also kept at 28. 12 is possible, and may lead to a small, clearer, and/or faster design. Have at it.
The MCell Source Code.