Embedding Game of Life into a Simple Asynchronous Cellular Automaton

Emulating the global transitions of synchronous cellular automata (CAs), like the well-known Game of Life (GL), is a conventional scheme for computing on asynchronous cellular automata (ACAs). Especially, the GL can be completely simulated by an ACA with Moore neighborhood (Lee et al., 2004), which requires 8 states per cell and hundreds of transition rules. The simulation can be made much more efficient if we employ a continuous block of cells in an ACA to emulate each cell in the GL, by laying out a logic circuit on every block to accomplish the functionality of a GL´s cell. Based on an efficient circuit scheme (Lee et al., 2014), we show that the GL can be embedded into a simpler ACA with von Neumann neighborhood that takes 5 cell states and tens of transition rules.