Reversibility and surjectivity problems of cellular automata

摘要

The problem of deciding if a given cellular automaton (CA) is reversible (or, equivalently, if its global transition function is injective) is called the reversibility problem of CA. In this article we show that the reversibility problem is undecidable in case of two-dimensional CA. We also prove that the corresponding surjectivity problem—the problem of deciding if the global function is surjective—is undecidable for two-dimensional CA. Both problems are known to be decidable in case of one-dimensional CA. The proofs of the theorems are based on reductions from the well-known tiling problem of the plane, known also as the domino problem.