Reversible Computing/3 input universal logic gates

Logic gates are used to build computer chips. Reversible logic gates are of interest because they could in principle generate useful results for less heat generated (Landauer 1961). The nand gate is universal among irreversible logic gates, in the sense that it is possible to simulate any irreversible logic gate with a network of nand gates. The Fredkin and Toffoli gates were the first gates to be proved universal among reversible logic gates. However, this universality is not unusual in the space of 3 input and 3 output reversible gates.

A three input and three output logic gate might have any one of 8⁸ possible truth tables, or about 16 million. However, the requirement for a reversible gate is that for each possible truth table output there is only one input which will produce it, and so reducing the number of possibilities down to 8!, or about 40 thousand.

Many of these tables are equivalent in that the truth table is identical to another table with the three inputs and/or three outputs rearranged. Thus the identity gate:

Is equivalent to this gate:

which merely swaps inputs 0 and 1.

By omitting the input lines and by treating columns as octal numbers and rows as hexadecimal numbers, the second table above may be abbreviated to [02134657=CC:AA:F0] . The first set of digits gives the output for each possible input, and the second set gives the truth table for each of the three outputs. The remainder of this article will use this notation.

Omitting duplicates gives us around 8000 possible gates.

We are interested in universality. Any one output of a three-input logic gate can have 2⁸ possible truth tables for the 8 distinct input values. A logic gate (or set of logic gates) is universal when suitable cascades of gates can be constructed to give us any of these 256 truth tables.

Surprisingly, it turns out that almost all of the 8 thousand or so 3/3 reversible gates are universal in this sense.

There are 269 exceptions. One of them is the "straight through" gate.

7 of them provide access to 8 possible truth tables. These are:
* [45670123=AA:CC:0F] is not universal - 8 truth tables accessible
* [46025713=F0:AA:33] is not universal - 8 truth tables accessible
* [46570213=CC:AA:0F] is not universal - 8 truth tables accessible
* [67234501=AA:0F:33] is not universal - 8 truth tables accessible
* [67452301=AA:33:0F] is not universal - 8 truth tables accessible
* [64752031=CC:55:0F] is not universal - 8 truth tables accessible
* [76543210=55:33:0F] is not universal - 8 truth tables accessible

These ones are those that provide a "not" operator. The 8 truth tables are the 8 ways you can not or not-not each of the 3 inputs.

The remaining exceptions all provide access to 16 truth tables. One example is [75462013=C3:99:0F] . As you can see, this table performs an Exclusive Or (XOR). The 16 truth tables that this gate and presumably all the others provide access to are:
* The 8 results provided by "not" alone
* The 3 ways you can XOR two different inputs
* The 3 ways you can ~XOR two different inputs
* The XOR of all 3 inputs
* The ~XOR of all 3 inputs

In summary: almost all 3 input/3 output reversible logic gates are universal in the sense that a network of them can produce any result. The exceptions are those that only copy their input, those that only perform a "not" on one or more of their inputs, and those that only perform some combination of "exclusive or" and "not" operations. Thus the Fredkin and Toffoli gates are not remarkable

See also

* Reversible computing
* Fredkin gate
* Toffoli Gate
* [http://en.wikipedia.org/wiki/User:Pmurray_bigpond.com/Source_code_for_finding_universal_reversible_gates The source code that produced these results]