A Category Theoretic Interpretation of Gandy’s Principles for Mechanisms

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Bibliographical metadata

Original languageEnglish
Title of host publicationElectronic Proceedings in Theoretical Computer Science
Publication statusAccepted/In press - 1 Feb 2019

Related information

Researchers

View all