Document Open Access Logo

Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything (Invited Talk)

Author Siamak Taati

PDF
Thumbnail PDF

File

OASIcs.AUTOMATA.2021.3.pdf
  • Filesize: 0.65 MB
  • 15 pages

Document Identifiers

Author Details

Siamak Taati
  • Department of Mathematics, American University of Beirut, Lebanon

Cite As Get BibTex

Siamak Taati. Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything (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. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.AUTOMATA.2021.3

Abstract

We consider reversible and surjective cellular automata perturbed with noise. We show that, in the presence of positive additive noise, the cellular automaton forgets all the information regarding its initial configuration exponentially fast. In particular, the state of a finite collection of cells with diameter n becomes indistinguishable from pure noise after O(log n) time steps. This highlights the seemingly unavoidable need for irreversibility in order to perform scalable reliable computation in the presence of noise.

Subject Classification

ACM Subject Classification
  • Hardware → Reversible logic
  • Hardware → Fault tolerance
  • Theory of computation → Parallel computing models
  • Mathematics of computing → Stochastic processes
  • Mathematics of computing → Information theory
Keywords
  • Reversible cellular automata
  • surjective cellular automata
  • noise
  • probabilistic cellular automata
  • ergodicity
  • entropy
  • reversible computing
  • reliable computing
  • fault tolerance

Metrics

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

References

  1. D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan. Limitations of noisy reversible computation, 1996. URL: http://arxiv.org/abs/quant-ph/9611028.
  2. C. H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17(6):525-532, 1973. URL: https://doi.org/10.1147/rd.176.0525.
  3. C. H. Bennett. The thermodynamics of computation - a review. International Journal of Theoretical Physics, 21(12):905-940, 1982. URL: https://doi.org/10.1007/BF02084158.
  4. C. H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing, 18(4):766-776, 1989. URL: https://doi.org/10.1137/0218053.
  5. P. Berman and J. Simon. Investigations of fault-tolerant networks of computers. In STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 66-77. ACM, 1988. URL: https://doi.org/10.1145/62212.62219.
  6. M. Bramson and C. Neuhauser. Survival of one-dimensional cellular automata under random perturbations. The Annals of Probability, 22(1):244-263, 1994. URL: https://doi.org/10.1214/aop/1176988858.
  7. B. Chopard and M. Droz. Cellular Automata Modeling of Physical Systems. Cambridge University Press, 1998. URL: https://doi.org/10.1017/CBO9780511549755.
  8. T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, second edition, 2006. URL: https://doi.org/10.1002/047174882X.
  9. E. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21(3/4):219-253, 1982. URL: https://doi.org/10.1007/BF01857727.
  10. P. 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.
  11. P. 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.
  12. P. Gács. Reliable computation, 2005. URL: https://www.cs.bu.edu/fac/gacs/.
  13. P. Gács and J. Reif. A simple three-dimensional real-time reliable cellular array. Journal of Computer and System Sciences, 36(2):125-147, 1988. URL: https://doi.org/10.1016/0022-0000(88)90024-4.
  14. P. Gács and I. Törmä. Stable multi-level monotonic eroders, 2018. URL: http://arxiv.org/abs/1809.09503.
  15. G. Hedlund. Endomorphisms and automorphisms of shift dynamical systems. Mathematical Systems Theory, 3:320-375, 1969. URL: https://doi.org/10.1007/BF01691062.
  16. J. Kari. Reversibility and surjectivity problems of cellular automata. Journal of Computer and System Sciences, 48(1):149-182, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80025-X.
  17. J. Kari. Reversible cellular automata: From fundamental classical results to recent developments. New Generation Computing, 36:145-172, 2018. URL: https://doi.org/10.1007/s00354-018-0034-6.
  18. R. Landauer. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5(3):183-191, 1961. URL: https://doi.org/10.1147/rd.53.0183.
  19. D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2009. Google Scholar
  20. I. Marcovici, M. Sablik, and S. Taati. Ergodicity of some classes of cellular automata subject to noise. Electronic Journal of Probability, 24(41), 2019. URL: https://doi.org/10.1214/19-EJP297.
  21. I. Marcovici and S. Taati, In preparation. Google Scholar
  22. N. Margolus. Physics-like models of computation. Physica D: Nonlinear Phenomena, 10(1-2):81-95, 1984. URL: https://doi.org/10.1016/0167-2789(84)90252-5.
  23. M. McCann and N. Pippenger. Fault tolerance in cellular automata at high fault rates. Journal of Computer and System Sciences, 74(5):910-918, 2008. URL: https://doi.org/10.1016/j.jcss.2008.02.003.
  24. E. F. Moore. Machine models of self-reproduction. In Mathematical Problems in the Biological Sciences, volume 14 of Proceedings of Symposia in Applied Mathematics, pages 17-33. American Mathematical Society, 1962. Google Scholar
  25. K. Morita. Reversible computing and cellular automata - a survey. Theoretical Computer Science, 395(1):101-131, 2008. URL: https://doi.org/10.1016/j.tcs.2008.01.041.
  26. K. Morita and M. Harao. Computation universality of one-dimensional reversible (injective) cellular automata. The Transactions of the IEICE, E72(6):758-762, 1989. Google Scholar
  27. J. Myhill. The converse of Moore’s Garden-of-Eden theorem. Proceedings of the American Mathematical Society, 14(4):685-686, 1963. URL: https://doi.org/10.2307/2034301.
  28. V. Salo and I. Törmä. A one-dimensional physically universal cellular automaton. In J. Kari, F. Manea, and I. Petre, editors, CiE 2017: Unveiling Dynamics and Complexity, volume 10307 of LNCS, pages 375-386. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-58741-7_35.
  29. L. Schaeffer. A physically universal cellular automaton. In ITCS '15: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 237-246. ACM, 2015. URL: https://doi.org/10.1145/2688073.2688107.
  30. T. Toffoli. Computation and construction universality of reversible cellular automata. Journal of Computer and System Sciences, 15(2):213-231, 1977. URL: https://doi.org/10.1016/S0022-0000(77)80007-X.
  31. T. Toffoli and N. Margolus. Cellular Automata Machines. MIT Press, 1987. Google Scholar
  32. T. Toffoli and N. Margolus. Invertible cellular automata: A review. Physica D: Nonlinear Phenomena, 45(1-3):229-253, 1990. URL: https://doi.org/10.1016/0167-2789(90)90185-R.
  33. A. Toom. Stable and attractive trajectories in multicomponent systems. In R. L. Dobrushin and Ya. G. Sinai, editors, Multicomponent Random Systems, pages 549-575. Marcel Dekker, 1980. Google Scholar
  34. A. L. Toom, N. B. Vasilyev, O. N. Stavskaya, L. G. Mityushin, G. L. Kuryumov, and S. A. Pirogov. Discrete local Markov systems. In R. L. Dobrushin, V. I. Kryukov, and A. L. Toom, editors, Stochastic cellular systems: ergodicity, memory, morphogenesis. Manchester University Press, 1990. Google Scholar
  35. G. Y. Vichniac. Simulating physics with cellular automata. Physica D: Nonlinear Phenomena, 10(1-2):96-116, 1984. URL: https://doi.org/10.1016/0167-2789(84)90253-7.
  36. J. von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In C. E. Shannon and J. McCarthy, editors, Automata Studies, pages 43-98. Princeton University Press, 1956. URL: https://doi.org/10.1515/9781400882618.
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