Classical recursion theory. The theory of functions and sets of natural numbers

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Related Items (only showing first 100 items - show all)

Learning Families of Closed Sets in Matroids ⋮ Some Transfinite Generalisations of Gödel’s Incompleteness Theorem ⋮ Exact Pairs for Abstract Bounded Reducibilities ⋮ On the classification of computable languages ⋮ Is there a ``Hilbert thesis? ⋮ The complexity of universal text-learners ⋮ Effective applicative structures ⋮ Effectivity questions for Kleene's recursion theorem ⋮ Initial segment complexities of randomness notions ⋮ On proofs of the incompleteness theorems based on Berry's paradox by Vopěnka, Chaitin, and Boolos ⋮ On notions of computability-theoretic reduction between Π21 principles ⋮ Herbrand semantics, the potential infinite, and ontology-free logic ⋮ Turing incomparability in Scott sets ⋮ Lightface $$\mathop {\varPi }\nolimits _{3}^{0}$$ Π 3 0 -Completeness of Density Sets Under Effective Wadge Reducibility ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ The impact of models of a physical oracle on computational power ⋮ Covering the Recursive Sets ⋮ Fixpoints and relative precompleteness ⋮ Infima of d.r.e. degrees ⋮ Unpredictability and Computational Irreducibility ⋮ The number of certain integral polynomials and nonrecursive sets of integers, Part 2 ⋮ Effective genericity and differentiability ⋮ Sofic profiles of $S(\omega)$ and computability ⋮ On the scope of the Effros theorem ⋮ The jump is definable in the structure of the degrees of unsolvability ⋮ Composition Over the Natural Number Ordering with an Extra Binary Relation ⋮ Depth, Highness and DNR Degrees ⋮ Computing the exact number of periodic orbits for planar flows ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ A syntactic approach to Borel functions: some extensions of Louveau's theorem ⋮ Unnamed Item ⋮ Zero-dimensional $\sigma $-homogeneous spaces ⋮ s-Degrees within e-Degrees ⋮ Folding left and right matters: Direct style, accumulators, and continuations ⋮ Automorphisms ofη-like computable linear orderings and Kierstead's conjecture ⋮ Programming Experimental Procedures for Newtonian Kinematic Machines ⋮ Semi-honest subrecursive degrees and the collection rule in arithmetic ⋮ Minimum-Weight Cycle Covers and Their Approximability ⋮ Embeddings between partial combinatory algebras ⋮ Varieties of self-reference in metamathematics ⋮ Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees ⋮ Closed left-r.e. sets ⋮ Hierarchies of function classes defined by the first-value operator ⋮ Prescribed Learning of R.E. Classes ⋮ Learning in Friedberg Numberings ⋮ Roots and (Re)sources of Value (In)definiteness Versus Contextuality ⋮ Weakly Represented Families in Reverse Mathematics ⋮ Strength and Weakness in Computable Structure Theory ⋮ $sQ_1$-degrees of computably enumerable sets ⋮ Linear dependent types in a call-by-value scenario ⋮ Universal Recursively Enumerable Sets of Strings ⋮ The finite intervals of the Muchnik lattice ⋮ Ideals in computable rings ⋮ The Information Content of Typical Reals ⋮ Truth-table Schnorr randomness and truth-table reducible randomness ⋮ Closed Left-R.E. Sets ⋮ An improved lower bound for the elementary theories of trees ⋮ The approximation structure of a computably approximable real ⋮ The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences ⋮ Noisy inference and oracles ⋮ Lowness properties and approximations of the jump ⋮ Index Sets and Universal Numberings ⋮ Alonzo church:his life, his work and some of his miracles ⋮ Production of Ideas by Means of Ideas: A Turing Machine Metaphor ⋮ An Essay in λ‐Calculus ⋮ Selection by Recursively Enumerable Sets ⋮ Turing Machines Can Be Efficiently Simulated by the General Purpose Analog Computer ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ Computational power of infinite quantum parallelism ⋮ Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets ⋮ On the hierarchies of Δ₂⁰-real numbers ⋮ Learners based on transducers ⋮ Function operators spanning the arithmetical and the polynomial hierarchy ⋮ The uniform Martin’s conjecture for many-one degrees ⋮ Unnamed Item ⋮ Highly Undecidable Problems For Infinite Computations ⋮ Difference randomness ⋮ Computability, noncomputability and undecidability of maximal intervals of IVPs ⋮ Computing a Glimpse of Randomness ⋮ ON A METRIC GENERALIZATION OF THE tt-DEGREES AND EFFECTIVE DIMENSION THEORY ⋮ Measure-theoretic applications of higher Demuth’s Theorem ⋮ Random Subgroups of Rationals ⋮ Computing boundary extensions of conformal maps ⋮ Effective λ-models versus recursively enumerable λ-theories ⋮ Locally finite ω-languages and effective analytic sets have the same topological complexity ⋮ On Approximate Decidability of Minimal Programs ⋮ Logical Theory of the Additive Monoid of Subsets of Natural Integers ⋮ COMPUTABILITY IN PARTIAL COMBINATORY ALGEBRAS ⋮ Learning from Streams ⋮ ON THE INVARIANCE OF GÖDEL’S SECOND THEOREM WITH REGARD TO NUMBERINGS ⋮ Hypersimplicity and semicomputability in the weak truth table degrees ⋮ Introduction to the Zambelli Festschrift ⋮ Aspects of Categorical Recursion Theory ⋮ ORDINAL ANALYSIS OF PARTIAL COMBINATORY ALGEBRAS ⋮ On the Computable Theory of Bounded Analytic Functions ⋮ Point Degree Spectra of Represented Spaces ⋮ Bounded Immunity and Btt-Reductions ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words ⋮ Lawvere-Tierney topologies for computability theorists ⋮ Satisfiability of Arbitrary Public Announcement Logic with Common Knowledge is Σ^1_1-hard

This page was built for publication: Classical recursion theory. The theory of functions and sets of natural numbers