Conditionally reversible computations and weak universality in category theory (Q2256643)

Reversible computations attract attention of many researchers; however, such computations without conditions occur rarely. The conditions may be concrete or more abstract, in both cases, the study of reversibility is commonly associated with concrete models of computations, fixed in advance (logic gates and circuits, quantum gates and circuits, various versions of real arithmetic, etc.). In this paper the authors attempt to study very general abstract conditions of reversibility, unrelated to a concrete domain (such as real arithmetic) and a concrete model of computation. In fact, their starting point was the observation that in category theory the difference between the so-called universal constructions and weakly universal constructions corresponds roughly to the difference between unconditional and conditional reversibility. It turned out that already at the level of basic examples there exists a relationship between this observation and the problem of canonical elements of datatypes. This problem is well known in logic and theoretical computer science. Due to the difference between canonical and noncanonical elements, many constructions considered as universal in category theory (for example product) are only weakly universal in computer science models. Thus, conditional reversibility may play an important role at the very basic level, when the representation of data is considered.