Universal Reversible Turing Machines with a Small Number of Tape Symbols

Issue title: Special issue in memoriam of Yurii Rogozhin

Article type: Research Article

Authors: Morita, Kenichi

Affiliations: Hiroshima University, Higashi-Hiroshima, 739-8527, Japan. km@hiroshima-u.ac.jp

Note: [] Address for correspondence: Hiroshima University, Higashi-Hiroshima, 739-8527, Japan

Abstract: 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.

Keywords: reversible computing, universal Turing machine, cyclic tag system

DOI: 10.3233/FI-2015-1195

Journal: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 17-29, 2015