Friedberg–Muchnik theorem

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

• Post's problem

References

• Friedberg, Richard M. (1957). Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944). Proceedings of the National Academy of Sciences of the United States of America. Vol. 43, no. 2. pp. 236–238. doi:10.1073/pnas.43.2.236. MR 0084474. PMC 528418.
• Kozen, Dexter (2006). Lecture 38: The Friedberg–Muchnik Theorem. Theory of Computation. London: Springer. pp. 253–256. doi:10.1007/1-84628-477-5_48.
• Mučnik, Albert Abramovich (1956). "On the unsolvability of the problem of reducibility in the theory of algorithms". Doklady Akademii Nauk SSSR. 108: 194–197. MR 0081859.