scientific article; zbMATH DE number 1955470

Publication date: 28 July 2003

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

textbook computability theory recursion theory enumeration degree Turing degree

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Computability and recursion theory (03Dxx)

Related Items

A new perspective on intermediate algorithms via the Riemann-Hilbert correspondence, Orbits of maximal vector spaces, A note on the enumeration degrees of 1-generic sets, Kripke Models Built from Models of Arithmetic, Parametric Church's thesis: synthetic computability without choice, The deluge of spurious correlations in big data, A Note on the Computable Categoricity of $$\ell ^p$$ ℓ p Spaces, Members of thin Π₁⁰ classes and generic degrees, Bounded low and high sets, Partial word and equality problems and Banach densities, The Hilbert's-tenth-problem operator, Computational processes, observers and Turing incompleteness, Total Degrees and Nonsplitting Properties of $\Sigma_2^0$ Enumeration Degrees, The Non-isolating Degrees Are Upwards Dense in the Computably Enumerable Degrees, On the complexity of the theory of a computably presented metric structure, Randomness, lowness and degrees, How enumeration reductibility yields extended Harrington non-splitting, Badness and jump inversion in the enumeration degrees, Cupping Classes of $\Sigma^0_2$ Enumeration Degrees, On the uniform computational content of computability theory, Effective weak and vague convergence of measures on the real line, On projections of free semialgebraic sets, Splitting and nonsplitting in the $\Sigma_2^0$ enumeration degrees, Tarski-type problems for free associative algebras, Extending and interpreting Post's programme, Algorithmically finite groups., Warsaw discs and semicomputability, Groups, graphs, languages, automata, games and second-order monadic logic, What does a group algebra of a free group ``know about the group?, Analytic computable structure theory and $L^p$ spaces, On a question of Slaman and Groszek, Derandomization in game-theoretic probability, Avoiding uniformity in the $\Delta_2^0$ enumeration degrees, Branching in the ${\Sigma^0_2}$-enumeration degrees: a new perspective, Incomputability Emergent, and Higher Type Computation, On Lachlan's major sub-degree problem, Measuring complexities of classes of structures, The power of backtracking and the confinement of length, Computable neighbourhoods of points in semicomputable manifolds, The fixed point problem of a simple reversible language, Physical Computational Complexity and First-order Logic, The relationship between word complexity and computational complexity in subshifts, Empiricism, probability, and knowledge of arithmetic: a preliminary defense, Algorithmic randomness and Fourier analysis, Bi-interpretability of some monoids with the arithmetic and applications, The minimal e-degree problem in fragments of Peano arithmetic, The limitations of cupping in the local structure of the enumeration degrees, Definability as hypercomputational effect, Forcing in Proof Theory, On the degree spectrum of a $\Pi ^0_1$ class, Computably enumerable Turing degrees and the meet property, Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness, Naturalness in Mathematics, On the jump classes of noncuppable enumeration degrees, Classical, quantum and biological randomness as relative unpredictability, Incompleteness, Undecidability and Automated Proofs, The high/low hierarchy in the local structure of the $\omega$-enumeration degrees, Empty intervals in the enumeration degrees, A non-splitting theorem in the enumeration degrees, Limits on jump inversion for strong reducibilities, Emergence as a computability-theoretic phenomenon, Uncomputability and undecidability in economic theory, Turing degrees in Polish spaces and decomposability of Borel functions, The strength of the rainbow Ramsey Theorem, Measure and cupping in the Turing degrees, On the Computable Theory of Bounded Analytic Functions, Computable Complex Analysis, Effective notions of weak convergence of measures on the real line, Lawvere-Tierney topologies for computability theorists