Fixed point theorems for precomplete numberings

DOI10.1016/J.APAL.2019.04.013zbMATH Open1454.03049arXiv1809.06233OpenAlexW2890683191WikidataQ127986194 ScholiaQ127986194MaRDI QIDQ2311209FDOQ2311209

Authors: Henk Barendregt, Sebastiaan A. Terwijn 

Publication date: 10 July 2019

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

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.

Full work available at URL: https://arxiv.org/abs/1809.06233

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

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)

Cites Work

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

Cited In (17)

• Title not available (Why is that?)
• On the main scientific achievements of Victor Selivanov
• Effectively infinite classes of numberings and fixed point theorems
• Extremal numberings and fixed point theorems
• Numberings, c.e. oracles, and fixed points
• Fixed-point selection functions
• Partial numberings and precompleteness
• Partial combinatory algebra and generalized numberings
• Precomplete numberings
• Title not available (Why is that?)
• Fixpoints and relative precompleteness
• Ordinal analysis of partial combinatory algebras
• Some properties of precompletely and positively numbered sets
• The noneffectivity of Arslanov's completeness criterion and related theorems
• 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)