List of universal cellular automata

From LifeWiki
Jump to navigation Jump to search

A cellular automaton is said to be universal (or Turing-complete) when it can perform any operation that a Turing machine can. The concept of universal computation is often tied to, but not equivalent to, functional completeness.

Proof of universality

As the concept of universal computation is informal, proofs or disproofs of universal computation are also informal. However, it is generally agreed that a proof of universal computation requires the construction of a universal computer. By convention, a cellular automaton is "proven" to be universal by building a structure which intuitively runs Rule 110.

List of cellular automata proven to be universal

This list is work in progress, feel free to add any cellular automaton or any information:

See also

Retrieved from "https://conwaylife.com/w/index.php?title=List_of_universal_cellular_automata&oldid=173973"