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.
翻译:部分组合代数是作为通用计算模型的代数结构。 在本文中, 我们研究嵌入的贝壳。 特别是, 我们系统化了Kleene模型相对化、 van Oosten连续计算模型相对化、 van Oosten的相继计算模型和 Scott 的图形模型之间的嵌入, 表明在两种相对化模型存在, 并且只有在神器之间有特定的减值时才能存在。 我们对羊绒微积分得出类似的结果, 特别表明它不能嵌入Kleene的第一个模型中 。