We now review the basic logic elements used in computation and explain how conventional computers may be used for any ``reasonable'' computation. A reasonable computation is one that may be written in terms of some (possibly large) Boolean expression, and any Boolean expression may be constructed out of a fixed set of logic gates. Such a set (e.g., AND, OR and NOT) is called universal. In fact we can get by with only two gates, such as AND and NOT or OR and NOT. Alternatively, we may replace some of these primitive gates by others, such as the exclusive-OR (called XOR); then AND and XOR form a universal set. The truth tables for these gates are displayed in Table 1. Any machine which can build up arbitrary combinations of logic gates from a universal set is then a universal computer.
Table 1 Truth table defining the operation of some elementary logic
gates. Each row shows two input values A and B and the
corresponding output values for gates AND, OR and XOR. The output
for the NOT gate is shown only for input B.
Which of the above gates is reversible? Since AND, OR, and XOR are many-to-one operations they are not, as they stand, logically reversible. Before we discuss how these logic gates may be made reversible we consider some non-standard gates that we shall require.