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.[1][2] 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, computabley 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.[3]

See also

References
  1. "Two Recursively Enumerable Sets Not Recursive in Each Other", Richard Friedberg, Proc. Nat. Acad. Sci. vol. 43, p. 236 (1957) [communicated by K. Gödel]. doi:10.1073/pnas.43.2.236
    • A. A. Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms. (in Russian) Doklady Akademii Nauk SSSR (N.S.), vol. 108 (1956), pp. 194–197
  3. https://link.springer.com/content/pdf/10.1007/1-84628-477-5_48.pdf



This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.