Computability in partial combinatory algebras
From MaRDI portal
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.
Recommendations
Cites work
- A general form of relative recursion
- Classical recursion theory. The theory of functions and sets of natural numbers
- Collapsing partial combinatory algebras
- Constructivism in mathematics. An introduction. Volume II
- Extending partial combinatory algebras
- Extensions of Scott's graph model and Kleene's second algebra
- Fixed point theorems for precomplete numberings
- GENERALIZATIONS OF THE RECURSION THEOREM
- Higher-order computability
- scientific article; zbMATH DE number 3889501 (Why is no real title available?)
- scientific article; zbMATH DE number 4148069 (Why is no real title available?)
- scientific article; zbMATH DE number 3827843 (Why is no real title available?)
- scientific article; zbMATH DE number 3900744 (Why is no real title available?)
- scientific article; zbMATH DE number 194101 (Why is no real title available?)
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 3536064 (Why is no real title available?)
- scientific article; zbMATH DE number 3556031 (Why is no real title available?)
- scientific article; zbMATH DE number 3216177 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3348085 (Why is no real title available?)
- Index sets of quotient objects of the Post numeration
- Introduction to Turing categories
- Realizability. An introduction to its categorical side
- Some reasons for generalising domain theory
- Theoretical Pearls:Representing ‘undefined’ in lambda calculus
- Theorie der Numerierungen I
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
Cited in
(16)- Completeness and reduction in algebraic complexity theory
- Extensions of Scott's graph model and Kleene's second algebra
- Partial combinatory algebra and generalized numberings
- Fixed point theorems for precomplete numberings
- Computing coproducts of finitely presented Gödel algebras
- On the existence of extensional partial combinatory algebras
- A sufficient condition for completability of partial combinatory algebras
- Generalizing Computability Theory to Abstract Algebras
- Collapsing partial combinatory algebras
- Extending partial combinatory algebras
- A notion of a computational step for partial combinatory algebras
- Ordinal analysis of partial combinatory algebras
- How much partiality is needed for a theory of computability?
- Embeddings between partial combinatory algebras
- Fixed point theorems in computability theory
- A general form of relative recursion
This page was built for publication: Computability in partial combinatory algebras
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4984865)
