Combinatory algebras of functions and their modest sets

Abstract

We consider a general notion of computation on arbitrary sets, where every element of the set acts as ``program'', but also as ``input''. We have a partial function, ``the application'', that sends a pair (x,y) to an element x.y. Think of this element as the result of applying program x to input y. The axioms this application has to satisfy, define the notion of partial combinatory algebra (PCA).

In this thesis we consider the set of all functions from A to A, for some infinite set A. Define an application on this set by using the idea of interrogation: a function asks questions of the form ``what is your value at this element?'' to a second function. Use the so called sequential functions to investigate this application. When A is the set of natural numbers, we can use topological properties. We also consider the notion of modest sets on our partial combinatory algebra, with ``computable functions'' between them. This notion can be related to the category of equilogical spaces.