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.
Original languageEnglish
Title of host publicationElectronic Proceedings in Theoretical Computer Science
Publication statusAccepted/In press - 1 Feb 2019

Keywords

  • Local determinism
  • Gandy
  • Cellular automata
  • Parallel computation
  • Time-varying graphs
  • Models of computation

Fingerprint

Dive into the research topics of 'A Category Theoretic Interpretation of Gandy’s Principles for Mechanisms'. Together they form a unique fingerprint.

Cite this