Universal Reversible Turing Machines with a Small Number of Tape Symbols

• Autorzy: Morita K.

Identyfikatory

DOI

10.3233/FI-2015-1195

• Języki publikacji: EN

Abstrakty

EN

We study the problem of finding small universal reversible Turing machines (URTMs) with four symbols or less. Here, we present two models of URTMs: a 24-state 4-symbol URTM, and a 32-state 3-symbol URTM. Both of them are designed so that they can simulate cyclic tag systems, a kind of string rewriting systems that are universal. By converting the 24-state 4-symbol URTM into a 2-symbol machine, we also obtain a 138-state 2-symbol URTM.

Słowa kluczowe

EN

reversible computing; universal Turing machine; cyclic tag system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 17--29
• Opis fizyczny: Bibliogr. 13 poz., tab., wykr.

Twórcy

autor

Morita K.

• Hiroshima University Higashi-Hiroshima, 739-8527, Japan

Bibliografia

• [1] Axelsen, H., Gl¨uck, R.: A simple and efficient universal reversible Turing machines, Proc. LATA 2011, LNCS 6638, Springer-Verlag, 2011.
• [2] Bennett, C. H.: Logical reversibility of computation, IBM J. Res. Dev., 17, 1973, 525–532.
• [3] Cocke, J., Minsky, M.: Universality of tag systems with P = 2, J. Assoc. Comput. Mach., 11, 1964, 15–20.
• [4] Cook, M.: Universality in elementary cellular automata, Complex Syst., 15, 2004, 1–40.
• [5] Kudlek, M., Rogozhin, Y.: A universal Turing machine with 3 states and 9 symbols, Proc. on DLT 2001, LNCS 2295, Springer-Verlag, 2002.
• [6] Minsky, M.: Computation: Finite and Infinite Machines, Prentice-Hall, Englewood Cliffs, NJ, 1967.
• [7] Morita, K.: Reversible computing and cellular automata — A survey, Theoret. Comput. Sci., 395, 2008, 101–131.
• [8] Morita, K.: Reversible Turing machines with a small number of states, Proc. Sixth Workshop on Non-Classical Models of Automata and Applications (NCMA 2014), 2014.
• [9] Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine, Trans. IEICE Japan, E-72, 1989, 223–228.
• [10] Morita, K., Yamaguchi, Y.: A universal reversible Turing machine, Proc. 5th Int. Conf. on Machines, Computations, and Universality, LNCS 4664, Springer-Verlag, 2007.
• [11] Neary, T.,Woods, D.: Four small universal Turing machines, Fundamenta Informaticae, 91, 2009, 123–144.
• [12] Rogozhin, Y.: Small universal Turing machines, Theoret. Comput. Sci., 168, 1996, 215–240.
• [13] Woods, D., Neary, T.: The complexity of small universal Turing machines: A survey, Theoret. Comput. Sci., 410, 2009, 443–450.