On reversible Turing machines and their function universality
On reversible Turing machines and their function universality
复制标题
DOI：
10.1007/s00236-015-0253-y
复制
发表时间：
2016-08-01
期刊：
影响因子：
0.6
通讯作者：
Gluck, Robert
中科院分区：
文献类型：
--
作者：
Axelsen, Holger Bock;Gluck, Robert
在严格的函数语义下，给出了可逆图灵机的一种处理方法。与许多现有的可逆计算模型不同，我们严格区分了计算函数和计算函数，或者f的其他内射嵌入。在这种语义下，我们重新解释和适应了一些重要的基本可逆计算结果。在单个模型中统一结果表明，正如预期的(和先前声称的)，RTM是健壮的，并且可以精确地计算所有内射可计算函数。因为内射性要求RTM不是严格图灵完全的W.r.t.函数，我们使用了适当的替代普适性定义，并展示了如何从现有的不可逆万能机中推导出普适RTM(URTM)。然后，我们会从头开始兴建市区重建区。这是第一台不依赖于现有通用机器的可逆模拟的URTM。新结构的优点在于，URTM的解释开销被限制为(依赖于程序的)常量因子。另一个新奇之处是，URTM可以充当反向解释器，而不需要任何渐近成本。
We provide a treatment of the reversible Turing machines (RTMs) under a strict function semantics. Unlike many existing reversible computation models, we distinguish strictly between computing the function and computing the function , or other injective embeddings of f. We reinterpret and adapt a number of important foundational reversible computing results under this semantics. Unifying the results in a single model shows that, as expected (and previously claimed), the RTMs are robust and can compute exactly all injective computable functions. Because injectivity entails that the RTMs are not strictly Turing-complete w.r.t. functions, we use an appropriate alternative universality definition, and show how to derive universal RTMs (URTMs) from existing irreversible universal machines. We then proceed to construct a URTM from the ground up. This resulting machine is the first URTM which does not depend on a reversible simulation of an existing universal machine. The new construction has the advantage that the interpretive overhead of the URTM is limited to a (program dependent) constant factor. Another novelty is that the URTM can function as an inverse interpreter at no asymptotic cost.