Kleene's Amazing Second Recursion Theorem

DOI10.2178/bsl/1286889124zbMath1211.03061OpenAlexW2118589925MaRDI QIDQ3161629

Yiannis N. Moschovakis

Publication date: 15 October 2010

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/bsl/1286889124

zbMATH Keywords

computable functionsrecursion theoremeffective descriptive set theory

Mathematics Subject Classification ID

Descriptive set theory (03E15) Recursive functions and relations, subrecursive hierarchies (03D20) Theory of numerations, effectively presented structures (03D45)

Related Items

Fixpoints and relative precompleteness ⋮ From Turing machines to computer viruses ⋮ Monoidal computer. I: Basic computability by string diagrams ⋮ Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines ⋮ Intuitionism and effective descriptive set theory ⋮ Classes of Polish spaces under effective Borel isomorphism ⋮ Classical descriptive set theory as a refinement of effective descriptive set theory ⋮ Polish group actions and effectivity ⋮ Hyperarithmetical Sets ⋮ GENERALIZATIONS OF THE RECURSION THEOREM ⋮ Monoidal computer III: a coalgebraic view of computability and complexity (extended abstract) ⋮ ON THE DIAGONAL LEMMA OF GÖDEL AND CARNAP ⋮ Fixed point theorems for precomplete numberings ⋮ The noneffectivity of Arslanov's completeness criterion and related theorems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classical descriptive set theory as a refinement of effective descriptive set theory
• Provability interpretations of modal logic
• Borel extractions of converging sequences in compact sets of Borel functions
• Many-one degrees of the predicates \(H_ a(x)\)
• Zur Theorie der konstruktiven Wohlordnungen
• 𝐴𝐷 and the very fine structure of 𝐿(ℝ)
• Hierarchies of number-theoretic predicates
• Recursive well-orderings
• On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
• Effective operations on partial recursive functions
• Effective properties in compact sets of Borel functions
• Projective determinacy
• Supercompact cardinals, sets of reals, and weakly homogeneous trees
• Uncomplemented C(X)-Subalgebras of C(X)
• Alternative proof of a theorem of Kleene
• On notation for ordinal numbers
• On the Forms of the Predicates in the Theory of Constructive Ordinals
• On the interpretation of intuitionistic number theory
• Recursively enumerable sets of positive integers and their decision problems
• Creative sets