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
In Branch
Source Friedberg-Muchnik theorem, Wikipedia
Proved By
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
Proved By: Albert Muchnik, Lead sentence, attribution
proven independently by Albert Muchnik and Richard Friedberg
In Group: Computability and Complexity Theory, Lead section
logic, the Friedberg-Muchnik theorem is a theorem about Turing reductions that was proven independently by Albert
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.