Closed Systems of Invertible Maps

Abstract

We generalise clones, which are sets of functions $f:A^n\to A$, to sets of mappings $f:A^n\to A^m$. We formalise this and develop language that we can use to speak about it. We then look at bijective mappings, which have connections to reversible computation, which is important for physical (e.g. quantum computation) as well as engineering (e.g. heat dissipation) reasons. We generalise Toffoli's seminal work on reversible computation to arbitrary arity logics. In particular, we show that some restrictions he found for reversible computation on alphabets of order 2 do not apply for odd order alphabets. For $A$ odd, we can create all invertible mappings from the Toffoli 1- and 2-gates, demonstrating that we can realise all reversible mappings from four generators. We discuss various forms of closure, corresponding to various systems of permitted manipulations. These correspond, amongst other things, to discussions about ancilla bits in quantum computation.

Submitted to the Journal for Multiple Valued Logic and Soft Computing

Cited by in corpus (3)

• Reversible k-valued logic circuits are finitely generated for odd k
• Finite generating sets for reversible gate sets under general conservation laws
• Distortion element in the automorphism group of a full shift