Algebraic models of computation have been developed in order to express many varied aspects of theories of computation. For instance Clone Theory emerged from the work of Post, Malcev and others, trying to understand the collections of computations that could be represented as gates, mappings from A^n to A for some signal or state set A. Clone theory has a well explored and powerful dual theory of relations.
This talk looks at the question of computation as collections of gates from A^n to A^n that are closed under natural operations. While the theory is more general, we are particularly interested in reversible gates, that is, permutations of A^n. Such collections have been studied for instance by Peter Cameron, Ben Fairbairn and Max Gadouleau as computation without memory.
Two ways in which computer scientists interested in reversible computation add memory is to talk about borrowed and ancilla bits, extra input-outputs that must be treated in certain ways. Ancilla bits are supplied and must be returned (output) in a particular state; borrowed bits can be supplied in any state and must be returned in that same state.
We will talk about generation in reversible gate sets and will share a description of the maximal gate sets without memory. We will outline our understanding of maximal gate sets closed with ancilla and borrowed memory, using Scott Aaronson, Daniel Grier and Luke Schaeffer?s analysis of ancilla closed classes of reversible gates on a state set of order 2. We will introduce Emil Jerabek?s dual structure to memoryless gate sets and will speculate on the version that should be used for ancilla and borrow memory.
The talk is necessarily interdisciplinary. It will be of interest to and accessible to researchers with an interest in permutation groups, computational modelling, clone theory, theoretical computer science or related fields.