nach oben

Natural Computing

Erschienen in:

01.06.2012

Grids and universal computations on one-dimensional cellular automata

verfasst von: Jean-Baptiste Yunès

Erschienen in: Natural Computing | Ausgabe 2/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This article shows how universal computations can be achieved on one-dimensional cellular automata. We are interested in intrinsic universality: we want a CA in which any other CA can be represented and simulated with no intermediate coding relevant to another computation model. We first abstract the space-time diagram in favor of the dependency graph. Then we show how such a dependency graph (via treillis automata) can be realized by what is called a grid, leading to a simple uniform simulation. Finally, we exhibit a very simple universal brick that can be used in grids to obtain an intrinsic universal CA.

Vorheriger Artikel A study on learning robustness using asynchronous 1D cellular automata rules

Nächster Artikel On Cellular Automata rules of molecular arrays

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Albert J, Čulik K II (1987) A simple universal cellular automaton and its oneway and totalistic versions. Complex Syst 1:1–16MATH

Arrighi P, Grattage J (2010) A simple intrinsically universal n-dimensional quantum cellular automata. LATA, LNCS 2010, 6031:70–81MathSciNet

Atrubin AJ (1965) A one-dimensional real-time iterative multiplier. IEEE Trans Electr Comput 14:394–399CrossRef

Choffrut C, Čulik K II (1984) On real-time cellular automata and trellis automata. Acta Inform 21:393–407MathSciNetMATHCrossRef

Cole SN (1969) Real-time computation by n-dimensional iterative arrays of finite-states machines. IEEE Trans Comput C-18/4:349–365CrossRef

Doty D, Lutz JH, Patitz MJ, Summers SM, Woods D (2010) Intrinsic universality in self-assembly. Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), (Nancy, France, March 4–6, 2010), pp 275–286

Durand B, Róka Z (1996) The game of life: universality revisited. Proceedings of Cellular Automata 1996, Saissac, France, Academic Publishers, Dordrecht

Durand-Lose J (1997) Intrinsic universality of a 1-dimensional reversible Cellular Automaton. STACS 97, Springer, Berlin

Martin B (1994) A universal cellular automaton in quasi-linear time and its S-m-n form. Theor Comput Sci 123:199–237MATHCrossRef

Mazoyer J (1987) A six states minimal time solution to the firing squad synchronization problem. Theor Comput Sci 50:183–328MathSciNetMATHCrossRef

Mazoyer J, Terrier V (1999) Signals in one-dimensional cellular automata. Theor Comput Sci 217/1:53–80MathSciNetCrossRef

Mazoyer J, Yunès JB (2011) Computations on cellular automata. In: Rozenberg G, Bäck T, Kok J (eds) Handbook of natural computing, Springer, Berlin

Ollinger N (2003) The intrinsic universality problem of one-dimensional cellular automata. Proceedings of STACS 2003, Lecture Notes on Computer Science, pp 632–641

Poupet V (2005) Cellular automata: real-time equivalence between one-dimensional neighborhoods. STACS 2005, Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, February 24–26, Stuttgart, pp 133–144

Titel: Grids and universal computations on one-dimensional cellular automata
verfasst von: Jean-Baptiste Yunès
Publikationsdatum: 01.06.2012
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2012
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-012-9312-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2012

Fermat’s last theorem and chaoticity

Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models

Membrane system models for super-Turing paradigms

Foreword

Asynchronous cellular automata and dynamical properties

The physical Church thesis as an explanation of the Galileo thesis

Premium Partner