On reversible Turing machines and their function universality (Q303695): Difference between revisions
From MaRDI portal
Created a new Item |
Created claim: Wikidata QID (P12): Q62038220, #quickstatements; #temporary_batch_1711439739529 |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Gregory Loren McColm / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6618617 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(r\)-Turing completeness | |||
Property / zbMATH Keywords: \(r\)-Turing completeness / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
RTM injectivity | |||
Property / zbMATH Keywords: RTM injectivity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
RTM-universality | |||
Property / zbMATH Keywords: RTM-universality / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
reversibility | |||
Property / zbMATH Keywords: reversibility / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
reversibilization | |||
Property / zbMATH Keywords: reversibilization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Turing machine inversion | |||
Property / zbMATH Keywords: Turing machine inversion / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
universal reversible Turing machine | |||
Property / zbMATH Keywords: universal reversible Turing machine / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00236-015-0253-y / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2279321119 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q62038220 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 10:00, 26 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On reversible Turing machines and their function universality |
scientific article |
Statements
On reversible Turing machines and their function universality (English)
0 references
22 August 2016
0 references
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.
0 references
\(r\)-Turing completeness
0 references
RTM injectivity
0 references
RTM-universality
0 references
reversibility
0 references
reversibilization
0 references
Turing machine inversion
0 references
universal reversible Turing machine
0 references