Turmite
In computer science, a turmite is a Turing machine which has an orientation in addition to 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.
History
[edit]Langton's ants were invented in 1986 and declared "equivalent to Turing machines".[1] Independently, in 1988, Allen H. Brady considered the idea of two-dimensional Turing machines with an orientation and called them "TurNing machines".[2][3]
Apparently independently of both of these,[4] 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.[5] Rudy Rucker relates the story as follows:
Dewdney reports that, casting about for a name for Turk's creatures, he thought, "Well, they're Turing machines studied by Turk, so they should be tur-something. And they're like little insects, or mites, so I'll call them tur-mites! And that sounds like termites!" With the kind permission of Turk and Dewdney, I'm going to leave out the hyphen, and call them turmites.
— Rudy Rucker, Artificial Life Lab[4]
Relative vs. absolute turmites
[edit]Turmites can be categorised as being either relative or absolute. Relative turmites, alternatively known as "turning machines", have an internal orientation. Langton's ant 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
[edit]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 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
[edit]- Examples of two-state two-color turmites on a square grid, all starting from an empty configuration:
-
Spiral growth. -
Production of a highway after a period of chaotic growth. -
Chaotic growth with a distinctive texture. -
Growth with a distinctive texture inside an expanding frame. -
Constructing a Fibonacci spiral. -
Constructing a growing diamond
- Examples of turmites with more states and colors and on non-square grids:
-
Three-state two-color turmite producing a snowflake-like fractal pattern. -
Three-color three-state turmite on a hexagonal grid, growing chaotically with a distinctive texture before getting stuck in a periodic loop after approximately 194150 steps.
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.
Busy Beaver game
[edit]Allen H. Brady searched for terminating turmites (the equivalent of busy beavers) and found a 2-state 2-color machine that printed 37 1's before halting, and another that took 121 steps before halting.[3] 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.[6]
Other grids
[edit]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 lattice, which Brady termed flippers. (One-dimensional absolute turmites are of course simply known as Turing machines.)
See also
[edit]- Cellular automaton – Discrete model studied in computer science
- Langton's ant – Two-dimensional Turing machine with emergent behavior
- Paterson's worms – Family of cellular automata to model feeding behaviour
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.
- ^ Brady, Allen H. (1988). "The Busy Beaver Game and the Meaning of Life". In Rolf Herken (ed.). The Universal Turing Machine: A Half-Century Survey. Springer-Verlag. ISBN 0-19-853741-7.
- ^ a b Brady, Allen H. (1995). "The Busy Beaver Game and the Meaning of Life". In Rolf Herken (ed.). The Universal Turing Machine: A Half-Century Survey (2nd ed.). Springer-Verlag. pp. 237–254. ISBN 3-211-82637-8.
- ^ a b Rucker, Rudy. "Artificial Life Lab". Archived from the original on June 10, 2011. Retrieved October 16, 2009.
- ^ Dewdney, A. K. (September 1989). "Computer Recreations: Two-dimensional Turing machines and Turmites make tracks on a plane". Scientific American. 261: 180–183. doi:10.1038/scientificamerican0989-180.
- ^ Pegg, Jr., Ed. "Math Puzzle". Retrieved 15 October 2009.
External links
[edit]
- "Webpage demonstrating several turmites". Archived from the original on 2013-12-21.
- Pegg Jr., Ed (June 7, 2004). "Math Games: 2D Turing Machines". MAA Online. Archived from the original on 2013-05-16.
- Pegg Jr., Ed (October 27, 2003). "Math Games: Paterson's Worms Revisited". MAA Online. Archived from the original on 2004-03-23.
- Turmite, at MathWorld.
- Golly script for generating arbitrary turmites
- Absolute- and relative-movement Turmites and Busy Beavers on square, cubic, triangular and hexagonal grids