Reversible space equals deterministic space

Reversible space equals deterministic space
复制标题

可逆空间等于确定性空间

DOI：
10.1109/ccc.1997.612299
复制
发表时间：
1997
期刊：
Proceedings of Computational Complexity. Twelfth Annual IEEE Conference
影响因子：
--
通讯作者：
Alain Tapp
Alain Tapp
中科院分区：
--
文献类型：
--
作者：
Klaus;P. McKenzie;Alain Tapp

文献摘要

被引文献

相似文献

本文描述了用一个在S（n）空间中运行的可逆图灵机来模拟一个S（n）空间有界的确定图灵机。这就回答了C.班尼特（1989）的猜想，并反驳了M. Li和P.Vitanyi（1996）指出，任何对不可逆计算的可逆模拟都必须遵守班尼特的可逆卵石博弈规则。
This paper describes the simulation of an S(n) space-bounded deterministic Turing machine by a reversible Turing machine operating in space S(n). It thus answers a question posed by C. Bennett (1989) and refutes the conjecture, made by M. Li and P. Vitanyi (1996), that any reversible simulation of an irreversible computation must obey Bennett's reversible pebble game rules.