Geodesic
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  - 
%0 Journal Article
%A Baiocchi, Claudio
%T Some results on cellular automata
%J Atti della Accademia nazionale dei Lincei. Rendiconti Lincei. Matematica e applicazioni
%D 1998
%P 307-316
%V 9
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/RLIN_1998_9_9_4_a6/
%G en
%F RLIN_1998_9_9_4_a6
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/