Circuit universality of two dimensional cellular automata: A review

Anahí Gajardo, Eric Goles

Producción científica: Capítulo del libro/informe/acta de congresoCapítulorevisión exhaustiva

1 Cita (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaRandomness and Complexity
Subtítulo de la publicación alojadaFrom Leibniz to Chaitin
EditorialWorld Scientific Publishing Co.
Páginas131-152
Número de páginas22
ISBN (versión digital)9789812770837
ISBN (versión impresa)9812770828, 9789812770820
DOI
EstadoPublicada - 1 ene. 2007
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Circuit universality of two dimensional cellular automata: A review'. En conjunto forman una huella única.

Citar esto