Degrees of Unsolvability. (AM-55)
From MaRDI portal
Publication:5519129
DOI10.1515/9781400881840zbMath0143.25302OpenAlexW2565632284MaRDI QIDQ5519129
Publication date: 1963
Full work available at URL: https://doi.org/10.1515/9781400881840
Related Items
Reductions among polynomial isomorphism types, An extension of the nondiamond theorem in classical and α-recursion theory, Computational depth and reducibility, An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees, Large Turing independent sets, On the Turing degrees of minimal index sets, Measure theory and weak König's lemma, Program Size Complexity of Correction Grammars in the Ershov Hierarchy, Bounded truth table does not reduce the one-query tautologies to a random oracle, DEGREES OF RANDOMIZED COMPUTABILITY, IN MEMORIAM: GERALD E. SACKS, 1933–2019, Cupping with random sets, Minimal complements for degrees below 0′, A theorem on minimal degrees, Index sets and presentations of complexity classes, On the Degrees of Index Sets, Deficiency Sets and Bounded Information Reducibilities, On a Problem of G. E. Sacks, Separating families and order dimension of Turing degrees, Initial segments of the degrees of unsolvability Part II: minimal degrees, PERMUTATIONS OF THE INTEGERS INDUCE ONLY THE TRIVIAL AUTOMORPHISM OF THE TURING DEGREES, Some contrasts between degrees and the arithmetical hierarchy, Recursively enumerable sets which are uniform for finite extensions, A General Framework for Priority Arguments, DEEP CLASSES, Continuous randomness via transformations of 2-random sequences, Mass problems and density, The enumeration degrees: Local and global structural interactions, Randomness, lowness and degrees, Sets of real numbers closed under Turing equivalence: applications to fields, orders and automorphisms, Some theorems on R-maximal sets and major subsets of recursively enumerable sets, On initial segment complexity and degrees of randomness, Elementary Differences Between the Isols and the Co-Simple Isols, \(A\)-computable graphs, On the Degrees of Index Sets. II, Isomorphism Types in Wreath Products and Effective Embeddings of Periodic Groups, Hierarchies of Effective Descriptive Set Theory, Martin's axiom and embeddings of upper semi-lattices into the Turing degrees, Some elementary degree-theoretic reasons why structures need similarity types, Permutations of the Integers Induce only the Trivial Automorphism of the Turing Degrees, A measure-theoretic proof of Turing incomparability, Semirecursive Sets and Positive Reducibility, Minimal Covers and Arithmetical Sets, Measure-Theoretic Uniformity in Recursion Theory and Set Theory, Derandomization in game-theoretic probability, Higher-Order Indecomposable Isols, There is no degree invariant half-jump, A minimal degree not realizing least possible jump, Bounded enumeration reducibility and its degree structure, Branching Degrees above low Degrees, The Information Content of Typical Reals, Cofinal maximal chains in the Turing degrees, Jump inversions inside effectively closed sets and applications to randomness, Does truth-table of linear norm reduce the one-query tautologies to a random oracle?, The decision problem for recursively enumerable degrees, Trivial Reals, Two existence theorems for computable numerations, WCS-analysis of the context-sensitive, On degrees of recursively enumerable sets, Augmented loop languages and classes of computable functions, Über die Reduzierbarkeit berechenbarer Numerierungen, Additive structure in uncountable models for a fixed completion of P, An operator embedding theorem for complexity classes of recursive functions, Polynomial and abstract subrecursive classes, Lattice initial segments of the hyperdegrees, The importance of Π10 classes in effective randomness, Maximal chains in the Turing degrees, Goodness in the enumeration and singleton degrees, The Role of True Finiteness in the Admissible Recursively Enumerable Degrees, Mass Problems and Randomness, A note on the consistency operator, Unnamed Item, Model-theoretic properties of Turing degrees in the Ershov difference hierarchy, Recursively enumerable sets and degrees, Measure-theoretic applications of higher Demuth’s Theorem, Jump operator and Yates Degrees, Intuitionistically provable recursive well-orderings, FINDING THE LIMIT OF INCOMPLETENESS I, Complete sets and closeness to complexity classes, Measure theory aspects of locally countable orderings, Lowness and nullsets, Degree Structures: Local and Global Investigations, Calibrating Randomness, The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable, Measure and cupping in the Turing degrees, Measures and their random reals, On the existence of a strong minimal pair, Lowness properties and randomness, Automorphisms of the lattice of recursively enumerable sets, A minimal pair of recursively enumerable degrees, Effective randomness for continuous measures, Random reals as measures of natural open sets, Probabilistic computability and choice, Sets of Formulas Valid in Finite Structures, Relativization of the Theory of Computational Complexity, Arithmetic transfinite induction and recursive well-orderings, Independence Results on the Global Structure of the Turing Degrees, Determining Automorphisms of the Recursively Enumerable Sets
