Computability in partial combinatory algebras

Bulletin of Symbolic Logic 26 (3-4):224-240 (2020)
  Copy   BIBTEX

Abstract

We prove a number of elementary facts about computability in partial combinatory algebras. 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.

Categories

Keywords

Reprint years

DOI

10.1017/bsl.2020.46

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 104,706

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Fixed point theorems for precomplete numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.
On the existence of extensional partial combinatory algebras.Ingemarie Bethke - 1987 - Journal of Symbolic Logic 52 (3):819-833.
Ordinal analysis of partial combinatory algebras.Paul Shafer & Sebastiaan A. Terwijn - 2021 - Journal of Symbolic Logic 86 (3):1154-1188.
Partial Combinatory Algebras of Functions.Jaap van Oosten - 2011 - Notre Dame Journal of Formal Logic 52 (4):431-448.
Stability of representations of effective partial algebras.Jens Blanck, Viggo Stoltenberg-Hansen & John V. Tucker - 2011 - Mathematical Logic Quarterly 57 (2):217-231.
Computable and continuous partial homomorphisms on metric partial algebras.Viggo Stoltenberg-Hansen & John V. Tucker - 2003 - Bulletin of Symbolic Logic 9 (3):299-334.
A note on partial numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
Extremal numberings and fixed point theorems.Marat Faizrahmanov - 2022 - Mathematical Logic Quarterly 68 (4):398-408.
A sufficient condition for completability of partial combinatory algebras.Andrea Asperti & Agata Ciabattoni - 1997 - Journal of Symbolic Logic 62 (4):1209-1214.

Analytics

Added to PP
2021-01-06

Downloads
24 (#1,000,712)

6 months
3 (#1,186,452)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Theorie der Numerierungen I.Ju L. Eršov - 1973 - Mathematical Logic Quarterly 19 (19‐25):289-388.
Theorie der Numerierungen II.J. U. L. Eršov - 1975 - Mathematical Logic Quarterly 21 (1):473-584.
Fixed point theorems for precomplete numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.

View all 9 references / Add more references