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)". 43. 236–238. doi:10.1073/pnas.43.2.236. 
• 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.