**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.

Irek Ulidowski, Department of Computer Science, University of Leicester.