A Category Theoretic Interpretation of Gandy's Principles for Mechanisms

2019/04/21 by Joseph Razavi, Andrea Schalk
Computer Science · Mathematics · #Adjoint functors #Algebra over a field #Axiom #Category theory #Computability, Logic, AI Algorithms #Computation #Functor #Homotopy and Cohomology in Algebraic Topology #Interpretation (philosophy) #Logic, programming, and type systems #cs.DM #cs.LO

paper · pdf · doi:10.4204/eptcs.293.7

published as EPTCS 293, 2019, pp. 85-92 · In Proceedings DCM 2018 and ITRS 2018 , arXiv:1904.09561

openalex publication_date 2019/04/21 · arxiv created 2019/04/23 · arxiv updated 2019/04/24 · openalex created_date 2019/04/25 · openalex updated_date 2026/08/05

Abstract

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.

Citations

• Proceedings Twelfth Workshop on Developments in Computational Models and Ninth Workshop on Intersection Types and Related Systems
• Categories for the Working Mathematician