An Algebraic Theory for Reversible Computation

Description

In this talk I will outline an adaption of the long standing theory of clones to deal with reversible computation. Reversible computation has been investigated intensely for several reasons for several decades, the fundamental work of Toffoli and others laying some basis upon which developments such as quantum computation is building. The theory of clones is a way of thinking about the computation possible with certain functions. Most importantly, clone theory has found a way of describing closed sets of functions equivalently by their generators or by the relational structures they preserve, the dual structure of clones. I will introduce the algebraic techniques used and show how we can replicate and generalise the results from Toffoli's 1980 paper on reversible computation. Looking beyond binary state sets, we find that some restrictions that he found do not apply. We will then look at some of the possible generalisations of the relations, at possible dual structures for reversible clone theory.

Period	12 Jan 2016
Event title	unbekannt/unknown
Event type	Other
Location	FinlandShow on map