Some results on cellular automata

Claudio Baiocchi

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni (1998)

  • Volume: 9, Issue: 4, page 307-316
  • ISSN: 1120-6330

Abstract

top
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.

How to cite

top

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 9.4 (1998): 307-316. <http://eudml.org/doc/252444>.

@article{Baiocchi1998,
abstract = {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.},
author = {Baiocchi, Claudio},
journal = {Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni},
keywords = {Cellular automata; Turing machine; Totalistic automata; totalistic automata; generic cellular automaton},
language = {eng},
month = {12},
number = {4},
pages = {307-316},
publisher = {Accademia Nazionale dei Lincei},
title = {Some results on cellular automata},
url = {http://eudml.org/doc/252444},
volume = {9},
year = {1998},
}

TY - JOUR
AU - Baiocchi, Claudio
TI - Some results on cellular automata
JO - Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni
DA - 1998/12//
PB - Accademia Nazionale dei Lincei
VL - 9
IS - 4
SP - 307
EP - 316
AB - 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.
LA - eng
KW - Cellular automata; Turing machine; Totalistic automata; totalistic automata; generic cellular automaton
UR - http://eudml.org/doc/252444
ER -

References

top
  1. Albert, J. - Culik II, K., A Simple Universal Cellular Automaton and its One-Way and Totalistic Version. Complex Systems, 1, 1987, 1-16. Zbl0655.68065MR891509
  2. Baiocchi, C., Qualche risultato sugli automi cellulari. Rend. Ist. Lombardo, to appear. 
  3. Balzer, R., An 8-state minimal time solution to the firing squad sincronization problem. Information and Control, 10, 1967, 22-42. 
  4. Berlekamp, E. R. - Conway, J. H. - Guy, R. K., Winning Ways for Your Mathematical Plays. Academic Press, London1982. Zbl1083.00003
  5. Dewdney, A. K., Computer recreations. Sci. Amer., 224, 1971, 226, 1972. 
  6. Gardner, M., Wheels, Life and other mathematical amusements. Freeman, 1983. Zbl0537.00002MR717760
  7. Gordon, D., On the Computational Power of Totalistic Cellular Automata. Math. Systems Theory, 20, 1987, 43-52. Zbl0627.68049MR901893DOI10.1007/BF01692058
  8. Lindgren, K. - Nordahl, M. G., Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems, 4, 1990, 299-318. Zbl0724.68072MR1065013
  9. Margenstern, M., Frontier between decidability and undecidability: a survey. In: M. Margenstern (ed.), Proceedings of MCU’98. Vol. II, Metz1998, 141-177. Zbl0956.03041
  10. Minski, M., Computation: Finite and Infinite machines. Prentice Hall, 1967. Zbl0195.02402MR356580
  11. Rogozhin, Ju. V., Small universal Turing machines. Theor. Comp. Sci., 168-2, 1987. Zbl0874.68106MR1422956DOI10.1016/S0304-3975(96)00077-1
  12. Shannon, C. E., A Universal Turing machine With Two Internal States. In: C. E. Shannon - J. McCarthy (eds.), Automata Studies. Princeton University Press, 1956. MR79548
  13. Smith III, A. R., Simple Computational-Universal Cellular Spaces. J. of ACM, 18, 1971. Zbl0221.94071MR294067
  14. Wolfram, S., Statistical Mechanics of Cellular Automata. Rev. Modern Physics, 55, 1983, 601-644. Zbl1174.82319MR709077DOI10.1103/RevModPhys.55.601
  15. S. Wolfram (ed.), Theory and Application of Cellular Automata. Advanced series on complex systems, 1, World Scientific, 1987. Zbl0609.68043MR857608

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.