May 2001, 15pp.
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 Aop, 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.