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.