Nontrivial Turmites are Turing-universal
Diego Maldonado, Anahí Gajardo, Benjamin Hellouin De Menibus and Andrés Moreir
A Turmite is a Turing machine that works over a two-dimensional grid, that is, an agent that moves, reads and writes symbols over the cells of the grid. Its state is an arrow and, depending on the symbol that it reads, it turns to the left or to the right, switching the symbol at the same time. The rule is specified by the turning direction for each symbol. Turmites are a generalization of Langton’s ant, and they present even more complex and diverse behaviors.
We prove that any Turmite, except for those who behave the same on every symbol, can simulate arbitrary computation in specific periodic configurations which are periodic, except for a finite input area. We also prove the P-completeness of predicting their future behavior by providing an explicit log-space reduction from the Topological Circuit Value Problem. A similar result was already established for Langton’s ant; here we use a similar technique but prove a stronger notion of simulation, and for a more general family. These results are obtained by using gadgets similar to single-use logic gates; each gate performs its computation as the Turmite travels through it, therefore simulating arbitrary computation.
Keywords: Turing-universality, p-completeness, one head machines, unconventional computation, turmits, unpredictability