220510 Jetze Zoethout

In the 1930s, Turing, Kleene, Church and others proposed a precise, mathematical notion of a computable function on the natural numbers. For the first time in history, this allowed mathematicians to prove that certain problems are not solvable by an algorithm. Moreover, it turned out that the computability theory of the natural numbers enjoys certain "algebraic" properties that also manifest themselves elsewhere. A structure satisfying these algebraic properties is called a partial combinatory algebra (PCA), and the study of PCAs can be seen as abstract recursion theory. In this talk, I want to give you a flavor of the subject by considering some concrete examples of PCAs, and how they relate to each other.