0
$\begingroup$

I have been reading up on 2D Turing machines on wolframscience and I am kind of confused about what exactly is the relationship between 2D Turing machines (like Paterson's worm and Langton's Ant) and Cellular Automata. I understand that they are both defined pretty differently but I keep seeing references between one and the other.
For example, this article regarding Langton's Ant suggests that "the ant can simulate cellular automata and is thus computationally universal." Why is this true?
Any additional resources or general guidance for this would be great. Thanks in advance!

$\endgroup$
3
  • $\begingroup$ Two-dimensional Turing machines can trivially simulate cellular automata. $\endgroup$ Oct 10 '21 at 9:44
  • $\begingroup$ Hi, could you elaborate further? From my understanding, Turing machines read/write or update a single cell before moving to the next while cellular automata updates generation by generation (where the whole grid updates). $\endgroup$ Oct 10 '21 at 11:06
  • $\begingroup$ Right, simulating one step takes the Turing machine many steps. $\endgroup$ Oct 10 '21 at 11:07
0
$\begingroup$

In a cellular automaton, every cell on the lattice is a finite state automaton that updates its state at each time step based on the prior state of itself and its neighbors. In other words, all cells are treated as "active" and capable of changing state simultaneously in parallel, although some may be in stable states where they will remain, at least until some of their neighboring cells change state.

A 2D Turing machine, however, just like its one-dimensional counterpart, consists of a passive lattice or tape of cells, and a (usually) single "head" (such as the "ant" in Langton's Ant) which can move around on the lattice and modify both its own internal state and the state of the cell at its current location. The lattice cells themselves, however, are only able to store a state, but can only change state in the presence of the head.

There is, of course, a rather straightforward and natural way of "embedding" a 2D Turing machine (2DTM) in a cellular automaton (CA). Basically, instead of having a single head that moves on the lattice, you equip each CA cell with enough possible states to let it store both every possible state of the head (plus one extra state for "head not present") as well as every possible state of a 2DTM lattice cell. (So, for a 2DTM with $m$ cell states and $n$ head states, you end up with a CA with $m(n+1)$ states per cell.) And then you define the state transition rules of the CA so that, whenever the head in the 2DTM would move to a different cell, the CA cell currently storing its state transitions to a "head not present" state, and the neighboring cell which the head would move into transitions into a state encoding the new state of the head. So, in effect, instead of a single active finite state machine "head" moving over a passive lattice, you have a lattice filled with active finite state machines cooperating in such a way as to pass the role of being the head around.

Thus, a CA can simulate a 2DTM in a direct manner, with each CA time step simulating one 2DTM time step and each CA cell storing the state of one 2DTM lattice cell (plus, possibly, the state of the head). The only inefficiency in this simulation is that the CA cells typically need a lot more states than the 2DTM cells in order to allow them to simulate the 2DTM head.

On the other hand, for a 2DTM to simulate even a single time step of a general CA, the head must somehow visit every cell on the lattice that might require a state update, carry out those updates (which typically requires also examining all neighboring cells) and then return to its starting point. This requires a lot of time, making simulating a CA by a 2DTM a rather slow process.

That said, this simulation can still be done in polynomial time: starting from a finite collection of active CA cells (i.e. ones not in a stable quiescent state) on a 2D lattice, the number of such cells can grow at most as a quadratic function of time, and so a 2DTM simulating such a CA needs to spend at most a quadratically growing number of steps to simulate each CA time step. So, if you follow the standard complexity-theoretic practice of treating any polynomial-time reduction as efficient, then a 2DTM can in fact "efficiently" simulate a CA.

(In particular, the way a 2DTM can simulate a CA isn't really all that different from how a real-world computer — also consisting of a single active CPU and a large number of passive memory cells — would simulate one. So the fact that we can practically simulate CA on a computer does indicate that, in practice, such simulation isn't that inefficient.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.