Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Basic Concepts of Cellular Automata Kapitel lesen Erstes Kapitel lesen

2012 | OriginalPaper | Buchkapitel

Universalities in Cellular Automata*

verfasst von : Nicolas Ollinger

Erschienen in: Handbook of Natural Computing

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

This chapter is dedicated to computational universalities in cellular automata, essentially Turing universality, the ability to compute any recursive function, and intrinsic universality, the ability to simulate any other cellular automaton. Constructions of Boolean circuits simulation in the two-dimensional case are explained in detail to achieve both kinds of universality. A detailed chronology of seminal papers is given, followed by a brief discussion of the formalization of universalities. The more difficult one-dimensional case is then discussed. Seminal universal cellular automata and encoding techniques are presented in both dimensions.

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
Vorheriges Kapitel Computations on Cellular Automata
Nächstes Kapitel Reversible Cellular Automata
Fußnoten
1
*A preliminary version of this work appeared under the title Universalities in Cellular Automata: A (Short) Survey in the proceedings of the first edition of the JAC conference (Ollinger 2008).
 
Literatur
Albert J, Čulik II K (1987) A simple universal cellular automaton and its one-way and totalistic version. Complex Syst 1(1):1–16MATH
Amoroso S, Patt YN (1972) Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J Comput Syst Sci 6:448–464MathSciNetMATHCrossRef
Arbib MA (1966) Simple self-reproducing universal automata. Info Control 9(2):177–189MATHCrossRef
Banks ER (1970) Universality in cellular automata. In: Symposium on switching and automata theory, Santa Monica, 1970. IEEE, New York, pp 194–215
Banks ER (1971) Information processing and transmission in cellular automata. Ph.D. thesis, Massachusetts Institute of Technology
Bennett CH (1973) Logical reversibility of computation. IBM J Res Dev 17(6):525–532MATHCrossRef
Berlekamp ER, Conway JH, Guy RK (1982) Winning ways for your mathematical plays, vol 2, Games in particular. Academic Press [Harcourt Brace Jovanovich Publishers], London
Burks AW (1970a) Von Neumann's self-reproducing automata. In: Burks AW (ed) Essays on cellular automata. University of Illinois Press, Urbana, IL, pp 3–64 (Essay one)
Burks AW (1970b) Programming and the theory of automata. In: Burks AW (ed) Essays on cellular automata. University of Illinois Press, Urbana, IL, pp 65–83 (Essay two)
Burks AW (1970c) Towards a theory of automata based on more realistic primitive elements. In: Burks AW (ed) Essays on cellular automata. University of Illinois Press, Urbana, IL, pp 84–102 (Essay three)
Codd EF (1968) Cellular automata. Academic Press, New YorkMATH
Cook M (2004) Universality in elementary cellular automata. Complex Syst 15:1–40MATH
Davis MD (1956) A note on universal turing machines. In: Shannon CE, McCarthy J (eds) Automata studies. Princeton University Press, Princeton, NJ, pp 167–175
Davis MD (2000) The universal computer: The road from Leibniz to Turing. W.W. Norton, New York
Delorme M (1999) An introduction to cellular automata: some basic definitions and concepts. In: Delorme M, Mazoyer J (eds) Cellular automata (Saissac, 1996). Kluwer, Dordrecht, pp 5–49
Delvenne J, Kurka P, Blondel VD (2006) Decidability and universality in symbolic dynamical systems. Fundam Info 74(4):463–490MathSciNetMATH
Dewdney AK (1990) The cellular automata programs that create Wireworld, Rugworld and other diversions. Sci Am 262:146–149CrossRef
Dubacq JC (1995) How to simulate Turing machines by invertible one-dimensional cellular automata. Int J Found Comput Sci 6(4):395–402MATHCrossRef
Durand B, Róka Z (1999) The Game of Life: universality revisited. In: Delorme M, Mazoyer J (eds) Cellular automata (Saissac, 1996). Kluwer, Dordrecht, pp 51–74
Durand-Lose J (1995) Reversible cellular automaton able to simulate any other reversible one using partitioning automata. In: Baeza-Yates RA, Goles E, Poblete PB (eds) LATIN '95, Valparaiso, 1995. Lecture notes in computer science, vol 911. Springer, Berlin/New York, pp 230–244
Durand-Lose J (1996) Automates cellulaires, automates partitions et tas de sable. Ph.D. thesis, Université Bordeaux I
Durand-Lose J (1997) Intrinsic universality of a 1-dimensional reversible cellular automaton. In: STACS 97 (Lübeck), Lecture notes in computer science, vol 1200. Springer, Berlin, pp 439–450
Gajardo A, Ch EG (2001) Universal cellular automaton over a hexagonal tiling with 3 states. IJAC 11(3):335–354MATH
Gardner M (1970) Mathematical games: The fantastic combinations of John Conway's new solitaire game ‘Life’. Sci Am 223(4):120–123CrossRef
Gödel K (1931) Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 38:173–198. Reprinted in Feferman S, Dawson W, Kleene SC, Moore G, Solovay RM, van Heijendort J (eds) (1986) Kurt Gödel: Collected works, vol 1. Oxford University Press, Oxford, pp 144–195CrossRef
Hertling P (1998) Embedding cellular automata into reversible ones. In: Calude CS, Casti J, Dinneen MJ (eds) Unconventional models of computation. Springer
Imai K, Morita K (2000) A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theor Comput Sci 231(2):181–191MathSciNetMATHCrossRef
Kari J (1990) Reversibility of 2D cellular automata is undecidable. Phys D. Nonlinear Phenomena 45(1–3):379–385. Cellular automata: theory and experiment, Los Alamos, NM, 1989MathSciNetMATHCrossRef
Kleene SC (1956) Representation of events in nerve nets and finite automata. In: Shannon CE, McCarthy J (eds) Automata studies. Princeton University Press, Princeton, NJ, pp 3–41
Lafitte G (2008) Gödel incompleteness revisited. In: Durand B (ed) Symposium on cellular automata journes automates cellulaires, JAC'2008, Uzès, 2008. MCCME, Moscow, pp 74–89
Langton C (1984) Self-reproduction in cellular automata. Phys D 10(1–2):135–144CrossRef
Lecerf Y (1963) Machines de Turing réversibles. C R Acad Sci Paris 257:2597–2600MathSciNet
Lindgren K, Nordahl MG (1990) Universal computation in simple one-dimensional cellular automata. Complex Syst 4(3):299–318MathSciNetMATH
Martin B (1993) Construction modulaire d'automates cellulaires. Ph.D. thesis, École Normale Supérieure de Lyon
Martin B (1994) A universal cellular automaton in quasilinear time and its S-m-n form. Theor Comput Sci 123(2):199–237MATHCrossRef
Mazoyer J (1999) Computations on grids. In: Cellular automata (Saissac, 1996). Kluwer, Dordrecht, pp 119–149
Mazoyer J, Rapaport I (1999) Inducing an order on cellular automata by a grouping operation. Discrete Appl Math 91(1–3):177–196MathSciNetMATHCrossRef
Mazoyer J, Terrier V (1999) Signals in one-dimensional cellular automata. Theor Comput Sci 217(1):53–80. Cellular automata, Milan, 1996MathSciNetMATHCrossRef
Miller DB, Fredkin E (2005) Two-state, reversible, universal cellular automata in three dimensions. In: Bagherzadeh N, Valero M, Ramírez A (eds) Proceedings of the conference on computing frontiers, Ischia, pp 45–51. ACMCrossRef
Minsky M (1967) Computation: finite and infinite machines. Prentice Hall, Englewoods Cliffs, NJMATH
Moore EF (1962) Machine models of self-reproduction. In: Proceedings of symposia in applied mathematics, vol 14, 1962. American Mathematical Society, Providence, pp 17–33
Moore EF (1970) Machine models of self-reproduction. In: Burks AW (ed) Essays on cellular automata. University of Illinois Press, Urbana, IL, pp 187–203 (Essay six)
Morita K (1990) A simple construction method of a reversible finite automaton out of Fredkin gates, and its related problem. IEICE Trans Info Syst E73(6):978–984
Morita K (1995) Reversible simulation of one-dimensional irreversible cellular automata. Theor Comput Sci 148(1):157–163MATHCrossRef
Morita K, Harao M (1989) Computation universality of one-dimensional reversible (injective) cellular automata. IEICE Trans Info Syst E72:758–762
Morita K, Imai K (2001) Number-conserving reversible cellular automata and their computation-universality. Theor Info Appl 35(3):239–258MathSciNetMATHCrossRef
Neary T, Woods D (2006) P-completeness of cellular automaton rule 110. In: Proceedings of ICALP 2006, Venice. Lecture notes in Computer science, vol 4051. Springer, Berlin, pp 132–143
von Neumann J (1966) In: Burks AW (ed) Theory of self-reproducing automata. University of Illinois Press, Urbana, IL
Noural F, Kashef R (1975) A universal four-state cellular computer. IEEE Trans Comput 24(8):766–776CrossRef
Odifreddi PG (1989) Classical recursion theory. Elsevier, AmsterdamMATH
Ollinger N (2001) Two-states bilinear intrinsically universal cellular automata. In: Freivalds R (ed) Fundamentals of computation theory, Riga, 2001. Lecture notes in computer science, vol 2138. Springer, Berlin, pp 396–399CrossRef
Ollinger N (2002a) Automates cellulaires: structures. Ph.D. thesis, École Normale Supérieure de Lyon
Ollinger N (2002b) The quest for small universal cellular automata. In: Widmayer P, Triguero F, Morales R, Hennessy M, Eidenbenz S, Conejo R (eds) International colloquium on automata, languages and programming, (Málaga, 2002). Lecture notes in computer science, vol 2380. Springer, Berlin, pp 318–329CrossRef
Ollinger N (2003) The intrinsic universality problem of one-dimensional cellular automata. In: Symposium on theoretical aspects of computer science, Berlin, 2003. Lecture notes in computer science. Springer, Berlin, doi:10.1007/3-540-36494-3_55
Ollinger N (2008) Universalities in cellular automata: a (short) survey. In: Durand B (ed) Symposium on cellular automata journes automates cellulaires, JAC'2008, Uz̀es. MCCME, Moscow, pp 102–118
Ollinger N, Richard G (2008) A particular universal cellular automaton. In: Neary T, Woods D, Seda AK, Murphy N (eds) CSP. Cork University Press, Cork, Ireland
Perrin D (1995) Les débuts de la théorie des automates. Tech Sci Info 14:409–433MathSciNet
Post E (1941) The two-valued iterative systems of mathematical logic. Princeton University Press, Princeton, NJMATH
Rapaport I (1998) Inducing an order on cellular automata by a grouping operation. Ph.D. thesis, École Normale Supérieure de Lyon
Richard G (2008) Rule 110: Universality and catenations. In: Durand B (ed) Symposium on cellular automata journes automates cellulaires, JAC'2008, Uz̀es. MCCME, Moscow, pp 141–160
Richardson D (1972) Tessellations with local transformations. J Comput Syst Sci 6:373–388MATHCrossRef
Shannon CE (1956) A universal Turing machine with two internal states. In: Shannon CE, McCarthy J (eds) Automata studies. Princeton University Press, Princeton, NJ, pp 157–165
Sutner K (2004) Universality and cellular automata. In: Margenstern M (ed) MCU 2004, Saint-Petersburg, 2004. Lecture notes in computer science, vol 3354. Springer, Berlin/Heidelberg, pp 50–59
Thatcher JW (1970a) Self-describing Turing machines and self-reproducing cellular automata. In: Burks AW (ed) Essays on cellular automata. University of Illinois Press, Urbana, IL, pp 103–131 (Essay four)
Thatcher JW (1970b) Universality in the von Neumann cellular model. In: Burks AW (ed) Essays on cellular automata. University of Illinois Press, Urbana, IL, pp 132–186 (Essay five)
Theyssier G (2005a) Automates cellulaires: un modèle de complexités. Ph.D. thesis, École Normale Supérieure de Lyon
Theyssier G (2005b) How common can be universality for cellular automata? In: STACS 2005, Stuttgart, 2005. Lecture notes in computer science, vol 3404. Springer, Berlin/Heidelberg, pp 121–132
Toffoli T (1977) Computation and construction universality of reversible cellular automata. J Comput Syst Sci 15(2):213–231MathSciNetMATHCrossRef
Turing AM (1936) On computable numbers with an application to the Entscheidungsproblem. Proc Lond Math Soc 42(2):230–265MathSciNet
Wolfram S (1984) Universality and complexity in cellular automata. Phys D Nonlinear Phenomena 10(1–2):1–35. Cellular automata: Los Alamos, NM, 1983MathSciNetCrossRef
Wolfram S (2002) A new kind of science. Wolfram Media, Champaign, ILMATH
Woods D, Neary T (2006) On the time complexity of 2-tag systems and small universal Turing machines. In: FOCS 2006, Berkeley, 2006. IEEE Computer Society, Washington, DC, pp 439–448
Woods D, Neary T (2007) The complexity of small universal Turing machines. In: Cooper SB, Löwe B, Sorbi A (eds) Computability in Europe, CiE 2007, Siena, 2007. Lecture notes in computer science, vol 4497. Springer, Berlin/Heidelberg, pp 791–799
Metadaten
Titel
Universalities in Cellular Automata*
verfasst von
Nicolas Ollinger
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
Buch
Handbook of Natural Computing

Print ISBN: 978-3-540-92909-3

Electronic ISBN: 978-3-540-92910-9

Copyright-Jahr: 2012

DOI
https://doi.org/10.1007/978-3-540-92910-9_6