A Sufficient Condition for Completability of Partial Combinatory Algebras
Asperti, Andrea ; Ciabattoni, Agata
J. Symbolic Logic, Tome 62 (1997) no. 1, p. 1209-1214 / Harvested from Project Euclid
A Partial Combinatory Algebra is completable if it can be extended to a total one. In [1] it is asked (question 11, posed by D. Scott, H. Barendregt, and G. Mitschke) if every PCA can be completed. A negative answer to this question was given by Klop in [12, 11]; moreover he provided a sufficient condition for completability of a PCA $(M, \cdot, K, S)$ in the form of ten axioms (inequalities) on terms of $M$. We prove that just one of these axiom (the so called Barendregt's axiom) is sufficient to guarantee (a slightly weaker notion of) completability.
Publié le : 1997-12-14
Classification: 
@article{1183745377,
     author = {Asperti, Andrea and Ciabattoni, Agata},
     title = {A Sufficient Condition for Completability of Partial Combinatory Algebras},
     journal = {J. Symbolic Logic},
     volume = {62},
     number = {1},
     year = {1997},
     pages = { 1209-1214},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745377}
}
Asperti, Andrea; Ciabattoni, Agata. A Sufficient Condition for Completability of Partial Combinatory Algebras. J. Symbolic Logic, Tome 62 (1997) no. 1, pp.  1209-1214. http://gdmltest.u-ga.fr/item/1183745377/