Abstract
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 language | English |
|---|---|
| Title of host publication | Randomness and Complexity |
| Subtitle of host publication | From Leibniz to Chaitin |
| Publisher | World Scientific Publishing Co. |
| Pages | 131-152 |
| Number of pages | 22 |
| ISBN (Electronic) | 9789812770837 |
| ISBN (Print) | 9812770828, 9789812770820 |
| DOIs | |
| State | Published - 1 Jan 2007 |
| Externally published | Yes |