**The Ed Pegg Jr's Langton's Ant Binary Counter**

by Nyles Heise

#### Our Ant Can Count Too

As if Langton's Ant didn't have enough to do. Along came
Ed Pegg, Jr. and
asked the poor guy to count!
Ed discovered
that by changing the rules a smidge
the ant's droppings will go through a binary counting sequence. The EPJLA rules
are

- If Mr/Mrs ant finds an empty square
- He/she leaves droppings and exits to the right

- If Mr/Mrs ant finds droppings in the square
- He/she picks up all the droppings and exits without changing direction

Well, it turns out it's easier for the ant to count than build the highway.
First of all, even though this is a 2D Turing machine, only two rows of
Turing cells are ever entered. As the counter passes through its states
the binary numbers appear in the upper row from center to the right,
in the upper row from the center to the left, in the bottom row from the
center to the right, and in the bottom row from the center to the left.
In order to count from 0 to 2^{n}-1 you need two rows of 2*n Turing
cells.
Second, many paths through the Turing cells never occur. Langton's original
ant can enter from the N, S, E, or W, and turn either direction from each
entry point. The EPJLAnt enters only from the W or S in the top row, and only
from the E or N in the bottom row. In the original version many cross
elements are needed, these being of the more difficult WireWorld elements
to construct. Ed's ant needs no crosses.

#### Description of the machine

No technical details, only English.

Three paths through each cell are required. For the top row they are

- Enter from W, exit to E
- Pick up droppings

- Enter from W, exit to S
- Leave droppings

- Enter from S, exit to E
- Leave droppings

For the bottom row, replace E with W, W with E, N with S, and S with N.
If you're a Turing purist please skip the rest of this paragraph. With the
original ant every Turing cell was identical to every other one and identical
when rotated by 1/4 and 1/2 turn. That approach could have been kept with
EPJLA also, but at the expense of many never-to-be-used paths. I took the
simpler approach of minimizing the logic, and using a 180-degree rotated
top row as the bottom row.

#### WireWorld Layout

The following counts from 0 through 31, then repeats. It takes slighly
over 5000 ticks to go from 0 to 0.

##### The EPJLA Binary Counter

Maximize and hit "f" to center.

The MCell Source Code.
You'll need
Mirek's Cellabration to run it.