Classical recursion theory. Vol. II

Publication date: 25 October 1999

Published in: Studies in Logic and the Foundations of Mathematics (Search for Journal in Brave)

zbMATH Keywords

recursive sets; limit sets; computability theory; inductive inference; hierarchies; arithmetical sets; complexity theory; recursive functions; complexity classes; recursively enumerable sets; enumeration degrees; recursively enumerable degrees; reducibilities; computable sets; arithmetical degrees; classical recursion theory; Classical recursion theory

Mathematics Subject Classification ID

03-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations

03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D20: Recursive functions and relations, subrecursive hierarchies

03D25: Recursively (computably) enumerable sets and degrees

03D30: Other degrees and reducibilities in computability and recursion theory

03D28: Other Turing degree structures

03-00: General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to mathematical logic and foundations

03D55: Hierarchies of computability and definability

03Dxx: Computability and recursion theory

Related Items

Maximal contiguous degrees, Properly ?2 minimal degrees and 0? complementation, Turing degrees of nonabelian groups, Minimal complements for degrees below 0′, On the hierarchies of Δ₂⁰-real numbers, The minimal complementation property above 0′, Iteration, inequalities, and differentiability in analog computers, Robust learning with infinite additional information, Synthesizing noise-tolerant language learners, Probabilistic inductive inference: A survey, Synthesizing learners tolerating computable noisy data, On a class of fuzzy computable functions, Vacillatory and BC learning on noisy data, Representations versus numberings: On the relationship of two computability notions, Control structures in hypothesis spaces: The influence on learning, Learning algebraic structures from text, Aspects of complexity of probabilistic learning under monotonicity constraints, Cupping and noncupping in the enumeration degrees of \(\Sigma_ 2^ 0\) sets, The theory of the recursively enumerable weak truth-table degrees is undecidable, Classes with easily learnable subclasses, Undefinability of truth and nonstandard models, Equational theories for inductive types, Epistemic entrenchment and arithmetical hierarchy, Real recursive functions and their hierarchy, Determining and stationary sets for some classes of partial recursive functions, The complexity of achievement and maintenance problems in agent-based systems, Unifying logic, topology and learning in parametric logic, Mathematics based on incremental learning -- excluded middle and inductive inference, The Medvedev lattice of computably closed sets, The jump operation for structure degrees, Strong enumeration reducibilities, Learning recursive functions: A survey, Learning indexed families of recursive languages from positive data: A survey, \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly, Fine hierarchies and m-reducibilities in theoretical computer science, Consistent and coherent learning with \(\delta \)-delay, \(\Pi_1^0 \) classes, LR degrees and Turing degrees, Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\), A new conceptual framework for analog computation, Intervals and sublattices of the r.e. weak truth table degrees. I: Density, Recursively enumerable \(m\)- and \(tt\)-degrees. II: The distribution of singular degrees, An improved zero-one law for algorithmically random sequences, Myhill's work in recursion theory, Nondiamond theorems for polynomial time reducibility, Weakly semirecursive sets and r.e. orderings, Investigations on measure-one identification of classes of languages, Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, Equality is a jump, Computability on subsets of Euclidean space. I: Closed and compact subsets, Index sets in computable analysis, On approximate and algebraic computability over the real numbers, Index sets for \(\Pi^0_1\) classes, Approximation methods in inductive inference, Splitting theorems and the jump operator, Feasible graphs with standard universe, Learning via queries and oracles, Splitting theorems in recursion theory, The structure of the honest polynomial m-degrees, Recursion theory on the reals and continuous-time computation, An excursion to the Kolmogorov random strings, Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals, Learning recursive functions from approximations, Query languages for bags and aggregate functions, Noisy inference and oracles, The generalized universal law of generalization., Learning how to separate., Computability on subsets of metric spaces., Continuous-time computation with restricted integration capabilities, Robust learning aided by context, Quasi-minimal enumeration degrees and minimal Turing degrees, Structural measures for games and process control in the branch learning model, Classes bounded by incomplete sets, Modelization of deterministic rational relations, Effectively closed sets and graphs of computable real functions., Inductive inference with additional information., Approximation representations for \(\Delta_2\) reals, On the computational complexity of Longley's \(H\) functional, Some orbits for \({\mathcal E}\), Learning classes of approximations to non-recursive functions., The complexity of universal text-learners., Learning to win process-control games watching game-masters, Degrees of Dowd-type generic oracles, An analog characterization of the Grzegorczyk hierarchy, PAC learning of probability distributions over a discrete domain., Trees and learning, Generalized notions of mind change complexity, The dimensions of individual strings and sequences, Counting extensional differences in BC-learning, Decidability of string graphs, Interpreting true arithmetic in the theory of the r.e. truth table degrees, Some intuitions behind realizability semantics for constructive logic: Tableaux and Läuchli countermodels, On the time complexity of partial real functions, Results on memory-limited U-shaped learning, Ideals in computable rings, The complexity of stochastic sequences, On explicating the concept `the power of an arithmetical theory', The P\(\neq\) NP conjecture in the context of real and complex analysis, Small \(\Pi^{0}_{1}\) classes, Mind change efficient learning, Definability as hypercomputational effect, Analog computation beyond the Turing limit, The ibT degrees of computably enumerable sets are not dense, Non-primitive recursive decidability of products of modal logics with expanding domains, Sets without subsets of higher many-one degree, Hypersimplicity and semicomputability in the weak truth table degrees, Mass Problems and Randomness, Calibrating Randomness, On the structure of the Medvedev lattice, Randomness, lowness and degrees, How enumeration reductibility yields extended Harrington non-splitting, Recursion in Higher Types and Resource Bounded Turing Machines, Upper Semilattices in Many-One Degrees, EXACT APPROXIMATIONS OF OMEGA NUMBERS, Highly Undecidable Problems For Infinite Computations, Low upper bounds of ideals, Automorphisms of the truth-table degrees are fixed on a cone, Recursively enumerable m- and tt-degrees. I: The quantity of m-degrees, T-Degrees, Jump Classes, and Strong Reducibilities, Two Theorems on Truth Table Degrees