Computability in partial combinatory algebras

2019/10/21 by Sebastiaan A. Terwijn, Terwijn, S. A.
Computer Science · #03B40 #03D25 #03D45 #03D80 #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1910.09258

openalex publication_date 2019/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• The complexity of completions in partial combinatory algebra
• Effective Operations of Type 2 in Pcas
• A general form of relative recursion
• Embeddings between partial combinatory algebras
• Partial combinatory algebra and generalized numberings