Programming Reversible Computers Ph.D. Thesis Proposal (Concise Version for Submission) $Revision: 2.8

I propose, for my Ph.D. thesis research, to delve into this question, and study in detail the relationship between the efficiency of a computation, and the amount of irreversible information destruction it performs. This investigation will involve both theoretical and experimental work.

On the theoretical side, I propose to formalize a new measure of computational complexity in terms of the amount of information that a computer erases, and determine where existing algorithms studied by computer scientists fall on this spectrum. I will attempt to develop efficient reversible versions of these algorithms. Some particular algorithms can be made reversible without affecting their asymptotic efficiency; I will describe these algorithms and attempt to characterize how this sort of transformation might be applied more generally. Finally, I will study how the efficiency of algorithms is affected if only partial reversibility is required.

On the experimental side, I propose to develop new abstractions, programming techniques, languages, and compilers that will allow programmers to easily write partially or fully reversible programs that are as space and time efficient as can be provided for, given the best known theoretical results to date. To the degree that time permits, I will write and compile example programs using this system, simulate the programs' execution on a reversible computer architecture, and experimentally measure the programs' efficiency and degree of reversibility, to validate the theoretical predictions.

By this work, I hope to show that a requirement for reversibility is not actually prohibitive for general-purpose computation, or at least, to show that the amount of information erasure in a computation can be greatly reduced (if not eliminated) without severely affecting its efficiency. If successful, this work will provide a crucial foundation for the programming of possible future generations of extremely high density computers, by allowing them to be energy-efficient enough to operate at high speeds without suffering severe cooling problems.

The proposed nominal period of research is one year, from December 1996 to December 1997. Out of this, I propose to spend approximately three months on theoretical work, five months on experimental work, and four months writing and revising the thesis. The period of research may be extended by approximately one semester, if necessary.