Langton's ant

Langton's ant, originally called "ant" by its creator, is a two-dimensional cellular automaton, one of the few that can be interpreted as a simple esolang. That however requires any program in it to have only one ant, and that ant is the data pointer.
== History ==
Langton's ant was invented in 1986 by Chris Langton to explore abiogenesis. In 2000, Gajardo, Moreira, & Goles proved that Langton's ant is Turing-complete.
Nowadays, it is a popular cellular automaton, and commonly implemented in CA programs.
== Description ==
Langton's ant works on an infinite two-dimensional array of bits, each program has a pointer (ant) which modifies bits, which can be set anywhere at the start.
Execution is very simple: Each step, the ant moves forward and inverts the bit it was originally on. Then, it checks the bit it's currently on: If the bit is 0, turn right. If it's 1, turn left.
Despite the simplicity, Langton's ant has shown amazing potential for computation, as well as highly complex behavior as a cellular automaton.
== Examples ==
=== Infinite loops (highways) ===
Nearly all random programs eventually settle into an infinite loop, usually into building "highways", which means indefinitely and periodically extending a trail of '1' bits. That includes the empty program: 
==== The empty program ====
Starting with nothing but an ant, it behaves unpredictably for a very long time until finally settling down into a highway. That's highly unique since empty programs usually does nothing.
Showing here the first few steps to demonstrate:
 ^
The bit is 0, so turn right
 >
 1
 1v
 1
 11
 1<
We've hit a 1, turn left
 11
 v1
 11
 01
 <
 11
 01
 ^1
 11
 >01
 11
 11
 1v1
 11
Another 1, turn left
 11
 111
 1>
 11
 111
 10v
=== Line manipulation ===
The ant can travel along a line in multiple different ways, both orthogonal and diagonal ones, shifting them in the process. It is also able to turn corners. Finding something predictable based on them is surprisingly difficult, though.
==== Example 1 ====
 >
 11111111
 1
 1
 1
 1 1
 1 1
 1 1
 11111111
==== Example 2 ====
 11
 1 1
 >1 1
 1 1
 1
 1
 1 11
 1 1 1
 11 1
=== Multiple ants ===
:This section is optional unless you have interest in cellular automaton.
Due to being defined as a CA, most implementations allows more than one ant to exist in a single program. This can cause more interesting stuff to happen.
Here's something surprising:
 1
 >>
 >> 1
(Of course, quite ordinary as a CA: are you interested in them now...?)
And below is an non-highway infinite loop that switches the field of bits into "Golly" and back, and repeat. Since it's too large, an RLE identifiable by Golly is used instead:
 x = 97, y = 56, rule = Langtons-Ant
 68.2A$67.A2.A$66.A4.A$65.A6.A$7.2A4.3A8.3A37.A8.A$6.A2.2A.A10.A3.A35.
 A10.A$5.A7.A10.A3.A2.2A29.A12.A$5.A.4A3.9A2.A2.A3.2A27.A14.A$6.A4.A.
 5A.A2.A.3A2.A2.A27.A16.A$2.2A4.A2.2A5.A.2A.A.A.3A.2A.3A22.A18.A$.A4.
 3A3.A4.A3.2A.A2.A3.4A.2A20.A20.A$A4.6A.2A.A.2A2.A.A3.4A2.A.3A19.A22.A
 $A.2A4.3A.A3.2A.A2.3A.2A2.A.2A.A4.A15.A24.A$.A2.A3.A3.A.2A.2A.2A.4A2.
 A.3A2.3A2.A13.A26.A$3.2A3.A4.A.2A6.A3.A2.2A.5A3.A12.A28.A$3.2A3.A7.A
 2.2A.A4.2A.A3.A.A2.A.A11.A30.A$3.2A3.A4.A.2A5.7A2.4A.A2.A.A10.A32.A$
 3.A2.A.A4.A.2A5.A.2A.2A2.2A.3A2.A.A9.A34.A$3.4A3.A3.2A.3A2.2A2.A4.A.
 2A.2A2.2A8.A36.A$8.3A2.H2.3A.A.4A3.A.A.3A4.2A7.A38.A$8.A4.A.A.2A2.2A
 2.A5.A2.A.3A.2A6.A40.A$4.5A3.3A.A4.A3.A2.3A2.A2.3A.2A5.A42.A$3.A3.2A
 4.2A.2A4.A.A4.A7.A3.A4.A44.A$2.A4.3A.3A3.2A.A.A.2A3.A.3A3.5A3.A46.A$
 2.A3.3A3.A.A.2A.6A2.3A2.A2.2A.2A.A2.A48.A$2.A4.2A3.7A.2A2.6A3.A3.2A.A
 2.A50.A$2.A2.A.A3.3A.A2.A2.A2.A.3A.A.A5.3A.A52.A$2.A2.4A.A2.2A2.A4.A.
 4A3.A.A2.A5.A53.A$2.A6.3A.A2.A.3A.A3.4A4.3A.2A.A54.A$3.A4.A.3A2.A.A.
 4A2.6A.2A.A2.3A54.A$4.4A4.A.A.3A2.2A2.2A3.A.A3.A.A.A.A51.A$11.A4.3A2.
 A.2A4.A.2A2.2A2.4A.A48.A$11.A6.A.A5.3A.A2.3A4.A2.A.A46.A$12.A4.A2.A.A
 4.A2.2A.A.A.A8.A44.A$13.4A4.2A.A.A.A4.5A9.A42.A$22.4A2.A.3A2.2A11.A
 40.A$25.A.A2.2A.F2.A12.A38.A$24.4A.3A4.A13.A36.A$24.A3.A3.A.3A14.A34.
 A$25.A10.A15.A32.A$26.A4.2A2.A17.A30.A$27.4A2.2A19.A28.A$55.A26.A$56.
 A24.A$57.A22.A$58.A20.A$59.A18.A$60.A16.A$61.A14.A$62.A12.A$63.A10.A$
 64.A8.A$65.A6.A$66.A4.A$67.A2.A$68.2A!
The program is stored as a built-in "pattern" in Golly, so you can also find the program in Golly's collection.
== Computational class ==
Langton's ant is Turing-complete. Specifically, it is undecidable whether the ant ever starts to build a highway from a starting configuration. Gajardo, Moreira, & Goles showed that the starting configurations are universal over Boolean circuits, and use this to sketch an automaton which implements universal Turing machines.
== Implementation ==
Langton's ant is commonly implemented on CA programs, as said before. For example, Golly has a built-in implementation of it. Here's how to use it:
When started, click "Control" on the upper-left corner, click "Set Rule...", type "Langtons-Ant" in the textbox, and click OK. Then press . and select an ant direction from the bar that pops up. To draw bits, select the one with a blank black icon.
Things to note about this implementation: It display '0' bits as white and '1' bits as black, and the ant direction displayed is the direction before the turning, so if you want for example to place a > on a '0' bit, you need to place the ant facing upward.
That is just an example, install any modern CA program and it's likely to have Langton's ant built in.
== Variations/Generalization ==
Langton's ant is the most famous of a group of esolangs/CA called turmites, which are similar to Langton's ant in the manner of having one or more pointers which manipulates bits (sometimes bytes), but may have very different behavior.
== External resources ==
* Langton 1986, "Studying artificial life with cellular automata"
* Gajardo, Moreira, & Goles 2000 "Complexity of Langton's Ant"
* Langton's Ant Society, a long-running discussion by Game of Life enthusiasts on variations of the ant
* Langton's ant on Wikipedia
Category:Languages
Category:Before 1993
Category:Turing complete
Category:Turing tarpits
Category:Cell-based
Category:Cellular automata
Category:No IO
Category:Implemented