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.

Langton's ant is a well-known type of turmite defined on the cells of a square 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.

[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.

With the kind permission of Turk and Dewdney, I'm going to leave out the hyphen, and call them turmites.Turmites can be categorised as being either relative or absolute.

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.

[6] Following Allen H. Brady's initial work of turmites on a triangular grid, hexagonal tilings have also been explored.