The Friedberg-Muchnik Theorem, proved independently by Richard Friedberg and Albert Muchnik in the mid-1950s, establishes the existence of two computably enumerable sets whose Turing degrees are incomparable, meaning neither set can be computed using an oracle for the other. It strengthened the earlier Kleene-Post theorem, which had only produced incomparable degrees below the halting problem, and its proof introduced the finite injury priority method, a technique for satisfying infinitely many competing requirements that has become one of the central tools of computability theory.
Facts
StatementThere exist two computably enumerable subsets A and B of the natural numbers such that neither is Turing reducible to the other, giving two incomparable computably enumerable Turing degrees. 1 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Friedberg-Muchnik theorem, Wikipedia
Sources
1. Friedberg-Muchnik theorem, Wikipedia
Formal statement
There exists two computationally enumerable subsets A, B ⊂ ℕ, such that A ≮T B, B ≮T A.
- In Branch: Logic and Foundations, Lead sentence
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.