Hostname: page-component-7b7567c8c-m6dxt Total loading time: 0 Render date: 2026-11-19T00:27:56.802Z Has data issue: false hasContentIssue false

On the existence of extensional partial combinatory algebras

Published online by Cambridge University Press:  12 March 2014

Ingemarie Bethke*
Affiliation:
Centre for Cognitive Science, University of Edinburgh, Edinburgh EH8 91W, Scotland

Abstract

The principal aim of this paper is to present a construction method for nontotal extensional combinatory algebras. This is done in §2. In §0 we give definitions of some basic notions for partial combinatory algebras from which the corresponding notions for (total) combinatory algebras are obtained as specializations. In §1 we discuss some properties of nontotal extensional combinatory algebras in general. §2 describes a “partial” variant of reflexive complete partial orders yielding nontotal extensional combinatory algebras. Finally, §3 deals with properties of the models constructed in §2, such as incompletability, having no total submodel and the pathological behaviour with respect to the interpretation of unsolvable λ-terms.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1987

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable