Turmite
Encyclopedia
In computer science
, a turmite is a Turing machine
which has an orientation as well as a current state and a "tape" that consists of an infinite two-dimensional grid of cells. The terms ant and vant are also used. Langton's ant
is a well-known type of turmite defined on the cells of a square grid. Paterson's worms
are a type of turmite defined on the edges of an isometric grid.
It has been shown that turmites in general are exactly equivalent in power to one-dimensional Turing machines with an infinite tape, as either can simulate the other.
s were invented in 1986 and declared "equivalent to Turing machines". Independently, in 1988, Allen H. Brady considered the idea of two-dimensional Turing machines with an orientation and called them "TurNing machines".
Apparently independently of both of these, Greg Turk
investigated the same kind of system and wrote to A. K. Dewdney
about them. A. K. Dewdney named them "tur-mites" in his "Computer Recreations" column in Scientific American
in 1989. Rudy Rucker
relates the story as follows:
is such an example. Relative turmites are, by definition, isotropic; rotating the turmite does not affect its outcome. Relative turmites are so named because the directions are encoded relative to the current orientation, equivalent to using the words 'left' or 'backwards'. Absolute turmites, by comparison, encode their directions in absolute terms: a particular instruction may direct the turmite to move 'North'. Absolute turmites are two-dimensional analogues of conventional Turing machines, so are occasionally referred to as simply "Two-dimensional Turing machines". The remainder of this article is concerned with the relative case.
As with Langton's ant, turmites perform the following operations each timestep:
As with Turing machines, the actions are specified by a state transition table
listing the current internal state of the turmite and the color of the cell it is currently standing on. For example, the turmite shown in the image at the top of this page is specified by the following table:
The direction to turn is one of L (90° left), R (90° right), N (no turn) and U (180° U-turn).
) and found a 2-state 2-color machine that printed 37 1's before halting, and another that took 121 steps before halting. He also considered turmites that move on a triangular grid, finding several busy beavers here too.
Ed Pegg, Jr.
considered another approach to the busy beaver game. He suggested turmites that can turn for example both left and right, splitting in two. Turmites that later meet annihilate each other. In this system, a Busy Beaver is one that from a starting pattern of a single turmite lasts the longest before all the turmites annihilate each other.
, which Brady termed flippers. (One-dimensional absolute turmites are of course simply known as Turing machines.)
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a turmite is a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
which has an orientation as well as a current state and a "tape" that consists of an infinite two-dimensional grid of cells. The terms ant and vant are also used. Langton's ant
Langton's ant
Langton's ant is a two-dimensional Turing machine with a very simple set of rules but complicated emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The universality of Langton's ant was proven in 2000...
is a well-known type of turmite defined on the cells of a square grid. Paterson's worms
Paterson's worms
Paterson's Worms are a family of Turing machines devised in 1971 by Mike Paterson and John Horton Conway to model the behaviour and feeding patterns of certain prehistoric worms. In the model, a worm moves between points on a triangular grid along line segments, representing food...
are a type of turmite defined on the edges of an isometric grid.
It has been shown that turmites in general are exactly equivalent in power to one-dimensional Turing machines with an infinite tape, as either can simulate the other.
History
Langton's antLangton's ant
Langton's ant is a two-dimensional Turing machine with a very simple set of rules but complicated emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The universality of Langton's ant was proven in 2000...
s were invented in 1986 and declared "equivalent to Turing machines". Independently, in 1988, Allen H. Brady considered the idea of two-dimensional Turing machines with an orientation and called them "TurNing machines".
Apparently independently of both of these, Greg Turk
Greg Turk
Greg Turk is an American-born researcher in the field of computer graphics and a Professor at the School of Interactive Computing in the College of Computing at the Georgia Institute of Technology...
investigated the same kind of system and wrote to A. K. Dewdney
Alexander Dewdney
Alexander Keewatin Dewdney is a Canadian mathematician, computer scientist and philosopher who has written a number of books on the future and implications of modern computing. He has also written one work of fiction, The Planiverse...
about them. A. K. Dewdney named them "tur-mites" in his "Computer Recreations" column in Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...
in 1989. Rudy Rucker
Rudy Rucker
Rudolf von Bitter Rucker is an American mathematician, computer scientist, science fiction author, and philosopher, and is one of the founders of the cyberpunk literary movement. The author of both fiction and non-fiction, he is best known for the novels in the Ware Tetralogy, the first two of...
relates the story as follows:
Relative vs. absolute turmites
Turmites can be categorised as being either relative or absolute. Relative turmites, alternatively known as 'Turning machines', have an internal orientation. Langton's AntLangton's ant
Langton's ant is a two-dimensional Turing machine with a very simple set of rules but complicated emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The universality of Langton's ant was proven in 2000...
is such an example. Relative turmites are, by definition, isotropic; rotating the turmite does not affect its outcome. Relative turmites are so named because the directions are encoded relative to the current orientation, equivalent to using the words 'left' or 'backwards'. Absolute turmites, by comparison, encode their directions in absolute terms: a particular instruction may direct the turmite to move 'North'. Absolute turmites are two-dimensional analogues of conventional Turing machines, so are occasionally referred to as simply "Two-dimensional Turing machines". The remainder of this article is concerned with the relative case.
Specification
The following specification is specific to turmites on a two-dimensional square grid, the most studied type of turmite. Turmites on other grids can be specified in a similar fashion.As with Langton's ant, turmites perform the following operations each timestep:
- turn on the spot (by some multiple of 90°)
- change the color of the square
- move forward one square
As with Turing machines, the actions are specified by a state transition table
State transition table
In automata theory and sequential logic, a state transition table is a table showing what state a finite semiautomaton or finite state machine will move to, based on the current state and other inputs...
listing the current internal state of the turmite and the color of the cell it is currently standing on. For example, the turmite shown in the image at the top of this page is specified by the following table:
| Current color | |||||||
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| Write color | Turn | Next state | Write color | Turn | Next state | ||
| Current state | 0 | 1 | R | 0 | 1 | R | 1 |
| 1 | 0 | N | 0 | 0 | N | 1 | |
The direction to turn is one of L (90° left), R (90° right), N (no turn) and U (180° U-turn).
Examples
Starting from an empty grid or other configurations, the most commonly observed behaviours are chaotic growth, spiral growth and 'highway' construction. Rare examples become periodic after a certain number of steps.Turmites and the Busy Beaver game
Allen H. Brady searched for terminating turmites (the equivalent of busy beaversBusy beaver
In computability theory, a busy beaver is a Turing machine that attains the maximum "operational busyness" among all the Turing machines in a certain class...
) and found a 2-state 2-color machine that printed 37 1's before halting, and another that took 121 steps before halting. He also considered turmites that move on a triangular grid, finding several busy beavers here too.
Ed Pegg, Jr.
Ed Pegg, Jr.
Ed Pegg, Jr. is an expert on mathematical puzzles and is a self-described recreational mathematician. He creates puzzles for the Mathematical Association of America online at Ed Pegg, Jr.'s Math Games. His puzzles have also been used by Will Shortz on the puzzle segment of NPR's Weekend Edition...
considered another approach to the busy beaver game. He suggested turmites that can turn for example both left and right, splitting in two. Turmites that later meet annihilate each other. In this system, a Busy Beaver is one that from a starting pattern of a single turmite lasts the longest before all the turmites annihilate each other.
Other grids
Following Allen H. Brady's initial work of turmites on a triangular grid, hexagonal tilings have also been explored. Much of this work is due to Tim Hutton, and his results are on the Rule Table Repository. He has also considered Turmites in three dimensions, and collected some preliminary results. Allen H. Brady and Tim Hutton have also investigated one-dimensional relative turmites on the integer latticeInteger lattice
In mathematics, the n-dimensional integer lattice , denoted Zn, is the lattice in the Euclidean space Rn whose lattice points are n-tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid lattice. Zn is the simplest example of a root lattice...
, which Brady termed flippers. (One-dimensional absolute turmites are of course simply known as Turing machines.)
External links
- Webpage demonstrating several turmites
- Math Games: 2D Turing Machines, at MAA Online
- Math Games: Paterson's Worms Revisited, at MAA Online
- Turmite, at MathWorldMathWorldMathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...
. - Golly script for generating arbitrary turmites
- Absolute- and relative-movement Turmites and Busy Beavers on square, cubic, triangular and hexagonal grids