Hostname: page-component-6bf8c574d5-qdpjg Total loading time: 0 Render date: 2025-02-21T00:01:20.455Z Has data issue: false hasContentIssue false

Reversible combinatory logic

Published online by Cambridge University Press:  24 July 2006

ALESSANDRA DI PIERRO
Affiliation:
Dipartimento di Informatica, Universitá di Pisa Largo Bruno Pontecorvo, 3, 56127 Pisa, Italy Email: dipierro@di.unipi.it
CHRIS HANKIN
Affiliation:
Department of Computing, Imperial College London 180 Queen's Gate, London SW7 2AZ, United Kingdom Email: clh@doc.ic.ac.uk, herbert@doc.ic.ac.uk
HERBERT WIKLICKY
Affiliation:
Department of Computing, Imperial College London 180 Queen's Gate, London SW7 2AZ, United Kingdom Email: clh@doc.ic.ac.uk, herbert@doc.ic.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The $\lambda$-calculus is destructive: its main computational mechanism, beta reduction, destroys the redex, which makes replaying the computational steps impossible. Combinatory logic is a variant of the $\lambda$-calculus that maintains irreversibility. Recently, reversible computational models have been studied mainly in the context of quantum computation, as (without measurements) quantum physics is inherently reversible. However, reversibility also fundamentally changes the semantical framework in which classical computation has to be investigated. We describe an implementation of classical combinatory logic in a reversible calculus for which we present an algebraic model based on a generalisation of the notion of a group.

Type
Paper
Copyright
2006 Cambridge University Press

Footnotes

The authors are partly funded by the EPSRC project S77066A ‘Quantitative Analysis of Computational Resources’.