Reversible space equals deterministic space

Authors
Lange, KJ McKenzie, P Tapp, A
Citation
Kj. Lange et al., Reversible space equals deterministic space, J COMPUT SY, 60(2), 2000, pp. 354-367
Citations number
23
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
ISSN journal
00220000 → ACNP
Volume
60
Issue
2
Year of publication
2000
Pages
354 - 367
Database
ISI
SICI code
0022-0000(200004)60:2<354:RSEDS>2.0.ZU;2-G
Abstract
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 t hus answers a question posed by Bennett in 1989 and refuses the conjecture. made by Li and Vitanyi in 1996, that any reversible simulation of an irrev ersible computation must obey Bennett's reversible pebble game rules. (C) 2 000 Academic Press.