Reversible Structured Program Theorem

In 2001, Patrick P. Gelsinger, a senior vice president at Intel corp., predicts that one of the bottlenecks of modern chip design is heat dissipation and that the upper limits of power density will be reached within the next 15 years, provided that the current trends continue [Gel01]. For the end of this decade he predicts a processor power consumption of over 1000 W and a processor power density of over 1000 W/cm 2 (as hot as a rocket nozzle). He concludes that “business as usual ” is not an option for chip design. Reversible computing holds the promise to reduce power consumption by recycling the energy used in the circuit in each computing process [Fra99]. Part of the heat generated by the dissipated energy might be used for other productive purposes. Reversible computing is one of the potential solution to overcome the future limits of power density in microprocessors. The ideas have been around for many years [Lan61,Ben73] and recently found renewed interest. An example is the reversible microprocessor Pendulum [Fra99]. To gain the highest reversibility profit, it is necessary to consider not only low-level hardware issues but also high-level logical reversibility on a software and programming language level. Reversible computation which is a deterministic forward and backward computation of a program is closely related to inverse computation. A reversible program allows a deterministic time-invertible computation where at any time not only the next machine state can be constructed given the current state, but the previous machine state can be constructe