Circuit universality of two dimensional cellular automata: A review

Anahí Gajardo, Eric Goles

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

1 Scopus citations


Universality of Cellular Automata (CA) is the ability to develop arbitrary computations, and is viewed as a "complexity certificate". The concept exists since the creation of CA by John von Neumann, and it has undergone several transformations and ramifications. We review a sample of models, starting with Banks’s CA, where universality has been shown through the construction of arbitrary boolean circuits ("Circuit Universality"), in most but not all cases leading to proofs of Turing Universality.

Original languageEnglish
Title of host publicationRandomness and Complexity
Subtitle of host publicationFrom Leibniz to Chaitin
PublisherWorld Scientific Publishing Co.
Number of pages22
ISBN (Electronic)9789812770837
ISBN (Print)9812770828, 9789812770820
StatePublished - 1 Jan 2007
Externally publishedYes


Dive into the research topics of 'Circuit universality of two dimensional cellular automata: A review'. Together they form a unique fingerprint.

Cite this