1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Hello Mr. Bauer, thank you for answering that quick! I feared so. I think I found the flaw in my idea: As the application is in general not total, the fact that some complexity classes can arise as the total maps of some Turing category, does not imply that these total maps are exactly those computable of a PCA. However I still think that it should imply that there is a PCA, whose total combinators are precisely the functions belonging to the complexity class... I didnt say K2 and Pw are not topological, I was rather thinking of other examples. I guess, as there seems to be ... $\endgroup$
    – Jonas Linssen
    Jun 5, 2019 at 14:12
  • $\begingroup$ ... 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. $\endgroup$
    – Jonas Linssen
    Jun 5, 2019 at 14:20
  • $\begingroup$ Perhaps I don't understand your question. Every subPCA of Kleene's first algebra contains every total computable function, that's my point. Regarding reflexive objects, you might find this paper by Hofmann and Mislove interesting. They show that topological models of lambda calculus cannot be compact Hausdorff. $\endgroup$
    – Andrej Bauer
    Jun 5, 2019 at 14:32
  • $\begingroup$ Clearly the total polynomial time functions etc. are represented in Kleene's first Algebra. The point of Total Maps of Turing Categories is however that you can construct a Turing category for which the total maps are precisely those belonging to your chosen complexity class. As Turing categories are completely determined by some PCA in it, imo this should imply that there is a PCA for which the all total combinators relate 1:1 to the functions in that class. My question thus is, how does this PCA relate to Kleene's first algebra? Thanks for the reference, I certainly will look it up! $\endgroup$
    – Jonas Linssen
    Jun 5, 2019 at 14:38
  • $\begingroup$ And I think I gave you an answer: every subPCA of Kleene's first algebra contains all total computable functions. Why isn't this a negative answer to one of your questions? $\endgroup$
    – Andrej Bauer
    Jun 5, 2019 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.