# Langton’s ant – Wikipedia

*by*Phil Tadros

From Wikipedia, the free encyclopedia

Two-dimensional Turing machine with emergent conduct

**Langton’s ant** is a two-dimensional universal Turing machine with a quite simple algorithm however advanced emergent conduct. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells.^{[1]} The universality of Langton’s ant was confirmed in 2000.^{[2]} The concept has been generalized in a number of alternative ways, equivalent to turmites which add extra colours and extra states.

Squares on a airplane are coloured variously both black or white. We arbitrarily establish one sq. because the “ant”. The ant can journey in any of the 4 cardinal instructions at every step it takes. The “ant” strikes in keeping with the principles beneath:

- At a white sq., flip 90° clockwise, flip the colour of the sq., transfer ahead one unit
- At a black sq., flip 90° counter-clockwise, flip the colour of the sq., transfer ahead one unit

Langton’s ant may also be described as a cellular automaton, the place the grid is coloured black or white and the “ant” sq. has considered one of eight totally different colours assigned to encode the mixture of black/white state and the present course of movement of the ant.^{[2]}

## Modes of conduct[edit]

These easy guidelines result in advanced conduct. Three distinct modes of conduct are obvious,^{[3]} when beginning on a very white grid.

- Simplicity. Throughout the first few hundred strikes it creates quite simple patterns which are sometimes symmetric.
- Chaos. After a couple of hundred strikes, a big, irregular sample of black and white squares seems. The ant traces a pseudo-random path till round 10,000 steps.
- Emergent order. Lastly the ant begins constructing a recurrent “freeway” sample of 104 steps that repeats indefinitely.

All finite preliminary configurations examined ultimately converge to the identical repetitive sample, suggesting that the “freeway” is an attractor of Langton’s ant, however nobody has been capable of show that that is true for all such preliminary configurations. It’s only recognized that the ant’s trajectory is at all times unbounded whatever the preliminary configuration^{[4]} – this is called the Cohen-Kong theorem.^{[5]}

## Computational universality[edit]

In 2000, Gajardo et al. confirmed a building that calculates any boolean circuit utilizing the trajectory of a single occasion of Langton’s ant.^{[2]} Moreover, it might be potential to simulate an arbitrary Turing machine utilizing the ant’s trajectory for computation. Which means the ant is able to common computation.

## Extension to a number of colours[edit]

Greg Turk and Jim Propp thought-about a easy extension to Langton’s ant the place as a substitute of simply two colours, extra colours are used.^{[6]} The colours are modified in a cyclic trend. A easy naming scheme is used: for every of the successive colours, a letter “L” or “R” is used to point whether or not a left or proper flip must be taken. Langton’s ant has the title “RL” on this naming scheme.

A few of these prolonged Langton’s ants produce patterns that grow to be symmetric again and again. One of many easiest examples is the ant “RLLR”. One ample situation for this to occur is that the ant’s title, seen as a cyclic listing, consists of consecutive pairs of an identical letters “LL” or “RR”. (the time period “cyclic listing” signifies that the final letter could pair with the primary one) The proof entails Truchet tiles.

The hexagonal grid permits as much as six totally different rotations, that are notated right here as N (no change), R_{1} (60° clockwise), R_{2} (120° clockwise), U (180°), L_{2} (120° counter-clockwise), L_{1} (60° counter-clockwise).

## Extension to a number of states[edit]

An additional extension of Langton’s ants is to think about a number of states of the Turing machine – as if the ant itself has a colour that may change. These ants are referred to as turmites, a contraction of “Turing machine termites“. Frequent behaviours embody the manufacturing of highways, chaotic progress and spiral progress.^{[7]}

## Extension to a number of ants[edit]

A number of Langton’s ants can co-exist on the 2D airplane, and their interactions give rise to advanced, higher-order automata that collectively construct all kinds of organized buildings.

There are alternative ways of modelling their interplay and the outcomes of the simulation could strongly depend upon the alternatives made.^{[8]}

One could select that every one the ants sitting on the identical sq. concurrently make the identical change to the tape. There’s a YouTube video displaying the simulation of such a number of ant interactions. Additionally there exists household of colonies which is absolute oscillator with linear interval 4(8n+3).

A number of turmites can co-exist on the 2D airplane so long as there’s a rule that defines what occurs after they meet. Ed Pegg, Jr. thought-about ants that may flip for instance *each* left and proper, splitting in two and annihilating one another after they meet.^{[9]}

## See additionally[edit]

## References[edit]

**^**Langton, Chris G. (1986). “Studying artificial life with cellular automata” (PDF).*Physica D: Nonlinear Phenomena*.**22**(1–3): 120–149. Bibcode:1986PhyD…22..120L. doi:10.1016/0167-2789(86)90237-X. hdl:2027.42/26022.- ^
^{a}^{b}^{c}Gajardo, A.; Moreira, A.; Goles, E. (15 March 2002). “Complexity of Langton’s ant” (PDF).*Discrete Utilized Arithmetic*.**117**(1–3): 41–50. arXiv:nlin/0306022. doi:10.1016/S0166-218X(00)00334-6. S2CID 1107883. **^**Pratchett, Terry (1999).*The Science Of Discworld*.**^**Bunimovich, Leonid A.; Troubetzkoy, Serge E. (1992). “Recurrence properties of Lorentz lattice fuel mobile automata”.*Journal of Statistical Physics*.**67**(1–2): 289–302. Bibcode:1992JSP….67..289B. doi:10.1007/BF01049035. S2CID 121346477.**^**Stewart, I. (1994). “The Ultimate in Anty-Particles” (PDF).*Sci. Am*.**271**(1): 104–107. Bibcode:1994SciAm.271a.104S. doi:10.1038/scientificamerican0794-104. Archived from the original (PDF) on 3 March 2016. Retrieved 6 Could 2013.**^**Gale, D.; Propp, J.; Sutherland, S.; Troubetzkoy, S. (1995). “Additional Travels with My Ant”.*Mathematical Entertainments Column, Mathematical Intelligencer*.**17**: 48–56. arXiv:math/9501233. doi:10.1007/BF03024370. S2CID 123800756.**^**Pegg, Jr., Ed. “Turmite”. From MathWorld–A Wolfram Internet Useful resource, created by Eric W. Weisstein. Retrieved 15 October 2009. .**^**Belgacem, S.; Fatès, N. (2012). “Robustness of Multi-agent Models: The Example of Collaboration between Turmites with Synchronous and Asynchronous Updating” (PDF).*Complicated Methods*.**21**(3): 165–182. doi:10.25088/ComplexSystems.21.3.165.**^**Pegg, Jr., Ed. “Math Puzzle”. Retrieved 15 October 2009..

## Exterior hyperlinks[edit]