Time-symmetric Turing machines for computable involutions
Time-symmetric Turing machines for computable involutions
复制标题
用于可计算对合的时间对称图灵机
DOI：
10.1016/j.scico.2021.102748
复制
发表时间：
2022
影响因子：
1.3
通讯作者：
Nakano Keisuke
中科院分区：
文献类型：
--
作者：
清野航;廣田佳久;Nakano Keisuke
可逆图灵机是一种前向和后向确定性图灵机，它已经成为可逆计算的一种表达模型。很明显，每个可逆图灵机都在函数语义下计算单射函数，其中运行的初始和最终配置对应于函数的输入和输出。Axelsen和Glück表明了相反的方向，即每个内射可计算函数都可以通过可逆图灵机来计算。本文在对合而不是内射函数上给出了类似的结果。对合，也称为自反函数，是一个函数f是它自己的逆，即f（f（x））= x保持每当f（x）被定义。本文提出了一个计算模型的对合作为图灵机的一个变种，称为时间对称图灵机。的计算模型被证明是表达的意义上，不仅是一个时间对称的图灵机总是计算的对合，但也可以计算的时间对称的图灵机的每一个可计算的对合。由于任何对合都是单射的（因此是可逆的），所以任何时间对称的图灵机都是可逆的图灵机。此外，在Axelsen和Glück为可逆图灵机引入的普适性的适当重新定义下，证明了普适时间对称图灵机的存在。
A reversible Turing machine is a forward and backward deterministic Turing machine, which has been an expressive model of reversible computation. It is obvious that every reversible Turing machine computes an injective function under a function semantics in which the initial and the final configuration of a run corresponds to an input and an output of the function. Axelsen and Glück showed the opposite direction that every injective computable function can be computed by a reversible Turing machine. This paper provides a similar result on involutions instead of injective functions. An involution, also called a self-inverse function, is a function f that is its own inverse, ie, f (f (x))= x holds whenever f (x) is defined. The paper presents a computational model of involution as a variant of Turing machines, called a time-symmetric Turing machine. The computational model is shown to be expressive in the sense that not only does a time-symmetric Turing machine always compute an involution but also every computable involution can be computed by a time-symmetric Turing machine. As any involution is injective (hence reversible), any time-symmetric Turing machine is a reversible Turing machine. Furthermore, the existence of a universal time-symmetric Turing machine is shown under an appropriate redefinition of universality introduced by Axelsen and Glück for reversible Turing machines.
登录
查看更多内容
一句话证明每个素数 p Ξ1(mod 4) 是两个平方和
影响因子：
0.5
作者：
D. Zagier
通讯作者：
D. Zagier
程序逆变器
DOI：
--
发表时间：
2004
期刊：
16th Nordic Workshop on Programming Theory. Proceedings
影响因子：
--
作者：
真田貴志;池田和美;保倉明子;中井 泉;池田 和美;真道 洋子(編);久保田 静香;久保田 静香;久保田 静香;Masahiko Kawabe;河邊 昌彦;Masahiko Kawabe
通讯作者：
Masahiko Kawabe
影响因子：
0.6
作者：
Axelsen, Holger Bock;Gluck, Robert
通讯作者：
Gluck, Robert
影响因子：
1.1
作者：
Gajardo, Anahi;Kari, Jarkko;Moreira, Andres
通讯作者：
Moreira, Andres