29/09/2001: Samson Abramsky (Univ. Oxford)
A structural approach to reversible computation.
Résumé
Reversibility is a basic issue in the physics of computation.
In principle, reversible computations can be performed with perfect
thermodynamic efficiency; moreover, quantum computation is inherently
reversible.
Reversibility has mainly been studied in terms of low-level computational
models. We take a more structural point of view, showing how high-level
functional programs can be translated compositionally into a
simple reversible model of computation.
The approach is based on ideas from Linear Logic and Geometry of
Interaction, but does not require any background in these topics, and in
fact provides a simple and concrete introduction to them.
We also pay some attention to how results can be extracted from such
computations, which raises some interesting issues, and indicate how a
logical delineation of the boundary between reversible and irreversible
computation arises naturally.