Niels Vorneeveld: Representability in partial combinatory algebras

Abstract: Coding structures with partial combinatory algebras (pca’s) gives us a way to define realizability. To better understand the effective power of a pca model, we can study which functions it represents. For some of the classical examples, representability coincides with continuity in a certain topology, while other models might be able to effectively distinguish between its elements. It is possible to enrich a pca by altering the model such that it represents more functions; this can be related to giving oracles to Turing machines in the case of Kleene’s first algebra. We will discuss how this method and others give us pca’s with interesting properties.