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)

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

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.

Original language	English
Pages (from-to)	393-430
Number of pages	38
Journal	Journal of Cellular Automata
Volume	7
Issue number	5-6
State	Published - 2012

Keywords

Attractors
Cellular automata
Chaos
Complexity
Compressibility
Gliders
Information theory
Mean field theory
Unconventional computing
Universality

Cite this

@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

Abstract

Keywords

Other files and links

Fingerprint

Cite this