ation of the com- puting history, which makes the computation irreversible. For computation, the term "irreversible" means that the computed information output cannot lead one to know the information input to the computation. The concept of computing irreversibility, however, seems to be in contradiction with the laws of physics. Indeed, if one fully knows the state of a system at a given time t, for instance, the distribution of molecules and their velocities inside a closed box, For instance, the addition of two integer numbers a and b, given the fact that the input information (a, b) is then erased, is irreversible: to any output C correspond C + 1 possible input pairs. If a and b are real numbers, the number of input-pair possibilities is infinite. Another example of irreversibility is the opera- tion of functional derivation: given any input function fin = f(x), the output is fout = f'(x). Reversing the algorithm yields f*(x) = Sxo f'(x)dx = f(x) + C where C = - f(x) is an arbitrary constant. The knowl- edge of fout = f'(x), thus, makes it possible to know f* = f(x) + C = fin(x) + C. This may represent useful information, but f* and fin differ from each other by an infinity of possible real constants C, which illustrates the irreversibility of the computation algorithm. Reversible computation Memory Instructions Registers Control unit Figure 15.2 Von Neumann's generic computer architecture. the laws of mechanics make it possible to compute the system at any time prior to t. This is like playing a video of a billiard ball game in reverse. From this perspective, a physicist should suspect that it is possible to effect reversible computations, without any heat dissipation or entropy increase. This brings the issue of the existence of reversible logic. In the next two sections, I shall describe logic gates, which are used in the heart of computer microcircuits, and then show that it is possible to define reversible logic gates and circuits. From computer architecture to logic gates According to the 1945 design o