Classical recursion theory. The theory of functions and sets of natural numbers
From MaRDI portal
Publication:1188502
zbMath0661.03029MaRDI QIDQ1188502
Publication date: 17 September 1992
Published in: Studies in Logic and the Foundations of Mathematics (Search for Journal in Brave)
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)
The Medvedev lattice of computably closed sets ⋮ The Hausdorff-Ershov hierarchy in Euclidean spaces ⋮ Refuting learning revisited. ⋮ Learning power and language expressiveness. ⋮ Trees and learning ⋮ Limiting partial combinatory algebras ⋮ Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations ⋮ \(\Sigma_ 1^ 1\)-completeness of a fragment of the theory of trees with subtree relation ⋮ Logicism as making arithmetic explicit ⋮ Invertible classes ⋮ Strong enumeration reducibilities ⋮ Results on memory-limited U-shaped learning ⋮ Computability by nondeterministic program and the Moschovakis search computability ⋮ On the learnability of vector spaces ⋮ Undecidable fragments of elementary theories ⋮ The last question on recursively enumerable \(m\)-degrees ⋮ Randomness and universal machines ⋮ On the classification of recursive languages ⋮ Extended regular expressions: succinctness and decidability ⋮ Traces, traceability, and lattices of traces under the set theoretic inclusion ⋮ Diagonalization in double frames ⋮ Levels of uniformity ⋮ The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma ⋮ An oracle builder's toolkit ⋮ Reducibilities among equivalence relations induced by recursively enumerable structures ⋮ Badness and jump inversion in the enumeration degrees ⋮ First-order logic in the Medvedev lattice ⋮ Closed choice and a uniform low basis theorem ⋮ An analytic system with a computable hyperbolic sink whose basin of attraction is non-computable ⋮ Probabilistic satisfiability: algorithms with the presence and absence of a phase transition ⋮ Beta-shifts, their languages, and computability ⋮ Bounded-low sets and the high/low hierarchy ⋮ Polynomial clone reducibility ⋮ Limit-depth and DNR degrees ⋮ Comparing Peano arithmetic, Basic Law V, and Hume's Principle ⋮ Limit complexities revisited ⋮ When unlearning helps ⋮ Degrees of difficulty of generalized r.e. separating classes ⋮ Non-U-shaped vacillatory and team learning ⋮ A uniquely ergodic cellular automaton ⋮ Bounded enumeration reducibility and its degree structure ⋮ Natural factors of the Medvedev lattice capturing IPC ⋮ Learnability and positive equivalence relations ⋮ Learning in Friedberg numberings ⋮ The strength of the Grätzer-Schmidt theorem ⋮ Covering the recursive sets ⋮ Bi-immunity over different size alphabets ⋮ A class of recursive permutations which is primitive recursive complete ⋮ Intermediate logics and factors of the Medvedev lattice ⋮ \(\Pi_1^0 \) classes, LR degrees and Turing degrees ⋮ Random numbers as probabilities of machine behavior ⋮ On relative randomness ⋮ Consistency of the intensional level of the minimalist foundation with Church's thesis and axiom of choice ⋮ Things that can be made into themselves ⋮ The scope of Gödel's first incompleteness theorem ⋮ Universal recursively enumerable sets of strings ⋮ Computably enumerable sets and related issues ⋮ Computability in planar dynamical systems ⋮ Quantum value indefiniteness ⋮ Approximation representations for \(\Delta_2\) reals ⋮ Numberings optimal for learning ⋮ The diagonalization method in quantum recursion theory ⋮ On computably enumerable structures ⋮ Continuum, name and paradox ⋮ Iterative learning of simple external contextual languages ⋮ Index sets and universal numberings ⋮ Goodness in the enumeration and singleton degrees ⋮ Introduction to Turing categories ⋮ Searching for shortest and least programs ⋮ Constructive dimension and Turing degrees ⋮ Input-dependence in function-learning ⋮ Speed-up theorems in type-2 computations using oracle Turing machines ⋮ On the solution of trivalent decision problems by quantum state identification ⋮ Monoidal computer III: a coalgebraic view of computability and complexity (extended abstract) ⋮ Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems ⋮ A class of reversible primitive recursive functions ⋮ Degree spectra of the successor relation of computable linear orderings ⋮ Khutoretskii's theorem for generalized computable families ⋮ A metasemantic challenge for mathematical determinacy ⋮ Prescribed learning of r.e. classes ⋮ A semantical proof of De Jongh's theorem ⋮ The structure of the s-degrees contained within a single e-degree ⋮ Randomness and initial segment complexity for measures ⋮ Minimum-weight cycle covers and their approximability ⋮ On interpreting Chaitin's incompleteness theorem ⋮ A foundation for real recursive function theory ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ Reductions between types of numberings ⋮ From computation to foundations via functions and application: The \(\lambda\)-calculus and its webbed models ⋮ Degrees of Dowd-type generic oracles ⋮ On trees without hyperimmune branches ⋮ Intensional Kleene and Rice theorems for abstract program semantics ⋮ On the interplay between inductive inference of recursive functions, complexity theory and recursive numberings ⋮ Graphs realised by r.e. equivalence relations ⋮ A reducibility related to being hyperimmune-free ⋮ Avoiding coding tricks by hyperrobust learning ⋮ \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets ⋮ Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness. ⋮ The efficiency of primitive recursive functions: a programmer's view ⋮ On the degrees of constructively immune sets
This page was built for publication: Classical recursion theory. The theory of functions and sets of natural numbers
