Fixed point theorems for precomplete numberings

DOI10.1016/J.APAL.2019.04.013MaRDI QIDQ2311209zbMATH OpenOpenAlexWikidataFDO

Authors Henk Barendregt, Sebastiaan A. Terwijn

Publication date 10 July 2019

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.06233, http://hdl.handle.net/2066/205967

zbMATH Keywords

ADN theoremArslanov completeness criterionpartial combinatory algebrasprecomplete numberingsErshov recursion theorem

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45)

Abstract: In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.

Recommendations

• Partial numberings and precompleteness
• Extremal numberings and fixed point theorems
• Computability in partial combinatory algebras
• Alternative Characterizations of Precomplete Numerations
• scientific article; zbMATH DE number 58108

Cites work

• scientific article; zbMATH DE number 3875232 (Why is no real title available?)
• scientific article; zbMATH DE number 3827843 (Why is no real title available?)
• scientific article; zbMATH DE number 3735770 (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 3995657 (Why is no real title available?)
• scientific article; zbMATH DE number 3216177 (Why is no real title available?)
• A Note on Positive Equivalence Relations
• A survey on universal computably enumerable equivalence relations
• Algorithmic randomness and complexity.
• Calculating self-referential statements
• Classical recursion theory. Vol. II
• Classifying positive equivalence relations
• Degrees of members of \(\Pi_ 1^ 0\) classes
• GENERALIZATIONS OF THE RECURSION THEOREM
• Higher-order computability
• Kleene's amazing second recursion theorem
• On degrees of unsolvability
• Positive equivalences
• Realizability. An introduction to its categorical side
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY
• The noneffectivity of Arslanov's completeness criterion and related theorems
• The þ-function in λ-K-conversion
• Theoretical Pearls:Representing ‘undefined’ in lambda calculus
• Theorie der Numerierungen I
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(17)

• scientific article; zbMATH DE number 58108 (Why is no real title available?)
• On the main scientific achievements of Victor Selivanov
• Effectively infinite classes of numberings and fixed point theorems
• Extremal numberings and fixed point theorems
• Fixed-point selection functions
• Numberings, c.e. oracles, and fixed points
• Partial numberings and precompleteness
• Partial combinatory algebra and generalized numberings
• Precomplete numberings
• scientific article; zbMATH DE number 3557768 (Why is no real title available?)
• Fixpoints and relative precompleteness
• The noneffectivity of Arslanov's completeness criterion and related theorems
• Ordinal analysis of partial combinatory algebras
• Some properties of precompletely and positively numbered sets
• Alternative Characterizations of Precomplete Numerations
• Computability in partial combinatory algebras
• Generic Kleene fixed point theorem

This page was built for publication: Fixed point theorems for precomplete numberings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2311209)