Reversible computation

Second, observe that the methodology need not be constrained to CA systems alone. With a suitable coarse-graining, the same methodology can easily be extended to provide the spectra of continuous dynamical systems, such as onedimensional mappings of the unit interval to itself. 

Any computation, whether performed by a slide rule, computer workstation or brain, is inherently a physical process, and as such is subject to whatever laws and limitations apply to physical systems in general. It is a natural question to ask, then, whether there exists a fundamental thermodynamic limit to computation i.e. 

Von Neumann s and Brilloun s assertions are both certainly very plausible ones, in view of the fact that each mechanical degree of freedom used to store one bit of information (such as a capacitor, for example) involves at least an amount of kT of thermal noise which must then apparently be overcome to reliably read or manipulate the given bit of information [benn82]. We have inserted the word apparently in quotes, however, because this supposition is now known to be false  

---

Chapter 6 is a short primer on CA and language theory, and provides a basic discussion of formal language theory, the relationship between CA and formal language theory, power spectra of regular languages and reversible computation. 

Consider a logic gate with 3-iiiput and 3-output lines. Edward Fredkin, motivated by a deep conviction in a fundamental connection between a discrete, finite physics and reversible computation [wrightSS], discovered a simple universal 3-input/ 3-output logic function that now bears his name [fredkin82]. 

Toffoli [toff77] managed to prove that an arbitrary d-dimensional CA can be embedded within a (d-fl)-dimensional reversible CA. An immediate corollary of this theorem, is that, given that there exists an irreversible d-dimensional computation-universal CA - of which, by that time, literally scores had been found - there exists a reversible computation-universal CA. 

An example of a 2-state partitioning CA rule mapping (2 x 2) blocks to (2 x 2) blocks is shown in figure 8.2. The rule is rotationally symmetric, so that only one instance of the mapping for a block with a given number of rr = 1 sites need be given to completely define the rule. The rule is trivially reversible since each initial state is mapped to a unique final state. Observe also that the number of I s (shown as solid circles in the figure) and O s (shown as clear squares) is conserved, but that this simple conservation law is not a consequence of reversibility. Indeed, we could have just as easily defined a rule that conserved the number of I s and O s as this one but which was not reversible. (We mention here also that, despite its simple appearance, this rule happens to define a universal CA. We will have a chance to discuss reversible computation later on in this section.)... 

A discussion of reversible computation, as well as some speculations concerning the fundamental limitations of computation, have already been given in section G.4 we will not repeat that discussion here. In the remaining sections of this chapter we instead wish to focus our attention on somewhat more speculative connections between physics and computation and in what way the universe itself might be thought of as a computer. 

Other early designs of classical reversible computers included Landauer s Bag and Pipes Model [land82a] (in which pipes are used as classical mechanical conduits of information carried by balls). Brownian motion reversible computers ([benn88], [keyesTO]) and Likharev s model based on the Josephson junction [lik82]. One crucial drawback to these models (aside from their impracticality), however, is that they are all decidedly macroscopic. If we are to probe the microscopic limits of computation, we must inevitably deal with quantum phenomena and look for a quantum mechanical reversible computer. 

Iand85] Landauer, R. and M.Buttiker, Drift and diffusion in reversible computation , Physica Scripta T9 (1985) 155-164. 

Bennett CH Notes on Landauer s principle, reversible computation, and Maxwell s Demon. Studies in History and Philosophy of Modern Physics 2003, 34(3) 501-510. 

Cuykendall, R., and Anderson, D. R., Reversible computing all-optical implementation of interaction and Priese gates. Opt. Commun., 62, 232 (1987). 

Processing Voter fault Random voter test Algorithm Assertions Plausibility check Reverse computation diversity... 

Reversible computation has a very important consequence until 1961 scientists believed that any computational action would result in an energy cost. But in 1961 Rolth Landauer showed [17] that what do cost energy is erasure. In other words, if no bit is lost during the computation, it can be made at energy-free cost This discovery lead to the solution of a century-old problem in thermodynamics the Maxwell demon problem. 

There is another gate which can be used to prove reversible computation. It is the Fredkin gate it performs a controlled swap operation between two bits [6]. 

How to address specific design issues, even the work on reversible computing... 

When the First Edition was written, much of the information on design computations had not theretofore been published, and such methods were new to much of the industry. This situation has also been reversed. Computation methods now flow from the industry at a rate that cannot be accommodated in new editions. 

The third reason simply is that smaller and smaller computers lead to a minimization of the length of communications pathways. In case of ideal, reversible computation this point is crucial, since theoretical speed limits are given solely by the lengths of the communication pathways and the speed of light. 

---