Turing completeness of cellular automata

tags
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

Bibliography

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

Links to this note


← Back to Notes