In this note, we prove that having unique head-normal forms is a sufficient condition on partial combinatory algebras to be completable. As application, we show that the pca of strongly normalizing CL-terms as well as the pca of natural numbers with partial recursive function application can be extended to total combinatory algebras.

, ,
Department of Computer Science [CS]
Specification and Analysis of Embedded Systems

Bethke, I., Klop, J. W., & de Vrijer, R. (1995). Completing partial combinatory algebras with unique head-normal forms. Department of Computer Science [CS]. CWI.