Mathematical Sciences Seminar - Memoryless Computation and Universal Simulation
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
Consider a finite set A and an integer n>1. Memoryless computation is the study of instructions of the Cartesian power An (i.e. transformations An->An with at most one nontrivial coordinate function) and the semigroups of transformations that they generate. This model of computation, which was inspired by the famous XOR swap algorithm, has been recently revitalised by several new results, such as the proof that the full transformation semigroup of An may be generated by just n+1 instructions (Cameron-Fairbairn-Gadouleau `14).
In this talk, we will review the basic results on memoryless computation, and we will introduce the concept of simulation of a transformation g:An->An by f:Am->Am, where n≤m. We will show that there exists a transformation of An+2 that may simulate every transformation of An, and we will study other schemes of simulation such as sequential, parallel and quasi-parallel. This is joint work with Maximilien Gadouleau.
Contact name:
Department of Economics, Mathematics and Statistics