On constructions of partial combinatory algebras and their relation to topology

Abstract

In this thesis we study models of partial combinatory algebras and we aim to construct new examples. Mainly, the sets of representable functions of these models and their connections to topology are explored. One famous example is Scott's Graph model, which can simulate the untyped lambda calculus. Using a theorem by Jaap van Oosten, we study an extension of this Graph Model in which the complement function is representable. This new model is decidable. Relations with other models yield two more decidable extensions, with interesting categorical properties. Additionally, a model is constructed that has a connection to the Cantor topology, and a model is made using the power set of another model.