Friedberg–Muchnik theorem explained
In mathematical logic, the Friedberg–Muchnik theorem is a theorem about Turing reductions that was proven independently by Albert Muchnik and Richard Friedberg in the middle of the 1950s. It is a more general view of the Kleene–Post theorem. The Kleene–Post theorem states that there exist incomparable languages A and B below K. The Friedberg–Muchnik theorem states that there exist incomparable, computably enumerable languages A and B. Incomparable meaning that there does not exist a Turing reduction from A to B or a Turing reduction from B to A. It is notable for its use of the priority finite injury approach.
See also
References
- Friedberg . Richard M. . Richard M. Friedberg . 10.1073/pnas.43.2.236 . . 84474 . 236–238 . Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944) . 43 . 1957 . 2 . free . 528418.
- Book: Kozen
, Dexter
. Dexter Kozen . 10.1007/1-84628-477-5_48 . London . 253–256 . Springer . Theory of Computation . Lecture 38: The Friedberg–Muchnik Theorem . 2006.
- Mučnik . Albert Abramovich . Albert Muchnik . . 0081859 . 194–197 . On the unsolvability of the problem of reducibility in the theory of algorithms . 108 . 1956.
