Skip to main content
SpringerLink
Log in

The Quest for Small Universal Cellular Automata

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 2002)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2380))

Included in the following conference series:

Abstract

We formalize the idea of intrinsically universal cellular automata, which is strictly stronger than classical computational universality. Thanks to this uniform notion, we construct a new one-dimensional universal automaton with von Neumann neighborhood and only 6 states, thus improving the best known lower bound both for computational and intrinsic universality.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. J. Albert and K. Čulik II, A simple universal cellular automaton and its one-way and totalistic version, Complex Systems, 1(1987), no. 1, 1–16.

    MATH  MathSciNet  Google Scholar 

  2. E. R. Banks, Universality in cellular automata, in Conference Record of 1970 Eleventh Annual Symposium on Switching and Automata Theory, pages 194–215, IEEE, 1970.

    Google Scholar 

  3. E. Codd, Cellular Automata, Academic Press, 1968.

    Google Scholar 

  4. M. Kudlek and Y. Rogozhin, New small universal circular Post machines, in R. Freivalds, editor, Proceedings of FCT’2001, volume 2138 of LNCS, pages 217–226, 2001.

    Google Scholar 

  5. K. Lindgren and M. G. Nordahl, Universal computation in simple one-dimensional cellular automata, Complex Systems, 4(1990), 299–318.

    MATH  MathSciNet  Google Scholar 

  6. J. Mazoyer and I. Rapaport, Inducing an order on cellular automata by a grouping operation, Discrete Appl. Math., 218(1999), 177–196.

    Article  MathSciNet  Google Scholar 

  7. M. Minsky, Finite and Infinite Machines, Prentice Hall, 1967.

    Google Scholar 

  8. N. Ollinger, Toward an algorithmic classification of cellular automata dynamics, 2001, LIP RR2001-10, http://www.ens-lyon.fr/LIP.

  9. N. Ollinger, Two-states bilinear intrinsically universal cellular automata, in R. Freivalds, editor, Proceedings of FCT’2001, volume 2138 of LNCS, pages 396–399, 2001.

    Google Scholar 

  10. C. E. Shannon, A universal Turing machine with two internal states, Ann. Math. Stud., 34(1956), 157–165.

    MathSciNet  Google Scholar 

  11. A. R. Smith III, Simple computation-universal cellular spaces, J. ACM, 18(1971), no. 3, 339–353.

    Article  MATH  Google Scholar 

  12. J. von Neumann, Theory of Self-reproducing Automata, University of Illinois Press, Chicago, 1966.

    Google Scholar 

  13. I. Wegener, The complexity of boolean functions, Wiley-Teubner, 1987.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIP, Ecole Normale Supérieure de Lyon, 46, allée d’Italie, 69 364, Lyon Cedex 07, France

    Nicolas Ollinger

Authors
  1. Nicolas Ollinger
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Theoretical Computer Science, ETH Zentrum, ETH Zürich, 8092, Zürich, Switzerland

    Peter Widmayer  & Stephan Eidenbenz  & 

  2. Department of Languages and Sciences of the Computation E.T.S. de Ingeniería Informática, University of Málaga, Campus de Teatinos, 29071, Málaga, Spain

    Francisco Triguero , Rafael Morales  & Ricardo Conejo ,  & 

  3. School of Cognitive and Computing Sciences, University of Sussex, Falmer, Brighton, BN1 9QN, UK

    Matthew Hennessy

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ollinger, N. (2002). The Quest for Small Universal Cellular Automata. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds) Automata, Languages and Programming. ICALP 2002. Lecture Notes in Computer Science, vol 2380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45465-9_28

Download citation

  • DOI: https://doi.org/10.1007/3-540-45465-9_28

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-43864-9

  • Online ISBN: 978-3-540-45465-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation