1. Embeddings between Partial Combinatory Algebras
- Author
-
Golov, A. and Terwijn, Sebastiaan A.
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES ,Logic ,Mathematics - Logic ,Logic in Computer Science (cs.LO) ,Mathematics::Logic ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Computer Science::Logic in Computer Science ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Logic (math.LO) ,Mathematics ,Computer Science::Formal Languages and Automata Theory - Abstract
Partial combinatory algebras are algebraic structures that serve as generalized models of computation. In this paper, we study embeddings of pcas. In particular, we systematize the embeddings between relativizations of Kleene's models, of van Oosten's sequential computation model, and of Scott's graph model, showing that an embedding between two relativized models exists if and only if there exists a particular reduction between the oracles. We obtain a similar result for the lambda calculus, showing in particular that it cannot be embedded in Kleene's first model., Comment: 31 pages
- Published
- 2023