Computability Models and Realizability Toposes

Jetze Zoethout

Research output: ThesisDoctoral thesis 1 (Research UU / Graduation UU)


A partial combinatory algebra (PCA) is a model of computation that embodies a certain notion of algorithm. The elements of a PCA act simultaneously as algorithms and as inputs that may be fed to these algorithms. For each PCA, we can construct a model of intuitionistic mathematics, called the realizability topos of the PCA. In this model, validity is governed by its underlying PCA: the truth of a statement must be corroborated by an algorithm of the PCA. In this thesis, we investigate some general properties of the construction that assigns, to a PCA, its corresponding realizability topos. We show that realizability toposes are not closed under certain elementary operations on categories, such as products and slices. On the basis of these negative results, we introduce natural classes of ‘realizability-like’ toposes that are closed under these operations. In addition, we investigate the general theory of computing with functions on a PCA. This includes computation relative to an oracle, which is a form of computation that may consult an external resource (the oracle) a finite number of times before coming up with a final output. Moreover, we study computation with higher-order functionals, which are functions that take functions, rather than elements, as their input.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Utrecht University
  • Moerdijk, Ieke, Primary supervisor
  • van Oosten, Jaap, Co-supervisor
Award date30 May 2022
Place of PublicationUtrecht
Print ISBNs978-90-393-7454-2
Electronic ISBNs978-90-393-7454-2
Publication statusPublished - 30 May 2022


  • Partial combinatorial algebra
  • Higher-order computation
  • Topos theory
  • Realizability


Dive into the research topics of 'Computability Models and Realizability Toposes'. Together they form a unique fingerprint.

Cite this