An investigation of some theoretical aspects of reversible computing
Date
2014-11-05
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The categorical semantics of reversible computing must be a category which combines the concepts of partiality and the ability to reverse any map in the category. Inverse categories, restriction categories in which each map is a partial isomorphism, provide exactly this structure. This thesis explores inverse categories and relates them to both quantum computing and standard non-reversible computing. The former is achieved by showing that commutative Frobenius algebras form an inverse category. The latter is by establishing the equivalence of the category of discrete inverse categories to the category of discrete Cartesian restriction categories — this is the main result of this thesis. This allows one to transfer the formulation of computability given by Turing categories onto discrete inverse categories.
Description
Keywords
Computer Science
Citation
Giles, B. (2014). An investigation of some theoretical aspects of reversible computing (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/24917