2018/09/17 by Henk Barendregt, Barendregt, H. P., Sebastiaan A. Terwijn +1
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.1809.06233
openalex publication_date 2018/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.