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

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) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28) General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to mathematical logic and foundations (03-00) Hierarchies of computability and definability (03D55) Computability and recursion theory (03Dxx)

Related Items

Learning Families of Closed Sets in Matroids, Maximal contiguous degrees, The dimensions of individual strings and sequences, Counting extensional differences in BC-learning, Decidability of string graphs, Degrees of Transducibility, Effectivity questions for Kleene's recursion theorem, Initial segment complexities of randomness notions, Partial combinatory algebra and generalized numberings, Results on memory-limited U-shaped learning, Interpreting true arithmetic in the theory of the r.e. truth table degrees, Covering the Recursive Sets, Effective genericity and differentiability, R.J. THOMPSON’S GROUPSFANDTARE BI-INTERPRETABLE WITH THE RING OF THE INTEGERS, Where join preservation fails in the bounded Turing degrees of c.e. sets, Some intuitions behind realizability semantics for constructive logic: Tableaux and Läuchli countermodels, Transducer degrees: atoms, infima and suprema, On the Hardness of Almost–Sure Termination, Recursively enumerable m- and tt-degrees. I: The quantity of m-degrees, The theory of the recursively enumerable weak truth-table degrees is undecidable, 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, Closed left-r.e. sets, Inductive inference and computable numberings, Weakly Represented Families in Reverse Mathematics, Strength and Weakness in Computable Structure Theory, There Are No Maximal d.c.e. wtt-degrees, On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets, Absolutely no free lunches!, THE COMPLEXITY OF INDEX SETS OF CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS, About the Domino Problem for Subshifts on Groups, Simple structures with complex symmetry, Unnamed Item, The structure of computably enumerable preorder relations, Computable irrational numbers with representations of surprising complexity, Avoiding uniformity in the $\Delta_2^0$ enumeration degrees, The $\omega$-Turing degrees, Degrees of Infinite Words, Polynomials and Atoms, Ideals in computable rings, On the time complexity of partial real functions, Learnability and positive equivalence relations, Truth-table Schnorr randomness and truth-table reducible randomness, Least Upper Bounds on the Size of Church-Rosser Diagrams in Term Rewriting and λ-Calculus, GENERALIZATIONS OF THE RECURSION THEOREM, The complexity of stochastic sequences, Schnorr trivial sets and truth-table reducibility, Empiricism, probability, and knowledge of arithmetic: a preliminary defense, On 0′-computable reals, Things that can be made into themselves, Algorithmic randomness and Fourier analysis, Complexity of Blowup Problems, Realizability with a local operator of A. M. Pitts, Index Sets and Universal Numberings, On explicating the concept `the power of an arithmetical theory', Medvedev Degrees of Generalized R.E. separating Classes, Revising Type-2 Computation and Degrees of Discontinuity, Selection by Recursively Enumerable Sets, The P$\neq$ NP conjecture in the context of real and complex analysis, Small $\Pi^{0}_{1}$ classes, Mind change efficient learning, The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata, Definability as hypercomputational effect, Analog computation beyond the Turing limit, The ibT degrees of computably enumerable sets are not dense, Properly ?2 minimal degrees and 0? complementation, Non-primitive recursive decidability of products of modal logics with expanding domains, A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle, Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness, Searching for shortest and least programs, Descriptive complexity of computable sequences revisited, Mass Problems and Randomness, Highly Undecidable Problems For Infinite Computations, On cototality and the skip operator in the enumeration degrees, Difference randomness, Low upper bounds of ideals, Automorphisms of the truth-table degrees are fixed on a cone, Normalized information distance and the oscillation hierarchy, Degrees of Infinite Words, Polynomials and Atoms, T-Degrees, Jump Classes, and Strong Reducibilities, Sub-computabilities, On $1$-degrees inside $m$-degrees, Fixed point theorems for precomplete numberings, Locally finite ω-languages and effective analytic sets have the same topological complexity, Two Theorems on Truth Table Degrees, Mass Problems and Measure-Theoretic Regularity, Calibrating Randomness, DECIDABILITY, UNDECIDABILITY, AND GÖDEL'S INCOMPLETENESS IN RELATIVITY THEORIES, Sets without subsets of higher many-one degree, Hypersimplicity and semicomputability in the weak truth table degrees, Unified characterizations of lowness properties via Kolmogorov complexity, Unpredictability of complex (pure) strategies, Enumerations of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msubsup><mml:mi mathvariant="normal">Π</mml:mi><mml:mn>1</mml:mn><mml:mn>0</mml:mn></mml:msubsup></mml:math> Classes: Acceptability and Decidable Classes, Random reals as measures of natural open sets, $Q$-reducibility and $m$-reducibility on computably enumerable sets, Towards a map for incremental learning in the limit from positive and negative information, Learning languages in the limit from positive information with finitely many memory changes, The Medvedev lattice of computably closed sets, An analog characterization of the Grzegorczyk hierarchy, The jump operation for structure degrees, PAC learning of probability distributions over a discrete domain., Trees and learning, Generalized notions of mind change complexity, The structure of the honest polynomial m-degrees, 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, Recursion theory on the reals and continuous-time computation, Strong enumeration reducibilities, Infinite games specified by 2-tape automata, An excursion to the Kolmogorov random strings, Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals, Strongly non-U-shaped language learning results by general techniques, Computation with perturbed dynamical systems, Learning recursive functions from approximations, Classes with easily learnable subclasses, Undefinability of truth and nonstandard models, Query languages for bags and aggregate functions, Extended regular expressions: succinctness and decidability, An improved zero-one law for algorithmically random sequences, Natural factors of the Muchnik lattice capturing IPC, Noisy inference and oracles, Computational processes, observers and Turing incompleteness, Streamlined subrecursive degree theory, Jumps of computably enumerable equivalence relations, On the uniform computational content of computability theory, The generalized universal law of generalization., Closed choice and a uniform low basis theorem, Extending and interpreting Post's programme, The effective theory of Borel equivalence relations, Games with 1-backtracking, Analogues of quantum complementarity in the theory of automata, Proof mining and effective bounds in differential polynomial rings, Recursion-theoretic ranking and compression, Learning how to separate., Learning recursive functions: A survey, Learning indexed families of recursive languages from positive data: A survey, Set systems: order types, continuous nondeterministic deformations, and quasi-orders, Computability on subsets of metric spaces., Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability, Derandomization in game-theoretic probability, Continuous-time computation with restricted integration capabilities, On the hardness of analyzing probabilistic programs, $S_{k,\text{exp}}$ does not prove $\text{NP} = \text{co-NP}$ uniformly, $\mu$-limit sets of cellular automata from a computational complexity perspective, Myhill's work in recursion theory, Fine hierarchies and m-reducibilities in theoretical computer science, Equational theories for inductive types, On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data, Algorithmic identification of probabilities is hard, Irreducible, singular, and contiguous degrees, Epistemic entrenchment and arithmetical hierarchy, Consistent and coherent learning with $\delta $-delay, $\Pi_1^0 $ classes, LR degrees and Turing degrees, Random numbers as probabilities of machine behavior, Nondiamond theorems for polynomial time reducibility, Non-determinism in Gödel's system $T$, Approximation representations for $\Delta_2$ reals, Weakly semirecursive sets and r.e. orderings, Real recursive functions and their hierarchy, Decision problems for Turing machines, Computability on reals, infinite limits and differential equations, Equivalences between learning of data and probability distributions, and their applications, Resource restricted computability theoretic learning: Illustrative topics and problems, Complexity-theoretic hierarchies induced by fragments of Gödel's $T$, A new conceptual framework for analog computation, Investigations on measure-one identification of classes of languages, Determining and stationary sets for some classes of partial recursive functions, Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, The high/low hierarchy in the local structure of the $\omega$-enumeration degrees, Robust learning aided by context, Quasi-minimal enumeration degrees and minimal Turing degrees, On the computational complexity of Longley's $H$ functional, Computations via Newtonian and relativistic kinematic systems, Structural measures for games and process control in the branch learning model, 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, The noneffectivity of Arslanov's completeness criterion and related theorems, 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, 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, Splitting theorems in recursion theory, Classes bounded by incomplete sets, Modelization of deterministic rational relations, Effectively closed sets and graphs of computable real functions., Inductive inference with additional information., 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, Characterizing time computational complexity classes with polynomial differential equations, Turing degrees of nonabelian groups, THE ∀∃ THEORY OF PEANO Σ₁ SENTENCES, Minimal complements for degrees below 0′, Members of thin Π₁⁰ classes and generic degrees, A STRUCTURAL DICHOTOMY IN THE ENUMERATION DEGREES, Computability and Computational Complexity of the Evolution of Nonlinear Dynamical Systems, r‐Maximal sets and Q1,N‐reducibility, Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines, Unnamed Item, Rogers semilattices of limitwise monotonic numberings, COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR, De groot duality for represented spaces, Elementarily traceable irrational numbers, On the complexity of learning programs, Embeddings between partial combinatory algebras, Game characterizations and lower cones in the Weihrauch degrees, The minimal complementation property above 0′, Iteration, inequalities, and differentiability in analog computers, REALIZABILITY SEMANTICS FOR QUANTIFIED MODAL LOGIC: GENERALIZING FLAGG’S 1985 CONSTRUCTION, 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, Schnorr triviality and genericity, Vacillatory and BC learning on noisy data, Learnability and positive equivalence relations, On the hierarchies of Δ₂⁰-real numbers, 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, RANK AND RANDOMNESS, Degrees of sets having no subsets of higher m- and t t-degree, Point Degree Spectra of Represented Spaces, Computability of Subsets of Metric Spaces, EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS