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_307_0,
author = {Claudio Baiocchi},
title = {Some results on cellular automata},
journal = {Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni},
volume = {9},
year = {1998},
pages = {307-316},
zbl = {0931.68072},
mrnumber = {1722789},
language = {en},
url = {http://dml.mathdoc.fr/item/RLIN_1998_9_9_4_307_0}
}
Baiocchi, Claudio. Some results on cellular automata. Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni, Tome 9 (1998) pp. 307-316. http://gdmltest.u-ga.fr/item/RLIN_1998_9_9_4_307_0/
[1] - , A Simple Universal Cellular Automaton and its One-Way and Totalistic Version. Complex Systems, 1, 1987, 1-16. | MR 891509 | Zbl 0655.68065
[2] , Qualche risultato sugli automi cellulari. Rend. Ist. Lombardo, to appear.
[3] , An 8-state minimal time solution to the firing squad sincronization problem. Information and Control, 10, 1967, 22-42.
[4] - - , Winning Ways for Your Mathematical Plays. Academic Press, London 1982. | Zbl 1083.00003
[5] , Computer recreations. Sci. Amer., 224, 1971, 226, 1972.
[6] , Wheels, Life and other mathematical amusements. Freeman, 1983. | MR 717760 | Zbl 0537.00002
[7] , On the Computational Power of Totalistic Cellular Automata. Math. Systems Theory, 20, 1987, 43-52. | MR 901893 | Zbl 0627.68049
[8] - , Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems, 4, 1990, 299-318. | MR 1065013 | Zbl 0724.68072
[9] , Frontier between decidability and undecidability: a survey. In: (ed.), Proceedings of MCU’98. Vol. II, Metz 1998, 141-177. | Zbl 0956.03041
[10] , Computation: Finite and Infinite machines. Prentice Hall, 1967. | MR 356580 | Zbl 0195.02402
[11] , Small universal Turing machines. Theor. Comp. Sci., 168-2, 1987. | MR 1422956 | Zbl 0874.68106
[12] , A Universal Turing machine With Two Internal States. In: - (eds.), Automata Studies. Princeton University Press, 1956. | MR 79548
[13] , Simple Computational-Universal Cellular Spaces. J. of ACM, 18, 1971. | MR 294067 | Zbl 0221.94071
[14] , Statistical Mechanics of Cellular Automata. Rev. Modern Physics, 55, 1983, 601-644. | MR 709077 | Zbl 1174.82319
[15] (ed.), Theory and Application of Cellular Automata. Advanced series on complex systems, 1, World Scientific, 1987. | MR 857608 | Zbl 0609.68043