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


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

← Back to Notes