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,[1] is a two-dimensional cellular automaton. It is an example of a local cellular automaton: changes only occur near a designated cell, called the ant. As the ant moves from cell to cell, it acts like a data pointer.

History

Langton's ant was invented in 1986 by Chris Langton to explore abiogenesis.[1] In 2000, Gajardo, Moreira, & Goles proved that Langton's ant is Turing-complete.

Today, it is a popular cellular automaton commonly implemented in CA programs.

Description

Langton's ant operates on an infinite two-dimensional array of cells where each cell contains a bit. Each program has a pointer, the ant, which modifies bits. The ant is oriented in one of four cardinal directions. The ant may be located anywhere at the start. The ant may also be oriented in any direction, or equivalently the array of cells can be rotated to line up with a fixed orientation. We will say that the cell currently pointed to by the ant is the ant cell.

Execution proceeds according to a single rule with three phases.

  1. The ant cell is inverted.
  2. The ant moves forward, pointing to the next cell in the direction that it is currently oriented.
  3. The ant turns according to the ant cell: turn right if the bit is 0 or turn left if the bit is 1.

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 are interested in cellular automata.

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.2A67ドル.A2.A66ドル.A4.A65ドル.A6.A7ドル.2A4.3A8.3A37.A8.A6ドル.A2.2A.A10.A3.A35.
A10.A5ドル.A7.A10.A3.A2.2A29.A12.A5ドル.A.4A3.9A2.A2.A3.2A27.A14.A6ドル.A4.A.
5A.A2.A.3A2.A2.A27.A16.A2ドル.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.A3ドル.2A3.A4.A.2A6.A3.A2.2A.5A3.A12.A28.A3ドル.2A3.A7.A
2.2A.A4.2A.A3.A.A2.A.A11.A30.A3ドル.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.A3ドル.4A3.A3.2A.3A2.2A2.A4.A.
2A.2A2.2A8.A36.A8ドル.3A2.H2.3A.A.4A3.A.A.3A4.2A7.A38.A8ドル.A4.A.A.2A2.2A
2.A5.A2.A.3A.2A6.A40.A4ドル.5A3.3A.A4.A3.A2.3A2.A2.3A.2A5.A42.A3ドル.A3.2A
4.2A.2A4.A.A4.A7.A3.A4.A44.A2ドル.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.A2ドル.A4.2A3.7A.2A2.6A3.A3.2A.A
2.A50.A2ドル.A2.A.A3.3A.A2.A2.A2.A.3A.A.A5.3A.A52.A2ドル.A2.4A.A2.2A2.A4.A.
4A3.A.A2.A5.A53.A2ドル.A6.3A.A2.A.3A.A3.4A4.3A.2A.A54.A3ドル.A4.A.3A2.A.A.
4A2.6A.2A.A2.3A54.A4ドル.4A4.A.A.3A2.2A2.2A3.A.A3.A.A.A.A51.A11ドル.A4.3A2.
A.2A4.A.2A2.2A2.4A.A48.A11ドル.A6.A.A5.3A.A2.3A4.A2.A.A46.A12ドル.A4.A2.A.A
4.A2.2A.A.A.A8.A44.A13ドル.4A4.2A.A.A.A4.5A9.A42.A22ドル.4A2.A.3A2.2A11.A
40.A25ドル.A.A2.2A.F2.A12.A38.A24ドル.4A.3A4.A13.A36.A24ドル.A3.A3.A.3A14.A34.
A25ドル.A10.A15.A32.A26ドル.A4.2A2.A17.A30.A27ドル.4A2.2A19.A28.A55ドル.A26.A56ドル.
A24.A57ドル.A22.A58ドル.A20.A59ドル.A18.A60ドル.A16.A61ドル.A14.A62ドル.A12.A63ドル.A10.A$
64.A8.A65ドル.A6.A66ドル.A4.A67ドル.A2.A68ドル.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

Definition. A block is a finite rectangle of cells in a particular configuration.

Each block has a width and a height.

One route to universality is via Boolean circuits. Gajardo, Moreira, & Goles showed that any Boolean circuit can be represented:

Theorem (Universality for Boolean circuits). Any finite Boolean circuit can be represented by a block and a starting position. (Gajardo, Moreira, & Goles, 2000)[2]

There is a polynomial-time algorithm which embeds a given Boolean circuit into cells. There are polynomial bounds on the width and height of blocks generated by this algorithm. It is P-complete whether a Boolean circuit satisfies a given assignment of initial truth values, since every gate must be visited at least once. The outcome of evaluating a circuit is to physically locate the ant at a particular output cell. Therefore:

Theorem (P-hardness). Given a block, a starting position, and a chosen cell, it is P-hard whether the ant ever visits the chosen cell. (Gajardo, Moreira, & Goles, 2000)

That is, if we think of a block as a Boolean circuit then it could be a P problem whether the ant visits a certain cell because the ant might have to evaluate the entire circuit first! Gajardo, Moreira, & Goles theorize that an NP-complete problem might be embeddable into a block as well, mirroring results in other cellular automata and video games.

Gajardo, Moreira, & Goles sketched an automaton built from Boolean circuits which implements universal Turing machines. From this sketch, it is shown that Langton's ant is Turing-complete; it should be possible to encode any Turing machine as a block of circuitry and a potentially-infinite initial pattern surrounding the circuit. Specifically, given an infinite initial configuration and a starting point for the ant, some facts are undecidable:

Theorem (Undecidability of Printing). It is undecidable whether, given an infinite initial configuration and a starting point, a particular block is ever constructed anywhere. (Gajardo, Moreira, & Goles, 2000)

Corollary (Undecidability of Halting). It is undecidable whether, given an infinite initial configuration and a starting point, a highway longer than some fixed bound is ever constructed anywhere. (Gajardo, Moreira, & Goles, 2000)

Implementation

Langton's ant has many implementations. For example, Golly has a built-in implementation. 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.

Generalizations

Langton's ant is a member of a family of cellular automata known as turmites.

External resources

References

  1. ↑ 1.0 1.1 C. Langton, 1986. Studying artificial life with cellular automata. https://deepblue.lib.umich.edu/handle/2027.42/26022
  2. ↑ Gajardo, Moreira, & Goles, 2000. Complexity of Langton's ant. https://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf
Retrieved from "https://esolangs.org/w/index.php?title=Langton%27s_ant&oldid=170632"