Computing backwards with Game of Life, part 1: wires and circuits
share
Conway's Game of Life is a two-dimensional cellular automaton. As a dynamical system, it is well-known to be computationally universal, i.e. capable of simulating an arbitrary Turing machine. We show that in a sense taking a single backwards step of Game of Life is a computationally universal process, by constructing patterns whose preimage computation encodes an arbitrary circuit-satisfaction problem, or (equivalently) any tiling problem. As a corollary, we obtain for example that the set of orphans is coNP-complete, exhibit a 6210 × 37800-periodic configuration that admits a preimage but no periodic one, and prove that the existence of a preimage for a periodic point is undecidable. Our constructions were obtained by a combination of computer searches and manual design.
READ FULL TEXT