Computation and universality: Class IV versus class III cellular automata

Genaro J. Martinez; Juan C. Seck-Tuoh-Mora; Hector Zenil

Computation and universality: Class IV versus class III cellular automata

Genaro J. Martinez, Juan C. Seck-Tuoh-Mora, Hector Zenil

Escuela Superior de Cómputo (ESCOM)

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

20 Citas (Scopus)

Resumen

This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram's classification) are capable of (Turing universal) computation.We explore some chaotic CA (believed to belong to Class III) reported over the course of the CA history, that may be candidates for universal computation, hence spurring the discussion on Turing universality on both Wolfram's classes III and IV.

Idioma original	Inglés
Páginas (desde-hasta)	393-430
Número de páginas	38
Publicación	Journal of Cellular Automata
Volumen	7
N.º	5-6
Estado	Publicada - 2012

Otros archivos y enlaces

Enlace a la publicación en Scopus

Citar esto

@article{3bdf58837580410b9fe7979ed10066de,

title = "Computation and universality: Class IV versus class III cellular automata",

abstract = "This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram's classification) are capable of (Turing universal) computation.We explore some chaotic CA (believed to belong to Class III) reported over the course of the CA history, that may be candidates for universal computation, hence spurring the discussion on Turing universality on both Wolfram's classes III and IV.",

keywords = "Attractors, Cellular automata, Chaos, Complexity, Compressibility, Gliders, Information theory, Mean field theory, Unconventional computing, Universality",

author = "Martinez, {Genaro J.} and Seck-Tuoh-Mora, {Juan C.} and Hector Zenil",

year = "2012",

language = "Ingl{\'e}s",

volume = "7",

pages = "393--430",

journal = "Journal of Cellular Automata",

issn = "1557-5969",

publisher = "Old City Publishing",

number = "5-6",

}

TY - JOUR

T1 - Computation and universality

T2 - Class IV versus class III cellular automata

AU - Martinez, Genaro J.

AU - Seck-Tuoh-Mora, Juan C.

AU - Zenil, Hector

PY - 2012

Y1 - 2012

N2 - This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram's classification) are capable of (Turing universal) computation.We explore some chaotic CA (believed to belong to Class III) reported over the course of the CA history, that may be candidates for universal computation, hence spurring the discussion on Turing universality on both Wolfram's classes III and IV.

AB - This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram's classification) are capable of (Turing universal) computation.We explore some chaotic CA (believed to belong to Class III) reported over the course of the CA history, that may be candidates for universal computation, hence spurring the discussion on Turing universality on both Wolfram's classes III and IV.

KW - Attractors

KW - Cellular automata

KW - Chaos

KW - Complexity

KW - Compressibility

KW - Gliders

KW - Information theory

KW - Mean field theory

KW - Unconventional computing

KW - Universality

UR - http://www.scopus.com/inward/record.url?scp=84875390164&partnerID=8YFLogxK

M3 - Artículo

AN - SCOPUS:84875390164

SN - 1557-5969

VL - 7

SP - 393

EP - 430

JO - Journal of Cellular Automata

JF - Journal of Cellular Automata

IS - 5-6

ER -

Computation and universality: Class IV versus class III cellular automata

Resumen

Otros archivos y enlaces

Huella

Citar esto