TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
From MaRDI portal
Publication:3248015
DOI10.1073/pnas.43.2.236zbMath0080.24302OpenAlexW2015965037WikidataQ37616911 ScholiaQ37616911MaRDI QIDQ3248015
Publication date: 1957
Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1073/pnas.43.2.236
Related Items
An extension of the nondiamond theorem in classical and α-recursion theory, Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, Untersuchungen über die Struktur des Kleene-Postschen Halbverbandes der Grade der Rekursiven Unlösbarkeit, Bounding minimal degrees by computably enumerable degrees, The post correspondence problem, THE COLLAPSE OF THE HILBERT PROGRAM: A VARIATION ON THE GÖDELIAN THEME, The minimum of two regressive isols, On the Turing degrees of minimal index sets, The ∀∃-theory of ℛ(≤,∨,∧) is undecidable, The Typical Constructible Object, A theorem on minimal degrees, Collapsing degrees, Non-p-generic and strongly nonbranching degree, On the Degrees of Index Sets, Pseudo-complements and ordinal logics based on consistency statements, Metarecursively enumerable sets and their metadegrees, On a Problem of G. E. Sacks, A Simple Set Which is Not Effectively Simple, The bounded injury priority method and the learnability of unions of rectangles, A cornucopia of minimal degrees, Initial segments of the degrees of unsolvability Part II: minimal degrees, Intervals containing exactly one c.e. degree, Non-p-generic and strongly nonbranching degree, The Quotient Semilattice of the Recursively Enumerable Degrees Modulo the Cappable Degrees, Recursively enumerable sets which are uniform for finite extensions, A General Framework for Priority Arguments, Computational processes, observers and Turing incompleteness, The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility, Not every finite lattice is embeddable in the recursively enumerable degrees, On unstable and unoptimal prediction, Extending and interpreting Post's programme, On \(n\)-tardy sets, Measure-theoretic construction of incomparable hyperdegrees, As easy as $\mathbb {Q}$: Hilbert’s Tenth Problem for subrings of the rationals and number fields, The combinatorics of the splitting theorem, An easy priority-free proof of a theorem of Friedberg, Ramsey's theorem and recursion theory, A minimal degree less than 0’, There is no degree invariant half-jump, On the cutting edge of relativization: The resource bounded injury method, Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory, On Lachlan's major sub-degree problem, Combinatorial systems defined over one- and two-letter alphabets, Finite injury and Σ1-induction, The decision problem for recursively enumerable degrees, On the structures inside truth-table degrees, On Reducibility by Recursive Functions, Undecidability and 1-types in the recursively enumerable degrees, Incomparable prime ideals of recursively enumerable degrees, The distribution of the generic recursively enumerable degrees, Things that can be made into themselves, An explicit solution to Post's problem over the reals, Forcing and reducibilities, Is it harder to factor a polynomial or to find a root?, Lattice nonembeddings and intervals of the recursively enumerable degrees, Naturalness in Mathematics, Hierarchy of Computably Enumerable Degrees II, Recursive Enumerability and the Jump Operator, Classification of computably approximable real numbers, Recursively enumerable sets and degrees, Splitting and nonsplitting, II: A low2 c.e. degree above which 0′ is not splittable, Recursively enumerable degress and the conjugacy problem, On the reducibility of \(\Pi_ 1^ 1\) sets, Post's problem for ordinal register machines: an explicit approach, Turing oracle machines, online computing, and three displacements in computability theory, Call-by-value lambda calculus as a model of computation in Coq, Computing degrees of unsolvability, Extensions of embeddings below computably enumerable degrees, A pseudofundamental sequence that is not equivalent to any monotone sequence, Degree Structures: Local and Global Investigations, Representation of one-one degrees by decision problems for system functions, Coding a family of sets, Orbits of computably enumerable sets: Low sets can avoid an upper cone, Definability in the Recursively Enumerable Degrees, Resource bounded immunity and simplicity, A minimal pair of recursively enumerable degrees, European Summer Meeting of the Association for Symbolic Logic, Uppsala 1991, Metarecursively enumerable sets and admissible ordinals, Computational classification of cellular automata, La théorie des fonctions récursives et ses applications. (Exposé d'information générale), Metarecursive sets, Definable incompleteness and Friedberg splittings
