dorsal/arxiv
View SchemaReversible Simulation of Irreversible Computation by Pebble Games
| Authors | Ming Li, John Tromp, Paul Vitanyi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9703009 |
| URL | https://arxiv.org/abs/quant-ph/9703009 |
| DOI | 10.1016/S0167-2789(98)00052-9 |
| Journal | Physica D120 (1998) 168-176 |
Abstract
Reversible simulation of irreversible algorithms is analyzed in the stylized form of a `reversible' pebble game. While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the computation. The reacheable reversible simulation instantaneous descriptions (pebble configurations) are characterized completely. As a corollary we obtain the reversible simulation by Bennett and that among all simulations that can be modelled by the pebble game, Bennett's simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps. One can reduce the auxiliary storage overhead incurred by the reversible simulation at the cost of allowing limited erasing leading to an irreversibility-space tradeoff. We show that in this resource-bounded setting the limited erasing needs to be performed at precise instants during the simulation. We show that the reversible simulation can be modified so that it is applicable also when the simulated computation time is unknown.
{
"annotation_id": "1414b9ad-c10a-46bf-a5db-ce407f8761f8",
"date_created": "2026-03-02T18:02:40.448000Z",
"date_modified": "2026-03-02T18:02:40.448000Z",
"file_hash": "9945ab1276cbe353008463a9d74f89eee8ac3ecbb0722a2cf691cc60d971d687",
"private": false,
"record": {
"abstract": "Reversible simulation of irreversible algorithms is analyzed in the stylized\nform of a `reversible\u0027 pebble game. While such simulations incur little\noverhead in additional computation time, they use a large amount of additional\nmemory space during the computation. The reacheable reversible simulation\ninstantaneous descriptions (pebble configurations) are characterized\ncompletely. As a corollary we obtain the reversible simulation by Bennett and\nthat among all simulations that can be modelled by the pebble game, Bennett\u0027s\nsimulation is optimal in that it uses the least auxiliary space for the\ngreatest number of simulated steps. One can reduce the auxiliary storage\noverhead incurred by the reversible simulation at the cost of allowing limited\nerasing leading to an irreversibility-space tradeoff. We show that in this\nresource-bounded setting the limited erasing needs to be performed at precise\ninstants during the simulation. We show that the reversible simulation can be\nmodified so that it is applicable also when the simulated computation time is\nunknown.",
"arxiv_id": "quant-ph/9703009",
"authors": [
"Ming Li",
"John Tromp",
"Paul Vitanyi"
],
"categories": [
"quant-ph",
"cs.CC",
"cs.DS"
],
"doi": "10.1016/S0167-2789(98)00052-9",
"journal_ref": "Physica D120 (1998) 168-176",
"title": "Reversible Simulation of Irreversible Computation by Pebble Games",
"url": "https://arxiv.org/abs/quant-ph/9703009"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "88574813-a0ac-42c4-9afe-50935b4e7883",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}