Circuit universality of two dimensional cellular automata: A review

Anahí Gajardo; Eric Goles

doi:10.1142/9789812770837_0007

Circuit universality of two dimensional cellular automata: A review

Anahí Gajardo
, Eric Goles

Producción científica: Capítulo del libro/informe/acta de congreso › Capítulo › revisión exhaustiva

2 Citas (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 original	Inglés
Título de la publicación alojada	Randomness and Complexity
Subtítulo de la publicación alojada	From Leibniz to Chaitin
Editorial	World Scientific Publishing Co.
Páginas	131-152
Número de páginas	22
ISBN (versión digital)	9789812770837
ISBN (versión impresa)	9812770828, 9789812770820
DOI	https://doi.org/10.1142/9789812770837_0007
Estado	Publicada - 1 ene 2007
Publicado de forma externa	Sí

Acceder al documento

10.1142/9789812770837_0007

Citar esto

@inbook{d60357aac7d54208bddbe6b74d9ebe6d,

title = "Circuit universality of two dimensional cellular automata: A review",

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{\textquoteright}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.",

author = "Anah{\'i} Gajardo and Eric Goles",

year = "2007",

month = jan,

day = "1",

doi = "10.1142/9789812770837\_0007",

language = "English",

isbn = "9812770828",

pages = "131--152",

booktitle = "Randomness and Complexity",

publisher = "World Scientific Publishing Co.",

}

TY - CHAP

T1 - Circuit universality of two dimensional cellular automata

T2 - A review

AU - Gajardo, Anahí

AU - Goles, Eric

PY - 2007/1/1

Y1 - 2007/1/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84967389187

U2 - 10.1142/9789812770837_0007

DO - 10.1142/9789812770837_0007

M3 - Chapter

AN - SCOPUS:84967389187

SN - 9812770828

SN - 9789812770820

SP - 131

EP - 152

BT - Randomness and Complexity

PB - World Scientific Publishing Co.

ER -

Circuit universality of two dimensional cellular automata: A review

Resumen

Acceder al documento

Huella

Citar esto