Langton's ant

From Esolang
Jump to navigation Jump to search
Not to be confused with ant.
Langton's ant
Designed by Chris Langton
Appeared in 1986
Computational class Turing-complete
Reference implementation built-in CA in Golly
File extension(s) {{{files}}}

Langton's ant, originally known as "ant", is a two-dimensional cellular automaton invented in 1986 by Chris Langton to explore abiogenesis. In 2000, Gajardo, Moreira, & Goles proved that Langton's ant is Turing-complete.

Conventions

This article treats Langton's ant as an esolang instead of a cellular automaton, so everything in this article assumes that only one ant per program is allowed.

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

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. For example, Golly has a built-in implementation of 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 turn, so if you want for example to place a > on a '0' bit, you need to place the ant facing upward.

Variations

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

Retrieved from "https://esolangs.org/w/index.php?title=Langton%27s_ant&oldid=143173"