Conservative logic circuits

We have thus far discussed the processing of only individual logic gates. In order to perform useful computations, however, we need to construct entire circuits. Luckily, building circuits does not involve any great jump in complexity, as we need only two additional abstract primitives to begin talking of real computation. 

The last element necessary for the construction of a universal computer is a simple time delay, i.e. a circuit primitive whose output at time t-fl equals the input at time t and which allows us to feed outputs back into gates as inputs. 

Recalling Bennett s and Fredkin s trick to erase the garbage bits, the way in which the reversible logic circuit in figure 6.9 can be made to act as a real reversible serial-adder circuit is to first operate the circuit as shown, store the desired output, and then operate it backwards using the output and all intermediary garbage bits as new input. After all operations are completed in the reverse direction, we will be left with our desired answer stored on the side and with the serial-adder circuit back in its original state ready for another run. 

In summary then, any computation that can be carried out by a conventional circuit can be reproduced by a conservative logic circuit (assuming only that some 

---

Fig. 6.9 A conservative-logic realization of a conventional serisJ adder circuit it is built entirely of Fredkin gates. Places along the wires marked with a dot represent unit time delays at those locations. Illustration patterns after [marg88] and [fredkin82]...

The previous theorem can be generalized to several other paraconsistent logics, that is, to those where a conservatively translation function from CPL can be defined taking into account that such translation function must be effectively calculated. In the other direction, the existence of uniform families of boolean circuits to every uniform family of L-circuits (for any logic L provided with PRC) is guaranteed by the classical computability of roots for polynomials over finite fields. Then, the L-circuits model does not invalidate Church-Turing s thesis. 

---