Programming Research Group Research Report RR-01-09

Samson Abramsky

May 2001, 15pp.

Abstract

We present a simple model of computation which is directly reversible in a very strong sense - every automaton A in our model has a "dual" automaton A^op, defined quite trivially from A, whose computations are exactly the time-reversals of the computations of A. We then establish a connection to models of functional computation. We will show that our model gives rise to a combinatory algebra, and derive universality as an easy consequence. This method of establishing universality has potential significance for the important issue of how to program reversible computations. Our approach can be seen as providing a simple, compositional (i.e. "syntax-directed") compilation from high-level functional programs into a reversible model of computation.