HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a turmite is a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
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

Langton's ants 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 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 (Georgia Tech). His paper "Zippered polygon mes ...
investigated the same kind of system and wrote to
A. K. Dewdney Alexander Keewatin Dewdney (born August 5, 1941) is a Canadian mathematician, computer scientist, author, filmmaker, and conspiracy theorist. Dewdney is the son of Canadian artist and author Selwyn Dewdney, and brother of poet Christopher Dewdney. ...
about them. A. K. Dewdney named them "tur-mites" in his "Computer Recreations" column in
Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...
in 1989.
Rudy Rucker Rudolf von Bitter Rucker (; born March 22, 1946) is an American mathematician, computer scientist, science fiction author, and one of the founders of the cyberpunk literary movement. The author of both fiction and non-fiction, he is best known f ...
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 Ant is such an example. Relative turmites are, by definition,
isotropic Isotropy is uniformity in all orientations; it is derived . Precise definitions depend on the subject area. Exceptions, or inequalities, are frequently indicated by the prefix ' or ', hence ''anisotropy''. ''Anisotropy'' is also used to describe ...
; 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 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).


Examples

square grid In geometry, the square tiling, square tessellation or square grid is a regular tiling of the Euclidean plane. It has Schläfli symbol of meaning it has 4 squares around every vertex. Conway called it a quadrille. The internal angle of the s ...
, all starting from an empty configuration:"> File:Turmite-111180121010-12536.png, Spiral growth. File:Turmite-121021110111-27731.png, Production of a highway after a period of chaotic growth. File:Turmite-121181121020-65932.png, Chaotic growth with a distinctive texture. File:Turmite-180121020081-223577.png, Growth with a distinctive texture inside an expanding frame. File:Turmite-181181121010-10211.png, Constructing a
Fibonacci spiral Fibonacci (; also , ; – ), also known as Leonardo Bonacci, Leonardo of Pisa, or Leonardo Bigollo Pisano ('Leonardo the Traveller from Pisa'), was an Italian mathematician from the Republic of Pisa, considered to be "the most talented Western ...
. File:Turmite creating a growing diamond.png, Constructing a growing diamond File:Turmite_Snowflake.jpg, Three-state two-color turmite producing a snowflake-like
fractal In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as illu ...
pattern. File:Hexagonal turmite.jpg, Three-color three-state turmite on a
hexagonal grid In geometry, the hexagonal tiling or hexagonal tessellation is a regular tiling of the Euclidean plane, in which exactly three hexagons meet at each vertex. It has Schläfli symbol of or (as a truncated triangular tiling). English mathematic ...
, 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

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. He also considered turmites that move on a triangular grid, finding several busy beavers here too.
Ed Pegg, Jr. Edward Taylor Pegg Jr. (born December 7, 1963) is an expert on mathematical puzzles and is a self-described recreational mathematician. He wrote an online puzzle column called Ed Pegg Jr.'s ''Math Games'' for the Mathematical Association of Amer ...
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 tiling In geometry, the hexagonal tiling or hexagonal tessellation is a regular tiling of the Euclidean plane, in which exactly three hexagons meet at each vertex. It has Schläfli symbol of or (as a truncated triangular tiling). English mathemat ...
s 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

* * *


References


External links

* * * {{cite web, url=http://www.maa.org/editorial/mathgames/mathgames_10_24_03.html, title=Math Games: Paterson's Worms Revisited , last=Pegg Jr. , first=Ed , date=October 27, 2003 , publisher=MAA Online , archive-url=https://web.archive.org/web/20040323220627/http://www.maa.org/editorial/mathgames/mathgames_10_24_03.html , archive-date=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
Artificial life Models of computation Cellular automaton rules Turing machine