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.
Ci proponiamo di discutere qualche proprietà degli automi cellulari con capacità di calcolo universali, nell’àmbito di automi uni-dimensionali di raggio 1. Siamo in particolare interessati da un lato al problema di rendere basso il numero di stati, e d’altro lato ad automi che, sia pure con alto numero di stati, abbiano una legge di transizione particolarmente semplice. Più in generale, cercheremo di simulare un qualunque automa con uno la cui legge di transizione sia «più semplice». 
@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 = {891509},
     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/

[1] J. Albert - K. Culik Ii, A Simple Universal Cellular Automaton and its One-Way and Totalistic Version. Complex Systems, 1, 1987, 1-16. | MR | Zbl

[2] C. Baiocchi, Qualche risultato sugli automi cellulari. Rend. Ist. Lombardo, to appear.

[3] R. Balzer, An 8-state minimal time solution to the firing squad sincronization problem. Information and Control, 10, 1967, 22-42.

[4] E. R. Berlekamp - J. H. Conway - R. K. Guy, Winning Ways for Your Mathematical Plays. Academic Press, London 1982. | Zbl

[5] A. K. Dewdney, Computer recreations. Sci. Amer., 224, 1971, 226, 1972.

[6] M. Gardner, Wheels, Life and other mathematical amusements. Freeman, 1983. | MR | Zbl

[7] D. Gordon, On the Computational Power of Totalistic Cellular Automata. Math. Systems Theory, 20, 1987, 43-52. | DOI | MR | Zbl

[8] K. Lindgren - M. G. Nordahl, Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems, 4, 1990, 299-318. | MR | Zbl

[9] M. Margenstern, Frontier between decidability and undecidability: a survey. In: M. Margenstern (ed.), Proceedings of MCU’98. Vol. II, Metz 1998, 141-177. | Zbl

[10] M. Minski, Computation: Finite and Infinite machines. Prentice Hall, 1967. | MR | Zbl

[11] Ju. V. Rogozhin, Small universal Turing machines. Theor. Comp. Sci., 168-2, 1987. | DOI | MR | Zbl

[12] C. E. Shannon, A Universal Turing machine With Two Internal States. In: C. E. Shannon - J. McCarthy (eds.), Automata Studies. Princeton University Press, 1956. | MR

[13] A. R. Smith Iii, Simple Computational-Universal Cellular Spaces. J. of ACM, 18, 1971. | MR | Zbl

[14] S. Wolfram, Statistical Mechanics of Cellular Automata. Rev. Modern Physics, 55, 1983, 601-644. | DOI | MR | Zbl

[15] S. Wolfram (ed.), Theory and Application of Cellular Automata. Advanced series on complex systems, 1, World Scientific, 1987. | MR | Zbl