Document Open Access Logo

Fixed Point Constructions in Tilings and Cellular Automata (Invited Talk)

Author Ilkka Törmä

PDF
Thumbnail PDF

File

OASIcs.AUTOMATA.2021.4.pdf
  • Filesize: 0.61 MB
  • 13 pages

Document Identifiers

Author Details

Ilkka Törmä
  • Department of Mathematics and Statistics, University of Turku, Finland

Cite As Get BibTex

Ilkka Törmä. Fixed Point Constructions in Tilings and Cellular Automata (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.AUTOMATA.2021.4

Abstract

The fixed point construction is a method for designing tile sets and cellular automata with highly nontrivial dynamical and computational properties. It produces an infinite hierarchy of systems where each layer simulates the next one. The simulations are implemented entirely by computations of Turing machines embedded in the tilings or spacetime diagrams. We present an overview of the construction and list its applications in the literature.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • Tilings
  • Wang tiles
  • cellular automata
  • multidimensional symbolic dynamics
  • self-simulation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nathalie Aubrun and Mathieu Sablik. Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Applicandae Mathematicae, 126:35-63, 2013. URL: https://doi.org/10.1007/s10440-013-9808-5.
  2. Robert Berger. The undecidability of the domino problem. Memoirs of the American Mathematical Society, 66, 1966. 72 pages. Google Scholar
  3. Mike Boyle and Douglas Lind. Expansive subdynamics. Transactions of the American Mathematical Society, 349(1):55-102, 1997. URL: https://doi.org/10.1090/S0002-9947-97-01634-6.
  4. Ilir Çapuni and Péter Gács. A Turing machine resisting isolated bursts of faults. Chicago Journal of Theoretical Computer Science, 2013(3), 2013. URL: https://doi.org/10.4086/cjtcs.2013.003.
  5. M. Delorme, J. Mazoyer, N. Ollinger, and G. Theyssier. Bulking I: an abstract theory of bulking. Theoretical Computer Science, 412(30):3866-3880, 2011. URL: https://doi.org/10.1016/j.tcs.2011.02.023.
  6. Bruno Durand, Leonid A. Levin, and Alexander Shen. Complex tilings. The Journal of Symbolic Logic, 73(2):593-613, 2008. URL: https://doi.org/10.2178/jsl/1208359062.
  7. Bruno Durand and Andrei Romashchenko. The expressiveness of quasiperiodic and minimal shifts of finite type. Ergodic Theory and Dynamical Systems, 41(4):1086-1138, 2021. URL: https://doi.org/10.1017/etds.2019.112.
  8. Bruno Durand, Andrei Romashchenko, and Alexander Shen. Fixed point and aperiodic tilings. In Developments in language theory, volume 5257 of Lecture Notes in Computer Science, pages 276-288. Springer, Berlin, 2008. URL: https://doi.org/10.1007/978-3-540-85780-8_22.
  9. Bruno Durand, Andrei Romashchenko, and Alexander Shen. Fixed point theorem and aperiodic tilings. Bulletin of the European Association for Theoretical Computer Science. EATCS, 97:126-136, 2009. Google Scholar
  10. Bruno Durand, Andrei Romashchenko, and Alexander Shen. High complexity tilings with sparse errors. In Automata, languages and programming. Part I, volume 5555 of Lecture Notes in Computer Science, pages 403-414. Springer, Berlin, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_34.
  11. Bruno Durand, Andrei Romashchenko, and Alexander Shen. Effective closed subshifts in 1D can be implemented in 2D. In Fields of logic and computation, volume 6300 of Lecture Notes in Computer Science, pages 208-226. Springer, Berlin, 2010. URL: https://doi.org/10.1007/978-3-642-15025-8_12.
  12. Bruno Durand, Andrei Romashchenko, and Alexander Shen. Fixed-point tile sets and their applications. Journal of Computer and System Sciences, 78(3):731-764, 2012. URL: https://doi.org/10.1016/j.jcss.2011.11.001.
  13. Péter Gács. Reliable computation with cellular automata. Journal of Computer and System Sciences, 32(1):15-78, 1986. URL: https://doi.org/10.1016/0022-0000(86)90002-4.
  14. Péter Gács. Reliable cellular automata with self-organization. Journal of Statistical Physics, 103(1-2):45-267, 2001. URL: https://doi.org/10.1023/A:1004823720305.
  15. Silvère Gangloff and Mathieu Sablik. Quantified block gluing, aperiodicity and entropy of multidimensional SFT. ArXiv e-prints, 2017. URL: http://arxiv.org/abs/1706.01627.
  16. Lawrence F. Gray. A reader’s guide to Gacs’s "positive rates" paper. Journal of Statistical Physics, 103(1-2):1-44, 2001. URL: https://doi.org/10.1023/A:1004824203467.
  17. Pierre Guillon and Gaétan Richard. Nilpotency and limit sets of cellular automata. In Mathematical foundations of computer science 2008, volume 5162 of Lecture Notes in Comput. Sci., pages 375-386. Springer, Berlin, 2008. URL: https://doi.org/10.1007/978-3-540-85238-4_30.
  18. Pierre Guillon and Charalampos Zinoviadis. Unpublished manuscript. Work in progress. Google Scholar
  19. Pierre Guillon and Charalampos Zinoviadis. Densities and entropies in cellular automata. In S. Barry Cooper, Anuj Dawar, and Benedict Löwe, editors, How the world computes, pages 253-263. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-30870-3_26.
  20. Michael Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae, 176(1):131-167, 2009. URL: https://doi.org/10.1007/s00222-008-0161-7.
  21. Michael Hochman. Non-expansive directions for ℤ² actions. Ergodic Theory and Dynamical Systems, 31(1):91-112, 2011. URL: https://doi.org/10.1017/S0143385709001084.
  22. Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics. Second Series, 171(3):2011-2038, 2010. URL: https://doi.org/10.4007/annals.2010.171.2011.
  23. Jarkko Kari. Theory of cellular automata: a survey. Theoretical Computer Science, 334(1-3):3-33, 2005. URL: https://doi.org/10.1016/j.tcs.2004.11.021.
  24. G. L. Kurdyumov. An example of a nonergodic one-dimensional homogeneous random medium with positive transition probabilities. Doklady Akademii Nauk SSSR, 238(6):1287-1290, 1978. URL: http://mi.mathnet.ru/eng/dan41542.
  25. Douglas Lind and Brian Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995. URL: https://doi.org/10.1017/CBO9780511626302.
  26. Jean Mairesse and Irène Marcovici. Around probabilistic cellular automata. Theoretical Computer Science, 559:42-72, 2014. URL: https://doi.org/10.1016/j.tcs.2014.09.009.
  27. Shahar Mozes. Tilings, substitution systems and dynamical systems generated by them. Journal d'Analyse Mathématique, 53:139-186, 1989. URL: https://doi.org/10.1007/BF02793412.
  28. Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12:177-209, 1971. URL: https://doi.org/10.1007/BF01418780.
  29. Ville Salo. On nilpotency and asymptotic nilpotency of cellular automata. In Enrico Formenti, editor, Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, La Marana, Corsica, September 19-21, 2012, volume 90 of Electronic Proceedings in Theoretical Computer Science, pages 86-96. Open Publishing Association, 2012. URL: https://doi.org/10.4204/EPTCS.90.7.
  30. Ville Salo and Ilkka Törmä. Nilpotent endomorphisms of expansive group actions. International Journal of Algebra and Computation, 2021. Published online. URL: https://doi.org/10.1142/S021819672150020X.
  31. Ilkka Törmä. A uniquely ergodic cellular automaton. Journal of Computer and System Sciences, 81(2):415-442, 2015. URL: https://doi.org/10.1016/j.jcss.2014.10.001.
  32. Hao Wang. Proving theorems by pattern recognition II. Bell System Technical Journal, 40:1-42, 1961. URL: https://doi.org/10.1002/j.1538-7305.1961.tb03975.x.
  33. Linda Brown Westrick. Seas of squares with sizes from a Π⁰₁ set. Israel Journal of Mathematics, 222(1):431-462, 2017. URL: https://doi.org/10.1007/s11856-017-1596-6.
  34. Charalampos Zinoviadis. Hierarchy and Expansiveness in Two-Dimensional Subshifts of Finite Type. PhD thesis, University of Turku, 2016. URL: http://urn.fi/URN:ISBN:%20978-952-12-3337-1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact