En lógica matemática, el teorema de Friedberg-Muchnik es un teorema sobre las reducciones de Turing que fue demostrado independientemente por Albert Muchnik y Richard Friedberg a mediados de la década de 1950. [1] [2] Es una visión más general del teorema de Kleene-Post. El teorema de Kleene-Post establece que existen lenguajes A y B incomparables por debajo de K. El teorema de Friedberg-Muchnik establece que existen lenguajes A y B incomparables y computablemente enumerables . Incomparables significa que no existe una reducción de Turing de A a B o una reducción de Turing de B a A. Es notable por su uso del enfoque de la lesión finita prioritaria. [3]