Conditionally reversible computations and weak universality in category theory

DOI10.1007/S10958-014-1955-3MaRDI QIDQ2256643zbMATH OpenOpenAlexFDO

Authors S. N. Baranov, Serguei V. Solov'ev

Publication date 20 February 2015

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10958-014-1955-3

zbMATH Keywords

conditionally reversible computationextensional and intensional equalityweak universality in categories

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Abstract and axiomatic computability and recursion theory (03D75) Foundations, relations to logic and deductive systems (18A15) Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) (18A40)

Review text

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.

Recommendations

• Equality in lambda calculus. Weak universality in category theory and reversible computations
• Towards a categorical representation of reversible event structures
• scientific article; zbMATH DE number 3999258
• Reversible monadic computing
• Join inverse categories and reversible recursion

Cites work

• scientific article; zbMATH DE number 49833 (Why is no real title available?)
• scientific article; zbMATH DE number 1216133 (Why is no real title available?)
• scientific article; zbMATH DE number 591911 (Why is no real title available?)
• Isomorphisms of simple inductive types through extensional rewriting
• Synthesis and optimization of reversible circuits -- a survey

Cited in

(4)

• Identities in modular arithmetic from reversible coherence operations
• Contextual equivalences in configuration structures and reversibility
• Eta-rules in Martin-Löf type theory
• Equality in lambda calculus. Weak universality in category theory and reversible computations

This page was built for publication: Conditionally reversible computations and weak universality in category theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256643)