5 ms·

> The important thing is that all evolution equations that we know of are time-reversible. I've heard this before, but it's so surprising to me, when one of th

• myaccount80 7y ago
  It is not reversible because you’re ereasing information. If you want to have a reversible addition you are not allowed to destroy the information. The same happens if you apply the standard AND operator to two bits because the output is only one bit, therefore it is impossible to figure out the two input bits. To have a reversible AND operator you can define it like this: f(x1, x2, b) = (x1, x2, b XOR (x1 AND x2)). E.g: f(1,1,0) = (1,1,1). From this output you can get back to the input. This way you can implement a NOT gate as well, and all others gates. At the end you can implement addition using bits and your summation becomes reversible :) You can see that with this definition we are not ereasing any information, hence it becomes reversible.
  • codernyc16 7y ago
    You’d have to do that for all results, not just one. This is basically what an event sourced system does: you store all the events and fold your state, so you can “play back” to any point in time. You could theoretically reverse from the end, but I haven’t seen it done.
    • Zenst 7y ago
      A transactional database would tick that box, events are stored and can rollback to a point in time.
      • acoma 7y ago
        Not quite. Dropping a column or updating a row is typically irreversible.
        • Zenst 7y ago
          That does depend upon the database, but can be done in some without resorting to a backup.
        • continuational 7y ago
          In PostgreSQL, schema changes are transactional.
          • anarazel 7y ago
            > In PostgreSQL, schema changes are transactional. With a few exceptions (that refuse to run in an explicit transaction): E.g. {CREATE, DROP} DATABASE, {CREATE, DROP} TABLESPACE, {CREATE INDEX, DROP INDEX, REINDEX} CONCURRENTLY, REINDEX {SCHEMA, SYSTEM, DATABASE}.
            • zcrackerz 7y ago
              Also, try adding a value to an enum via ALTER TYPE ... ADD VALUE
              • anarazel 7y ago
                Not anymore ;). Well, at least in the upcoming PG 12. https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=212fab9926b2f0f04b0187568e7124b70e8deee5 https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit... commit 212fab9926b2f0f04b0187568e7124b70e8deee5 Author: Thomas Munro <tmunro@postgresql.org> Date: 2018-10-09 12:51:01 +1300 Relax transactional restrictions on ALTER TYPE ... ADD VALUE (redux). There's still some restrictions: > This patch removes that restriction, and instead insists that an uncommitted enum value can't be referenced unless it belongs to an enum type created in the same transaction as the value.
    • setr 7y ago
      Urbit ;-)
  • fizx 7y ago
    Quantum computing is reversible in this way. Rabbit hole starts here: https://en.wikipedia.org/wiki/Ancilla_bit https://en.wikipedia.org/wiki/Ancilla_bit
    • gigatexal 7y ago
      Famous last words... After reading: “oh my god it’s full of stars!”
  • LifeLiverTransp 7y ago
    So basically a deterministic simulation?
• OscarCunningham 7y ago
  The difference between them is that physical evolution takes one state to another state, whereas addition takes two numbers to another number.
  • hyperpallium 7y ago
    |a| = 2 a^2 = 4
    • hyperpallium 7y ago
      Most functions are not invertible. In modulo arithmetic (numbers wrap around like days of the week, months, hours in a day, or the units column, e.g. mod 10 has numbers 0 to 9, and 9+1=0) we can count them. There are n^n possible functions (each of the n inputs could map to any n values), but only n! invertible functions (the first input can be to any of n, the second can be to any but the first's, etc (n)(n-1)(n-2)...(1)). n!/n^n < 1/2 for all n>2 Does this converge to a fraction as n->infinity (i.e. for the naturals)? As a recurrence relation, we have: n!/n^n = (n-1)!/(n-1)^(n-1) x n(n-1)^(n-1)/n^n We could change variables to rewrite the factor as (n+1)n^n/(n+1)^(n+1) = n^n/(n+1)^n Since n+1 converges to n, I think this converges to 1. Meaning that the whole thing converges to something - but working out what it converges to is beyond my abiility. EDIT Wolfram says the limit is actually 0 https://www.wolframalpha.com/input/?i=n%21%2Fn%5En https://www.wolframalpha.com/input/?i=n%21%2Fn%5En lim_(n->∞) n^(-n) n! = 0 Reversibility is very rare indeed! At least, with the prior pr density implied from this comception of functions.
      • OscarCunningham 7y ago
        Stirling's approximation says that n! ~ sqrt(2 pi n) (n/e)^n. So n!/n^n ~ sqrt(2 pi n)e^-n.
        • hyperpallium 7y ago
          Cool! So the 1/e^n factor will bring it to 0, as n goes to infinity, I think?
• kmm 7y ago
  Your state changes from two numbers to one number, such a transition is of course not going to be bijective unless carefully designed. In physics most states stay the same "shape", making invertibility easier to achieve.
• mannykannot 7y ago
  Ha! I had not looked at it that way before. Insofar as addition is an abstract representation of merging two collections, we are abstracting away the information that links each element of the resulting collection to the one it came from.
  • aserafini 7y ago
    Isn’t this exactly the same for subtraction, multiplication and division?
    • mannykannot 7y ago
      Considering integer operators specifically: in subtraction, you partition a collection and then discard one part. Multiplication is more abstract, as one of the operands denotes the number of applications of an operator (addition), and in division, the result is a count of the number of applications of a subtraction. I'm not sure if that can be called the same as addition in this regard, but they all lead back to that case.
• dls2016 7y ago
  That quote is not exactly correct, there are plenty of evolution equations which are not time-reversible beginning with the linear heat equation. If you look at the solution given by convolution (usually taught in first PDE course) you see that this equation has infinite speed of propagation. Any parabolic/dissipative equation is not time-reversible (which is analogous to addition not being reversible... dissipation involves an averaging process). Elsewhere the author says "all fundamental evolution equations in physics are time-reversible." By fundamental I'm assuming she means: Maxwell's equations, Einstein's field equations and the Schrodinger equation.
  • marcosdumay 7y ago
    I don't think they mean Maxwell's ones, since they can be derived from the Schrodinger equation with a well chosen Hamiltonian. But then, the observation principle is as fundamental as Schrodinger's equation and irreversible. It's just not an equation.
• crdrost 7y ago
  Addition is reversible, in the physics sense. So for example one typical quantum gate is called for physicists CNOT, or you would call it in computing a generalization of the XOR gate. We physicists would not think “Oh XOR is irreversible because A ⊕ B = B ⊕ A even when A ≠ B, so the same output can come from two different outputs.” That is just not what reversibility means to us. Contrast this with boolean AND, which we would say is irreversible. What’s the difference? It's that we think of all of our operations as being automorphisms, they map a system back to itself. So when we are looking at CNOT/XOR, we are thinking about a system which looks like this: (t increasing)--> A ---.----- \ \ B ------⊕-- and if you have the output "1, 0" from this system you can infer that the input was "1, 1". In that automorphic sense XOR is reversible, even though given the output on wire B alone you cannot decide what A or B was. Contrast with boolean AND, where if I give you the output "0, 0" you cannot genuinely determine whether that came from "0, 1" or "0, 0". It could have come from either place. So the automorphism (x, y) ⇒ (x, x + y) in fact is reversible in this sense; there is an automorphism which undoes it. The weirdness that you are identifying comes from the fact that you were actually considering the automorphism (x, y) ⇒ (0, x + y), which is a composition of the addition gate above with an ERASE gate, (x) ⇒ (0). Ignore the erasure and you get a reversible process again. You might know that AND, OR, and NOT are universal: you can write any circuit from N bits to 1 bit by enumerating all of the inputs which could set the bit to 1, using AND and NOT to build “masks” for those inputs, and then using a final big OR-gate to see if any of the masks was triggered. By de Morgan's laws, you can build an OR gate out of NOT and AND; and then it is not too hard to see that you can build both NOT and AND from NAND: so we say that “NAND is a universal boolean gate.” To get a universal reversible system you just need to go to three bits. Two working options are the Toffoli gate “doubly controlled NOT” and the Fredkin gate “controlled swap,” Toffoli = ([x, y, z]) => [x, y, (x && y)? z : !z] Fredkin = ([x, y, z]) => [x, x? z : y, x? y : z] The universality of Toffoli is very easy to see from the universality of NAND: because Toffoli(x, y, 0) is actually just (x, y, x NAND y). However the fact that you start with an “isolated” bit and then it becomes “involved” in the computation, this is where you eventually start to need to erase bits if you do not have unlimited amounts of memory. [Fredkin is a little more difficult to reason about but for example Fredkin(x, 0, y) = (x, x AND y, (NOT x) AND y) and so you can then build both an AND gate directly from this construction and a NOT gate with y=1.]
• Strilanc 7y ago
  Actually addition is reversible, as long as you do it inline. The inverse of `a += b` is `a -= b`. An example of an action that's not reversible is masking: `a &= b`. But if you dig deep enough into the physics, you find that these kinds of irreversible actions are actually always implemented in a way analogous to the following: // a &= b acquire zero'd register z from environment z ^= a & b z ^= a a ^= z z ^= a discard z into environment Which can be reversed if you're able to get the discarded `z` register back.
  • FakeComments 7y ago
    You’re just hiding the loss: The loss in your operation occurs when you zero out z, and there’s no way to implement it without that loss. If it’s reversible, how do you zero out z, from the environment? The energy cost of a computer fundamentally comes from having to use energy and discard information (heat) in clearing z.
  • H8crilA 7y ago
    See also the Linear logic, a logic in which discarding information is disallowed: https://en.m.wikipedia.org/wiki/Linear_logic https://en.m.wikipedia.org/wiki/Linear_logic
  • SamReidHughes 7y ago
    The function (a,b) -> a+b is not reversible. The function a -> a+b is reversible, and so is (a,b) -> (a+b, b).
• improv32 7y ago
  A closer mathematical operation would be unitary matrix multiplication