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 and many other CA programs
File extension(s) usually the same as Life

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

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