semi-entscheidbar
Wenn nur nur das Entscheidungsproblem nur Ja aber nicht Nein zurück geben kann.
co-semi-entscheidbar
Wenn nur nur das Entscheidungsproblem nur Nein aber nicht Ja zurück geben kann.
Satz
Ein Problem ist entscheidbar wenn es semi-entscheidbar und co-semi-entscheidbar ist.