ein von E. Post 1944 aufgestelltes Problem der Berechnungstheorie: Gibt es rekursiv aufzählbare Mengen, die weder entscheidbar (Entscheidbarkeit) sind, noch denselben Turing-Grad wie das Halteproblem haben?

Um das Problem zu lösen, wurden von Post die einfachen Mengen und die immunen Mengen eingeführt (was aber nicht zum Erfolg führte). Das Problem wurde dann 1952 unabhängig von Friedberg und Muchnik im positiven Sinne gelöst. Der Beweis gelang mit einer neuen Beweistechnik, der Prioritätsmethode.