22 March 2009, York, UK
A Satellite Workshop of ETAPS 2009
Reversible computer hardware: Alexis De Vos, Univerity of Gent
Abstract: Reversible logic circuits are beneficial to both classical and quantum computer design. Present-day logic building-blocks (like OR gates and NAND gates) are logically irreversible and therefore cannot be used for designing reversible computers. Thus reversible computation needs an appropriate design methodology. In contrast to conventional digital logic circuits, reversible logic circuits form a mathematical group. Its subgroups allow systematic and efficient synthesis of an arbitrary reversible circuit. The optimal design is reminiscent of the so-called banyan networks of telecommunication.
As an illustration, experimental prototypes (in c-MOS chip technology) of reversible computing devices are presented. Special care has been taken to avoid as much as possible the appearance of garbage bits. The examples illustrate how, in a near future, reversible computers will outperform conventional computers, in terms of power dissipation and heat generation.
Universality issues in reversible computing systems and cellular automata: Kenichi Morita, Hiroshima University
Abstract: Since reversibility is one of the fundamental microscopic physical laws of Nature, it is important to investigate how universal computer can be implemented efficiently in a system having such a property. This is because the size of future computing devices will become nanoscale ones. So far, various reversible computing systems have been proposed and investigated. In this talk, we give a survey on universality issues of such systems, in particular on reversible logic circuits, reversible Turing machines, and reversible cellular automata. We can see that even very simple reversible systems have universal computing ability. In these reversible systems, computation can be carried out in a very different manner from conventional computing systems, and thus they give new ways and concepts for future computing.
From such simple a beginning: The momentous consequences of microscopic physics' reversibility for communication and computation—and for almost everything else: Tommaso Toffoli, Boston University
Abstract: Darwin concludes The Origin of Species with a splendid one-phrase poem,
From such a simple beginning endless forms most beautiful and most wonderful have been, and are being, evolved.Today, Darwin's "simple beginning" may be taken to mean MACROSCOPIC DISSIPATION—evolution's basic fuel. All the rest is commentary—or perhaps corollary.
What if we apply the above phrase to something that is apparently just the opposite, namely, physics' fundamental assumption of MICROSCOPIC REVERSIBILITY? As we shall see, this constraint turns out to be an extraordinarily productive resource, whose impact is particularly evident in computer and communication sciences. To paraphrase Dobzhansky, no sensible step can be taken today in those disciplines if not in the light of reversibility.
Reversible computation and reversible programming languages : Tetsuo Yokoyama, Nagoya University
Abstract: We will discuss the fundamental properties of reversible computation from a programming language perspective. We show principles for good design of a reversible high-level language and a reversible machine code, in which the reversibility of each layer is guaranteed independently. Many irreversible language constructs and properties can be used in reversible programming languages. For example, we show that structured program theorem holds for reversible programming languages. On the other hand, we show reversible programming languages have their own modularity and programming techniques. The practicality of reversible programming languages is shown by implementation of a reversible fast Fourier transform and reversible physical simulation.