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.

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

After reading: “oh my god it’s full of stars!”

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

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...

  commit 212fab9926b2f0f04b0187568e7124b70e8deee5
  Author: Thomas Munro <[email protected]>
  Date:   2018-10-09 12:51:01 +1300
  
      Relax transactional restrictions on ALTER TYPE ... ADD VALUE (redux).

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

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

https://en.m.wikipedia.org/wiki/Linear_logic

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.

But then, the observation principle is as fundamental as Schrodinger's equation and irreversible. It's just not an equation.

  |a| = 2
  a^2 = 4

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

  lim_(n->∞) n^(-n) n! = 0

So n!/n^n ~ sqrt(2 pi n)e^-n.

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.

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

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]