Extending Partial Combinatory Algebras


We give a negative answer to the question whether every partial 
combinatory algebra can be completed. The explicit counterexample 
will be an intricately constructed term model, the construction 
and the proof that it works heavily depending on syntactic 
techniques. In particular, it is a nice example of reasoning with 
elementary diagrams and descendants. We also include a 
domain-theoretic proof of the existence of an incompletable 
partial combinatory algebra.