TIME-SPACE TRADE-OFFS FOR REVERSIBLE COMPUTATION
TIME-SPACE TRADE-OFFS FOR REVERSIBLE COMPUTATION
复制标题
DOI：
10.1137/0218053
复制
发表时间：
1989-08-01
影响因子：
1.6
通讯作者：
BENNETT, CH
中科院分区：
文献类型：
--
作者：
BENNETT, CH
可逆图灵机是指其转移函数为，使得任何瞬时描述(ID)都有一个以上的前身。本文利用鹅卵石理论证明，对于任何一个使用时间T和空间S的普通多带图灵机，都可以用线性时空中的可逆时间和空间来模拟图灵机。前面的结果特别表明可逆机可以在二次空间中模拟普通的可逆机。这些结果涉及保存其输入的可逆机器，从而确保初始ID和最终ID之间的全局关系，即使正在计算的函数是多对一的。相反，擦除输入的可逆机当然只能计算部分递归函数，并且确实提供了此类函数的Godel编号。在这样的机器上计算函数的时间/空间成本在小多项式内等于在普通图灵机上计算函数及其逆的成本。
A reversible Turing machine is one whose transition function is, so that no instantaneous description (ID) has more than one predecessor. Using a pebbling argument, this paper shows that, for any, ordinary multitape Turing machines using timeTand spaceScan be simulated by reversible ones using timeand spaceor in linear time and space. The former result implies in particular that reversible machines can simulate ordinary ones in quadratic space. These results refer to reversible machines that save their input, thereby insuring a globalrelation between initial and final IDs, even when the function being computed is many-to-one. Reversible machines that instead erase their input can of course compute onlypartial recursive functions and indeed provide a Godel numbering of such functions. The time/space cost of computing afunction on such a machine is equal within a small polynomial to the cost of computing the function and its inverse on an ordinary Turing machine.