[Roxxik]

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 mutating auxiliary space and then restoring it.

What I haven't yet figured out is how to do reversible instructions on auxiliary space. You can mutate a value depending on your input, but how do you use that value, since you can't assume anything about the contents of the auxiliary space and just overwriting with a constant (e.g. 0) is not reversible.

Maybe there is some xor like trick, where you can store two values in the same space and you can restore them, as long as you know one of the values.

Edit: After delving into the paper linked in another comment, which is rather mathy (or computer sciency in the original meaning of the phrase), I'd like to have a simple example of a program that can not run in it's amount of free space and actually needs to utilize the auxiliary space.

[falsifian]

If you want an example, I wrote a blog post about this a few years ago: https://www.falsifian.org/blog/2021/06/04/catalytic/

Alternatively, Ian Mertz's survey might be a bit more accessible than the original catalytic paper: https://iuuk.mff.cuni.cz/~iwmertz/papers/m23.reusing_space.p...

[westurner]

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 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.

[samstave]

Can you feed gravitationaly waves forward to a receptor that only carries that gravitational waves bit, but can be recalled?

[cubefox]

> 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.

If the results were stored outside the auxiliary "full" memory, there wouldn't be any need to reverse storing the results. So you probably meant the opposite: store the result inside of the auxiliary "full" memory.

[NooneAtAll3]

for me, perfect introduction to catalytic computing was this lecture: https://www.youtube.com/watch?v=_KEORzRpxY8

[myself248]

Just run it twice and XOR the relevant bits each time, so the second pass flips them back?

[throwaway81523]

Is this something like pointer reversing garbage collection or the XOR trick to interchange two integer values?