# Examples for Partial Combinatory Algebras

I am currently working on my Bachelor thesis about Turing Categories (see Introduction to Turing Categories ). In this context I got some questions regarding Partial Combinatory Algebras (PCAs), which I want to get out here, as neither of my supervisors could help me.

1. In Total Maps of Turing Categories  necessary and sufficient conditions for a category to appear as subcategory of total maps of some Turing category are given. As a corollary, the category of PTIME-functions, LOGSPACE-functions, LTIME-functions etc. can appear as total maps of some Turing category. Does this imply that these classes can be characterized by a specific PCA and (if so) how does it relate to Kleene's first model? In other words, are there complexity classes which can be represented by sub-PCAs of Kleene's first model?

2. Are there models of PCAs which are not a priori inspired by computability theory? The general setting of applicative system and computable function (see  section 4) seems to be rather general such that it may be applicable in general categories. However all my attempts to find a PCA in categories like Top, K-Vec, R-Alg, R-Mod etc. have failed. I am well aware of Kleene's second model, Scott's graph model and the $$\lambda$$-calculus as they are stated in Realizability - An Introduction to its Categorical Side . I am just curious whether this notion of computability naturally arises anywhere else in ordinary mathematics...

I hope anybody can help me out. No matter what, thank you all for your time.

Consider a subPCA $$A$$ of Kleene's first algebra. It contains $$K$$ and $$S$$. These are sufficient to implement every total computable function, so $$A$$ must contain at least these, and cannot be just some limited complexity class.
I do not quite understand why Kleene's second algebra and Scott's graph model aren't "topological". Kleene's second algebra is the universal 0-dimensional countably based Hausdorff space. Scott's graph model is the universal $$T_0$$ countably based space. These characterizations have no trace of computability, but because the spaces are universal it is to be expected that they have a very rich structure, and so can be made into models of $$\lambda$$-calculus.
• ... a correspondence between PCAs and untyped $\lambda$-calculus, my other question could be answered by "just search for reflexive objects". However I rather search for some "simple" example along the lines of "just consider evaluation of polynomials over some commutative ring" or something with "homotopies of paths / loops" or so. Jun 5 '19 at 14:20