On the Existence of Extensional Partial Combinatory Algebras
Bethke, Ingemarie
J. Symbolic Logic, Tome 52 (1987) no. 1, p. 819-833 / Harvested from Project Euclid
The principal aim of this paper is to present a construction method for nontotal extensional combinatory algebras. This is done in $\S2$. In $\S0$ we give definitions of some basic notions for partial combinatory algebras from which the corresponding notions for (total) combinatory algebras are obtained as specializations. In $\S1$ we discuss some properties of nontotal extensional combinatory algebras in general. $\S2$ describes a "partial" variant of reflexive complete partial orders yielding nontotal extensional combinatory algebras. Finally, $\S3$ deals with properties of the models constructed in $\S2$, such as incompletability, having no total submodel and the pathological behaviour with respect to the interpretation of unsolvable $\lambda$-terms.
Publié le : 1987-09-14
Classification: 
@article{1183742447,
     author = {Bethke, Ingemarie},
     title = {On the Existence of Extensional Partial Combinatory Algebras},
     journal = {J. Symbolic Logic},
     volume = {52},
     number = {1},
     year = {1987},
     pages = { 819-833},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742447}
}
Bethke, Ingemarie. On the Existence of Extensional Partial Combinatory Algebras. J. Symbolic Logic, Tome 52 (1987) no. 1, pp.  819-833. http://gdmltest.u-ga.fr/item/1183742447/