LoginSign Up
Turmite

Turmite

A Turing machine that computes on a 2d grid where the tape of the machine is an infinite grid of binary cells that gives rise to complex output patterns. A specific case was discovered in 1986 by Langton.

Turmites can produce complex patterns (spirals, golden rectangles, chaotic structures, nested growth and cyclical structures) and repeating structures such as 'highways'. In the case of the cells being squares (ie a square grid) a well known turmite is called a Langton's ant. When on a isometric grid, this type of turmite is called a Paterson worm.

The grid can be painted or erased (1 or 0) by the active cell and then the active cell is turned (up, down, left, right) based on the state of the current grid cell that the active cell is on. Each time the turing machine is run, a cell is painted or erased and moved onto an adjacent cell. The turmite tracks its own position, direction and current state.

The active cell has various names including: ant, turmite, vant for square grids and bee, turtle, worm on hexagonal grids. 'Turtle' comes from 'turtle geometry' by Seymour Papert.

The turmite can halt and go into repetition, thus a relation to the halting problem exists.

History

In 1986 Langton discovered the specific turmite type of Langton's ant. By 1988 Allen Brady conceived a 2D Turing Machine with rotation coining it a 'TurNing machine'.

A. K Dewdney coined the phrase 'tur-mite' in a 1989 Scientific American article called 'Computer Recreations'.

Properties of turmites

Turmites have been shown to be equivalent to 1D Turing machines with infinite tape.

Timeline

People

Name
Role
Related Golden topics

Further reading

Title
Author
Link
Type

Turmite

http://mathworld.wolfram.com/topics/Pegg.html

Documentaries, videos and podcasts

Title
Date
Link

Companies

Company
CEO
Location
Products/Services