Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-18T03:57:11.699Z Has data issue: false hasContentIssue false

COMPUTABILITY IN PARTIAL COMBINATORY ALGEBRAS

Published online by Cambridge University Press:  05 January 2021

SEBASTIAAN A. TERWIJN*
Affiliation:
DEPARTMENT OF MATHEMATICS RADBOUD UNIVERSITY NIJMEGEN P.O. BOX 9010, 6500 GL NIJMEGEN, THE NETHERLANDS E-mail: terwijn@math.ru.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 prove a number of elementary facts about computability in partial combinatory algebras (pca’s). We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.

Information

Type
Articles
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press