Turing completeness of cellular automata

Cellular automata, Turing-completeness

Rule 110

Elementary cellular automaton rule 110 is universal (Cook 2004).

Game of Life

Conway’s Game of Life has also been show to be Turing-complete. Gliders can be used to implement logic gates.

A working computer in Game of Life


Cook, Matthew. 2004. “Universality in Elementary Cellular Automata.” Complex Systems, 40.

Links to this note

← Back to Notes