Abstract:
Toffoli showed that every cellular automaton of an arbitrary dimension d can be embedded into a
reversible cellular automaton of dimension d+1. He asked “whether an arbitrary cellular automaton
can be embedded in a reversible one having the same number of dimensions” and conjectured that
this is not possible. We show that his conjecture is true. Even if one imposes only a weak, natural
condition on embeddings, no cellular automaton which possesses a Garden of Eden configuration
can be embedded into a reversible cellular automaton of the same dimension.