Reversibility for Nanoscale Systems

There are a number of emerging nanoscale devices that promise to operate at amazing speeds with very low power and at very high densities. However, many of these promises ignore critical factors in the design of a computer that would render them little to no better than today's transistors. This dissertation explores reversibility as an avenue to allow the high speed, high density, and low power potential of nanoscale devices to be harnessed. This work begins by providing the foundation for a theory of reversible computation by presenting a formal investigation of reversible finite automata and reversible regular languages that surpasses previous discussions of reversible finite automata that were insufficient to allow fundamental and important discussions to be held about the differences between reversible finite automata and reversible regular languages and their traditional counterparts. The discussion is also extended to reversible regular expressions. The work continues by discussing a new symmetry discovered in reversible gates that facilitates the identification of complete, reversible gate sets for emerging nanodevices. Next, a simple reversible architecture, Palindrome, is presented that demonstrates the impact of reversibility on the instruction set architecture, microarchitecture, and assembly level programming. Finally, a path is shown for designing physically reversible architectures using a particular nanoscale device, quantum-dot cellular automata.