Structure and computability of preimages in the Game of Life

Ville Salo, Ilkka Törmä

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 Tur…