Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T22:57:35.126Z Has data issue: false hasContentIssue false

Extending partial combinatory algebras

Published online by Cambridge University Press:  01 August 1999

INGE BETHKE
Affiliation:
University of Nijmegen, Department of Computer Science, Email: inge@cs.vu.nl
JAN WILLEM KLOP
Affiliation:
University of Nijmegen, Department of Computer Science, and CWI, Amsterdam and Vrije Universiteit Amsterdam, Department of Computer Science, Email: jwk@cwi.nl
ROEL de VRIJER
Affiliation:
Vrije Universiteit Amsterdam, Department of Computer Science, Email: rdv@cs.vu.nl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We give a negative answer to the question of 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 depend heavily on syntactic techniques. In particular, it provides 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.

Information

Type
Research Article
Copyright
© 1999 Cambridge University Press