Hacker News Reader

Comment by free_bip | Hacker News Reader

Seems pretty obviously limited - it's not Turing complete because it can't calculate e.g. periodic functions. Are there any practical uses for a language where every operation must be invertible like this?

View on HN

Reversible computing is sort of hypothetical at heart. Besides cryptography and encoders, it’s mostly “if quantum computers eventually fit our model’s for reversible computing, then Landauer’s limit gives us energy-free computing as long as we never extract an answer!”

Technically speaking, Landauer allows you to pay for extracted data on a bit-for-bit basis -- you don't need to pay for the whole computation as long as you're willing to spend approximately the same amount of time undoing it as you did doing it.

Can you be more explicit about the functions it can't compute? I'm pretty sure it can output at least some periodic things (e.g. it's trivial to make it output 01010101 forever).

Edit: just looking at it I'm pretty sure this language is Turing complete, I can't see any reason why it wouldn't be

Remainder after division is one. E.g. 12 mod 4 = 0. There's no way to reverse that operation given only the output and the modulus. (x mod 4 = 0 has infinite solutions)

Bitwise operators are another. A & B, A | B, A << B, A >> B are all in general not invertible given the output and B. (e.g. A | 1 = 1, is A 0 or 1?)

Now I haven't looked at the language in detail, maybe there's a way around this, but it sounds like if truly every single operation is invertible, then there would be no way to calculate these simple functions.

In general, one solution is to just keep the original inputs around as necessary. So instead of x -> x mod 4, take the function x -> (x, x mod 4); the inverse is just (x, y) -> x.

The actual % operator in this language is defined as (x, y) -> (y, x / y, x % y), acting as a divmod. The + and - operators are defined as (x, y) -> (x + y, y) and (x, y) -> (x - y, y). And so on, making sure enough inputs are left on the stack to reconstruct the others.

The proper way to think of reversible computing is that you just write everything down in a single-static-assignment ledger and never erase anything except for the tail end of the ledger. This can be accomplished with a multi-tape machine where writing down a value duplicates the current tape except the changed value. And once you're done with the computation, you can erase one tape at a time, starting with the most recent duplicate. So it can simulate a Turing machine. This implementation isn't as efficient as possible, but it's a good mental model for the absurdity required for reversibility.

Oh yeah, if that's what you're talking about you're just wrong. There are standard ways to deal with that in reversible computing, the most obvious is just to keep enough of the original data around that everything becomes invertible. E.g. instead of 12 mod 4 giving you zero it gives you (0,4,12) or something similar.

In addition to the standard ways of dealing with this given by other commenters (keeping the original input around), perhaps more interesting is to imagine how befreak might compute 12 mod 4 using repeated subtraction.

I'm not clever enough to write the solution, but I imagine a loop using the branching operators (<, >, v, ^). Since each time through the loop pushes a bit onto the control stack, you have a built-in count for the number of times the loop was traversed.

In the example of 12 mod 4, the program would loop through 3 times and break once giving you 0001 (or 1110) on the control stack and something like 12, 8, 4, 0 on the stack. Then when reversing, control bits would be popped off and you'd end up going back 0, 4, 8, 12.

This just means that the language forces you to use more memory to make the computation reversible

Quantum computing suffer from the same problem. There you use the CNOT gate for example, because XOR is not reversible

Some pointers

https://en.wikipedia.org/wiki/Controlled_NOT_gate

https://en.wikipedia.org/wiki/Reversible_computing#Logical_r...

https://physics.stackexchange.com/questions/270266/why-do-qu...

Reply on news.ycombinator.com