11–20 of 22 posts
This is very similar to an old approach to LISP garbage collection. All of memory is a tree of small cells. You need to walk the the tree and don't have space for a stack of the links that got you to where you are. So you store the backlinks in the forward links by XORing the forward link with the backlink. As the tree-walker backs down the tree, the links are XORed again, restoring the forward link.
So the trick is to do the computation forwards, but take care to only use reversible operations, store the result outside of the auxiliary "full" memory and then run the computation backwards, reversing all instructions and thus undoing their effect on the auxiliary space. Which is called catalytic, because it wouldn't be able to do the computation in the amount of clean space it has, but can do it by temporarily mut…
From "Reversible computing escapes the lab" (2025) https://news.ycombinator.com/item?id=42660606#42705562 :
> FWIU from "Quantum knowledge cools computers", if the deleted data is still known, deleting bits can effectively thermally cool, bypassing the Landauer limit of electronic computers? Is that reversible or reversibly-knotted or?
> "The thermodynamic meaning of negative entropy" (2011) https://www.nature.com/articles/nature10123
Though also Landauer's limit presumably only applies to electrons; not photons or phonons or gravitational waves.
This is very similar to an old approach to LISP garbage collection. All of memory is a tree of small cells. You need to walk the the tree and don't have space for a stack of the links that got you to where you are. So you store the backlinks in the forward links by XORing the forward link with the backlink. As the tree-walker backs down the tree, the links are XORed again, restoring the forward link.
That's brilliant
So the trick is to do the computation forwards, but take care to only use reversible operations, store the result outside of the auxiliary "full" memory and then run the computation backwards, reversing all instructions and thus undoing their effect on the auxiliary space. Which is called catalytic, because it wouldn't be able to do the computation in the amount of clean space it has, but can do it by temporarily mut…
So the trick is to do the computation forwards, but take care to only use reversible operations, store the result outside of the auxiliary "full" memory and then run the computation backwards, reversing all instructions and thus undoing their effect on the auxiliary space. Which is called catalytic, because it wouldn't be able to do the computation in the amount of clean space it has, but can do it by temporarily mut…
That sounds similar to this in QC: From "Reversible computing escapes the lab" (2025) https://news.ycombinator.com/item?id=42660606#42705562 : > FWIU from "Quantum knowledge cools computers", if the deleted data is still known, deleting bits can effectively thermally cool, bypassing the Landauer limit of electronic computers? Is that reversible or reversibly-knotted or? > "The thermodynamic meaning of negative entrop…
If I give you a hard drive full of photos, you could compress them, use the excess hard drive space for your algorithm, then uncompress the photos and give a full hard drive back to me. Is that’s what’s going on here? Basically it’s exploiting unused channel capacity of the memory if the Shannon entropy isn’t maxed out?
They are explicitly not assuming anything about the content of the auxiliary space (full hard drive). So the data might be incompressible and thus compressing it and restoring it afterwards would not work. Edit: From the paper: > One natural approach is to compress the data on the hard disk as much as possible, use the freed-up space for your computation and finally uncompress the data, restoring it to its original s…
Earlier quoted context omitted.
They are explicitly not assuming anything about the content of the auxiliary space (full hard drive). So the data might be incompressible and thus compressing it and restoring it afterwards would not work. Edit: From the paper: > One natural approach is to compress the data on the hard disk as much as possible, use the freed-up space for your computation and finally uncompress the data, restoring it to its original s…
Why wouldn't decompressing work? The whole point is that the hard drive is restored to its (arbitrary) original state upon completion.
Earlier quoted context omitted.
That's brilliant
Wikipedia has a note on XOR linked lists.[1] That's a more general form of this concept. This technique is decades older than the references there indicate. I'm trying to find a reference to this in early garbage collection papers, and not, so far, succeeding. It's the sort of thing that mattered around when LISP was being invented in the 1950s and 1960s, and memory cost millions of dollars per megabyte. [1] https://…
Earlier quoted context omitted.
Why wouldn't decompressing work? The whole point is that the hard drive is restored to its (arbitrary) original state upon completion.
Some data is just incompressible, like random numbers, encrypted data or already compressed data.
Put arbitrary data in, get the same arbitrary data out.