Closed Systems of Invertible Maps
Tim Boykett
We generalise clones, which are sets of functions f : An → A, to sets of maps f : An → Am. We formalise this and develop language that we can use to speak about such maps. In particular we look at bijective mappings, which model the logical gates of reversible computation. Reversible computation 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 multiple valued logics. In particular, we show that some restrictions Toffoli 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. This leads, amongst other things, to discussions about ancilla bits in quantum computation.
Keywords: Toffoli gate, reversible computation, clones, multiple-valued logic, general algebra, mappings, iterative algebras