Twierdzenie Friedberga-Muchnika
W logice matematycznej twierdzenie Friedberga-Muchnika jest twierdzeniem o redukcjach Turinga , które zostało niezależnie udowodnione przez Alberta Muchnika i Richarda Friedberga w połowie lat pięćdziesiątych. Jest to bardziej ogólny pogląd na twierdzenie Kleene-Posta. Twierdzenie Kleene-Posta stwierdza, że istnieją nieporównywalne języki A i B poniżej K. Twierdzenie Friedberga-Muchnika stwierdza, że istnieją nieporównywalne, policzalne języki A i B. Nieporównywalne oznacza, że nie istnieje redukcja Turinga z A do B lub redukcja Turinga z B do A. Jest godna uwagi ze względu na zastosowanie priorytetowego podejścia do skończonych obrażeń.
Zobacz też
Kategorie: