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.


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?
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.