4 ms·

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

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

free_bip 2y ago
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.
- LegionMammal978 2y ago
  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.
- klyrs 2y ago
  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.
- eigenket 2y ago
  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.
- plusplusungood 2y ago
  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.
- nextaccountic 2y ago
  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/Controlled_NOT_gate https://en.wikipedia.org/wiki/Reversible_computing#Logical_reversibility https://en.wikipedia.org/wiki/Reversible_computing#Logical_r... https://physics.stackexchange.com/questions/270266/why-do-quantum-gates-have-to-be-reversible https://physics.stackexchange.com/questions/270266/why-do-qu...

free_bip 2y ago

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.

LegionMammal978 2y ago
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.
klyrs 2y ago
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.
eigenket 2y ago
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.
plusplusungood 2y ago
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.
nextaccountic 2y ago
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/Controlled_NOT_gate https://en.wikipedia.org/wiki/Reversible_computing#Logical_reversibility https://en.wikipedia.org/wiki/Reversible_computing#Logical_r... https://physics.stackexchange.com/questions/270266/why-do-quantum-gates-have-to-be-reversible https://physics.stackexchange.com/questions/270266/why-do-qu...