On reversible Turing machines and their function universality (Q303695): Difference between revisions

This article presents a formal characterization of reversible Turing machines (RTMs) and outlines their semantics and expressive power. Largely self-contained, this article develops the basic theory from the ground up. A Turing machine is \textit{reversible} if it is deterministic and if we can define an inverse transition function for it: e.g., for a ``symbol move'', if \(\delta(q, s) = (q', s')\) for states \(q\), \(q'\) and symbols \(s\), \(s'\), then \(\delta^{-1}(q', s') = (q, s)\). The two primary issues addressed are expressivity and parametrization. Beginning with the expressive power of RTMs, \textit{J. McCarthy} [``The inversion of functions defined by Turing machines'', in: Automata studies. Princeton, NJ: Princeton University Press. 177--181 (1956)] had observed that if an injective function was computable, so was its inverse. Functions computed by RTMs are injective, and the question becomes: what injective functions are RTM-computable? If we let \([\![ T ]\!]\) be the function computed by an RTM \(T\), then we have an operation \(T \mapsto T^{-1}\) on RTMs, and \textit{C. H. Bennett} [IBM J. Res. Dev. 17, 525--532 (1973; Zbl 0267.68024)] demonstrated that if \(T\) is an RTM then \([\![ T^{-1} ]\!] = [\![ T ]\!]^{-1}\). Meanwhile, \textit{R. Landauer} [IBM J. Res. Dev. 5, 183--191 (1961; Zbl 1160.68305)] showed that for any Turing machine \(T\), there was an RTM \(L(T)\) that simulated it -- this the article characterizes as the first example of ``reversibilization'', which Bennett later tightened. Developing on this thread, the authors find that the injective functions are precisely the functions computed by RTMs. Having determined the expressive power of RTMs, the article turns to universal RTMs. Because of technical issues, the article presents the following definition: given a Turing machine \(T\), let \(\ulcorner T \urcorner\) be the string that characterizes it. A ``universal RTM'' (URTM) is an RTM \(U_{\text{RTM}}\) such that for any RTM \(T\), \([\![ U_{\text{RTM}} ]\!](\ulcorner T \urcorner, x) = (\ulcorner T \urcorner, [\![ T ]\!](x))\); notice the extra \(\ulcorner T \urcorner\). They demonstrate the existence of a URTM, and then devote a section of the article to the construction of a more efficient RTM. They then conclude with a notion of reversible Turing completeness.