A Category Theoretic Interpretation of Gandy's Principles for Mechanisms

Joseph Razavi
Andrea Schalk

Based on Gandy's principles for models of computation we give category-theoretic axioms describing locally deterministic updates to finite objects. Rather than fixing a particular category of states, we describe what properties such a category should have. The computation is modelled by a functor that encodes updating the computation, and we give an abstract account of such functors. We show that every updating functor satisfying our conditions is computable.

In Michele Pagani and Sandra Alves: Proceedings Twelfth Workshop on Developments in Computational Models and Ninth Workshop on Intersection Types and Related Systems (DCM 2018 and ITRS 2018 ), Oxford, UK, 8th July 2018, Electronic Proceedings in Theoretical Computer Science 293, pp. 85–92.
Published: 23rd April 2019.

ArXived at: http://dx.doi.org/10.4204/EPTCS.293.7 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org