Document Open Access Logo

Idempotent Turing Machines

Author Keisuke Nakano

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.79.pdf
  • Filesize: 0.78 MB
  • 18 pages

Document Identifiers

Author Details

Keisuke Nakano
  • Research Institute of Electrical Communication, Tohoku University, Sendai, Japan

Funding

This work was partially supported by JSPS KAKENHI Grant Numbers JP21K11744, JP18H04093 and JP17H06099.

Acknowledgements

I am grateful to Mirai Ikebuchi for careful proofreading of earlier drafts of this manuscript. I also want to thank anonymous reviewers for their helpful comments.

Cite AsGet BibTex

Keisuke Nakano. Idempotent Turing Machines. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 79:1-79:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.79

Abstract

A function f is said to be idempotent if f(f(x)) = f(x) holds whenever f(x) is defined. This paper presents a computation model for idempotent functions, called an idempotent Turing machine. The computation model is necessarily and sufficiently expressive in the sense that not only does it always compute an idempotent function but also every idempotent computable function can be computed by an idempotent Turing machine. Furthermore, a few typical properties of the computation model such as robustness and universality are shown. Our computation model is expected to be a basis of special-purpose (or domain-specific) programming languages in which only but all idempotent computable functions can be defined.

Subject Classification

ACM Subject Classification
  • Theory of computation → Turing machines
Keywords
  • Turing machines
  • Idempotent functions
  • Computable functions
  • Computation model

Metrics

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

References

  1. Holger Bock Axelsen and Robert Glück. What Do Reversible Programs Compute? In Foundations of Software Science and Computational Structures - 14th International Conference, FOSSACS 2011, Saarbrücken, Germany, March 26-April 3, 2011. Proceedings, pages 42-56, 2011. URL: https://doi.org/10.1007/978-3-642-19805-2_4.
  2. Holger Bock Axelsen and Robert Glück. On reversible Turing machines and their function universality. Acta Inf., 53(5):509-543, 2016. URL: https://doi.org/10.1007/s00236-015-0253-y.
  3. Charles 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.
  4. Sebastian Fischer, Zhenjiang Hu, and Hugo Pacheco. The essence of bidirectional programming. Sci. China Inf. Sci., 58(5):1-21, 2015. URL: https://doi.org/10.1007/s11432-015-5316-8.
  5. J. Nathan Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan Schmitt. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Trans. Program. Lang. Syst., 29(3):17, 2007. URL: https://doi.org/10.1145/1232420.1232424.
  6. Anahí Gajardo, Jarkko Kari, and Andrés Moreira. On time-symmetry in cellular automata. J. Comput. Syst. Sci., 78(4):1115-1126, 2012. URL: https://doi.org/10.1016/j.jcss.2012.01.006.
  7. Robert Glück and Tetsuo Yokoyama. A Linear-Time Self-Interpreter of a Reversible Imperative Language. Computer Software, 33(3):3_108-3_128, 2016. URL: https://doi.org/10.11309/jssst.33.3_108.
  8. Pieter Hooimeijer, Benjamin Livshits, David Molnar, Prateek Saxena, and Margus Veanes. Fast and Precise Sanitizer Analysis with BEK. In 20th USENIX Security Symposium, San Francisco, CA, USA, August 8-12, 2011, Proceedings. USENIX Association, 2011. Google Scholar
  9. Martin Kutrib and Thomas Worsch. Time-Symmetric Machines. In Reversible Computation - 5th International Conference, RC 2013, Victoria, BC, Canada, July 4-5, 2013. Proceedings, pages 168-181, 2013. URL: https://doi.org/10.1007/978-3-642-38986-3_14.
  10. R. Landauer. Irreversibility and Heat Generation in the Computing Process. IBM Journal of Research and Development, 5(3):183-191, July 1961. URL: https://doi.org/10.1147/rd.53.0183.
  11. Yves Lecerf. Machines de Turing réversibles. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, 257:2597-2600, 1963. Google Scholar
  12. John McCarthy. The Inversion of Functions Defined by Turing Machines. In Automata Studies. (AM-34), pages 177-182. Princeton University Press, 1956. URL: https://doi.org/10.1515/9781400882618-009.
  13. Shin-Cheng Mu, Zhenjiang Hu, and Masato Takeichi. An Injective Language for Reversible Computation. In Dexter Kozen and Carron Shankland, editors, Mathematics of Program Construction, 7th International Conference, MPC 2004, Stirling, Scotland, UK, July 12-14, 2004, Proceedings, volume 3125 of Lecture Notes in Computer Science, pages 289-313. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-27764-4_16.
  14. Keisuke Nakano. Involutory Turing Machines. In Ivan Lanese and Mariusz Rawski, editors, Reversible Computation - 12th International Conference, RC 2020, Oslo, Norway, July 9-10, 2020, Proceedings, volume 12227 of Lecture Notes in Computer Science, pages 54-70. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-52482-1_3.
  15. Keisuke Nakano. A Tangled Web of 12 Lens Laws. In Shigeru Yamashita and Tetsuo Yokoyama, editors, Reversible Computation - 13th International Conference, RC 2021, Virtual Event, July 7-8, 2021, Proceedings, volume 12805 of Lecture Notes in Computer Science, pages 185-203. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-79837-6_11.
  16. OWASP. Double Encoding. https://owasp.org/www-community/Double_Encoding. [Online; 21-January-2021].
  17. Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, Boston, MA, 1997. Google Scholar
  18. Tetsuo Yokoyama, Holger Bock Axelsen, and Robert Glück. Principles of a reversible programming language. In Proceedings of the 5th Conference on Computing Frontiers, 2008, Ischia, Italy, May 5-7, 2008, pages 43-54, 2008. URL: https://doi.org/10.1145/1366230.1366239.
  19. Tetsuo Yokoyama, Holger Bock Axelsen, and Robert Glück. Reversible Flowchart Languages and the Structured Reversible Program Theorem. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, volume 5126 of Lecture Notes in Computer Science, pages 258-270. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70583-3_22.
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 Imprint Privacy Contact