Friedberg–Muchniks sats
Inom matematisk logik är Friedberg-Muchnik-satsen ett teorem om Turing-reduktioner som bevisades oberoende av Albert Muchnik och Richard Friedberg i mitten av 1950-talet. Det är en mer allmän syn på Kleene-Post-satsen. Kleene–Post-satsen anger att det finns ojämförliga språk A och B under K. Friedberg-Muchnik-satsen anger att det finns ojämförliga, beräkningsbart uppräknade språk A och B. Ojämförlig betyder att det inte finns en Turing-reduktion från A till B eller en Turing-reduktion från B till A. Det är anmärkningsvärt för sin användning av den prioriterade ändliga skadan.
Se även
Kategorier: