Some results on cellular automata
Atti della Accademia nazionale dei Lincei. Rendiconti Lincei. Matematica e applicazioni, Série 9, Tome 9 (1998) no. 4, pp. 307-316
Voir la notice de l'article provenant de la source Biblioteca Digitale Italiana di Matematica
We want to discuss some properties of one-dimensional, radius 1, CUCAs (we denote by CUCA a Computationally Universal Cellular Automaton; see later on for the definitions). In particular, on one hand we want to keep small the number of states (the first example of «small» CUCA is due to Smith III [13]; it requires 18 states); on the other hand we are interested into automata, possibly requiring a high number of states, whose transition law is «as simple as possible»; e.g. totalistic automata (the existence of a totalistic CUCA, conjectured by Wolfram [14], was proved by Gordon [7] who constructed a totalistic CUCA with 9139 states). More generally, we will deal with the problem of simulating a generic cellular automaton through an automaton having a «simpler» transition law.
@article{RLIN_1998_9_9_4_a6,
author = {Baiocchi, Claudio},
title = {Some results on cellular automata},
journal = {Atti della Accademia nazionale dei Lincei. Rendiconti Lincei. Matematica e applicazioni},
pages = {307--316},
publisher = {mathdoc},
volume = {Ser. 9, 9},
number = {4},
year = {1998},
zbl = {0931.68072},
mrnumber = {MR1722789},
language = {en},
url = {http://geodesic.mathdoc.fr/item/RLIN_1998_9_9_4_a6/}
}
TY - JOUR AU - Baiocchi, Claudio TI - Some results on cellular automata JO - Atti della Accademia nazionale dei Lincei. Rendiconti Lincei. Matematica e applicazioni PY - 1998 SP - 307 EP - 316 VL - 9 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/RLIN_1998_9_9_4_a6/ LA - en ID - RLIN_1998_9_9_4_a6 ER -
Baiocchi, Claudio. Some results on cellular automata. Atti della Accademia nazionale dei Lincei. Rendiconti Lincei. Matematica e applicazioni, Série 9, Tome 9 (1998) no. 4, pp. 307-316. http://geodesic.mathdoc.fr/item/RLIN_1998_9_9_4_a6/