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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

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

On the existence of extensional partial combinatory algebras.Ingemarie Bethke - 1987 - Journal of Symbolic Logic 52 (3):819-833.
Partial Combinatory Algebras of Functions.Jaap van Oosten - 2011 - Notre Dame Journal of Formal Logic 52 (4):431-448.
A General Form of Relative Recursion.Jaap van Oosten - 2006 - Notre Dame Journal of Formal Logic 47 (3):311-318.
Computable and continuous partial homomorphisms on metric partial algebras.Viggo Stoltenberg-Hansen & John V. Tucker - 2003 - Bulletin of Symbolic Logic 9 (3):299-334.
Computability and continuity in computable metric partial algebras equipped with computability structures.Fredrik Dahlgren - 2004 - Mathematical Logic Quarterly 50 (4):486.
Computability and continuity in metric partial algebras equipped with computability structures.Fredrik Dahlgren - 2004 - Mathematical Logic Quarterly 50 (4-5):486-500.
On the problem of deciding equality in partial combinatory algebras and in a formal system.Giuseppa Longo - 1976 - Studia Logica 35 (4):363 - 375.
A sufficient condition for completability of partial combinatory algebras.Andrea Asperti & Agata Ciabattoni - 1997 - Journal of Symbolic Logic 62 (4):1209-1214.
Partial algebras for Łukasiewicz logics and its extensions.Thomas Vetterlein - 2005 - Archive for Mathematical Logic 44 (7):913-933.
Review: Dimiter G. Skordev, Computability in Combinatory Spaces. An Algebraic Generalization of Abstract First Order Computability. [REVIEW]Dag Normann - 1995 - Journal of Symbolic Logic 60 (2):695-696.
D-algebras.Stanley Gudder - 1996 - Foundations of Physics 26 (6):813-822.
Introduction to Turing categories.J. Robin B. Cockett & Pieter Jw Hofstra - 2008 - Annals of Pure and Applied Logic 156 (2):183-209.
Skordev Dimiter G.. Computability in combinatory spaces. An algebraic generalization of abstract first order computability. Mathematics and its applications , vol. 55. Kluwer Academic publishers, Dordrecht, Boston, and London, 1992, xiv + 320 pp. [REVIEW]Dag Normann - 1995 - Journal of Symbolic Logic 60 (2):695-696.
Partial Boolean algebras in a broader sense.Janusz Czelakowski - 1979 - Studia Logica 38 (1):1 - 16.
Algebraic theory of quasivarieties of heterogeneous partial algebras.Peter Burmeister - 2004 - Studia Logica 78 (1-2):129-153.

Analytics

Added to PP
2021-01-06

Downloads
16 (#880,136)

6 months
9 (#298,039)

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 10 references / Add more references