Title: Nontrivial Turmites are Turing-universal,
Abstract: A Turmit 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. Several symbols
are admitted, and the rule is specified by the turning sense that the machine
has over each symbol. Turmites are a generalization of Langtons ant, and they
present very complex and diverse behaviors. We prove that any Turmite, except
for those whose rule does not depend on the symbol, can simulate any Turing
Machine. We also prove the P-completeness of prediction their future behavior
by explicitly giving a log-space reduction from the Topological Circuit Value
Problem. A similar result was already established for Langtons ant; here we use
a similar technique but prove a stronger notion of simulation, and for a more
general family.