# Examples for Partial Combinatory Algebras

I am currently working on my Bachelor thesis about Turing Categories (see Introduction to Turing Categories [1]). 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 [2] 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 [1] 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 [3]. 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, 2019 at 14:20