Time/Space Trade-Offs for Reversible Computation

Charles H. Bennett · 1989 · SIAM J. Comput. 18(4)

| 编号 QRC002 | 主题 可逆计算与编译 | 链接 DOI 10.1137/0218053 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

A reversible Turing machine is one whose transition function is $1:1$, so that no instantaneous description (ID) has more than one predecessor. Using a pebbling argument, this paper shows that, for any \varepsilon > 0, ordinary multitape Turing machines using time T and space S can be simulated by reversible ones using time $O(T^{1+\epsilon })$ and space $O(S\log T)$ or in linear time and space $O(S{T}^{\epsilon })$. 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 global $1:1$ relation 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 only $1:1$ partial recursive functions and indeed provide a Godel numbering of such functions. The time/space cost of computing a $1:1$ function 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.

本站词条在引用该文献时，会以 wikilink（sources/QRC002）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。