Turmite
From Wikipedia, the free encyclopedia
In computer science, a turmite is a two-dimensional Turing machine which has a current state, and a "tape" that consists of an infinite grid with labelled cells, nodes or edges. 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.
[edit] External links
- Math Games: 2D Turing Machines, at MAA Online
- Math Games: Paterson's Worms Revisited, at MAA Online
- Turmite, at MathWorld.