Eigenschaft von Mengen.

Eine Menge A ist semi-entscheidbar, wenn sie Definitionsbereich einer berechenbaren Funktion ist. Das bedeutet, daß es einen Algorithmus gibt, der genau auf den Eingaben aus A stoppt. Es gilt der folgende Satz:

Eine Menge ist genau dann semi-entscheidbar, wenn sie rekursiv aufzählbar ist.