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

1. Matthew Cook. 2004. "Universality in Elementary Cellular Automata". Complex Systems, 40.