A Category Theoretic Interpretation of Gandy’s Principles for Mechanisms

Joseph Razavi; Andrea Schalk

A Category Theoretic Interpretation of Gandy’s Principles for Mechanisms

Formal Methods

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	Electronic Proceedings in Theoretical Computer Science
Publication status	Accepted/In press - 1 Feb 2019

Keywords

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

Access to Document

https://arxiv.org/abs/1904.10109v1

Cite this

@inproceedings{2223c2bbdfb849c09c74a3d6b2acc13a,

title = "A Category Theoretic Interpretation of Gandy{\textquoteright}s Principles for Mechanisms",

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.",

keywords = "Local determinism, Gandy, Cellular automata, Parallel computation, Time-varying graphs, Models of computation",

author = "Joseph Razavi and Andrea Schalk",

year = "2019",

month = feb,

day = "1",

language = "English",

booktitle = "Electronic Proceedings in Theoretical Computer Science",

}

TY - GEN

T1 - A Category Theoretic Interpretation of Gandy’s Principles for Mechanisms

AU - Razavi, Joseph

AU - Schalk, Andrea

PY - 2019/2/1

Y1 - 2019/2/1

N2 - 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.

AB - 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.

KW - Local determinism

KW - Gandy

KW - Cellular automata

KW - Parallel computation

KW - Time-varying graphs

KW - Models of computation

M3 - Conference contribution

BT - Electronic Proceedings in Theoretical Computer Science

ER -

A Category Theoretic Interpretation of Gandy’s Principles for Mechanisms

Abstract

Keywords

Access to Document

Fingerprint

Cite this