Reversible Computation with Stacks and “Reversible Management of Failures”
Matteo Palazzo, Luca Roversi · 2025
Read Reversible Computation with Stacks and “Reversible Management of Failures” by Matteo Palazzo, Luca Roversi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05259.txt.
Description
A program that can run backward as cleanly as forward obeys a strict rule: no step may blur two states into one. Matteo Palazzo and Luca Roversi study that rule in 2025 for programs built on stacks. The cheap way to force it halts the run whenever a past state cannot be read back — a partial fix.
Their language, SCORE, works with plain variables and stacks, and its acts stay total: every run can be undone, with none halted mid-way. Stack acts are where the cheap way usually breaks, since a pop throws facts away. Total undoing matters for the cost theory of such machines. The design shows stacks can join the fully reversible world.
Catalog record
| CREATOR | Matteo Palazzo, Luca Roversi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-05259