论文标题
部分组合代数之间的嵌入
Embeddings between partial combinatory algebras
论文作者
论文摘要
部分组合代数是代数结构，可作为一般计算模型。在本文中，我们研究了PCAS的嵌入。特别是，我们将Kleene模型的相对化，Van Oosten的顺序计算模型和Scott的图形模型之间的嵌入系统化，这表明当两个相对模型之间存在嵌入时，并且仅当存在特定的口腔之间时存在特定的减少时。我们获得了lambda演算的类似结果，特别表明它不能嵌入Kleene的第一个模型中。
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.
