Klasse von Mengen, deren Komplement rekursiv aufzählbar ist; äquivalent: Probleme, für die Nicht-Zugehörigkeit semi-entscheidbar ist durch ein Verfahren, das bei negativen Instanzen hält.

Prinzip

Eine Menge ist ko-rekursiv aufzählbar (ko-r.e.), wenn es eine Turingmaschine gibt, die genau die Eingaben akzeptiert, die nicht zur Menge gehören; ko-r.e. erfasst die Semi-Entscheidbarkeit der Falschheit statt der Wahrheit.

Demonstration

Ist die Halte-Menge K rekursiv aufzählbar, so ist ihr Komplement — die Kodierungen von Programm-Eingabepaaren, die nicht halten — ko-rekursiv aufzählbar; Zugehörigkeit zum Komplement kann bestätigt werden, falls ein Erkenner für Nicht-Halten existiert (z. B. über Aufzählung von Nicht-Halt-Beweisen in beschränkten Kontexten).

Fehlanwendung

Anzunehmen, ko-r.e. impliziere Entscheidbarkeit, oder ein Verfahren, das manchmal Mitgliedschaft widerlegt, als einheitliche Widerlegungsmethode für alle Eingaben zu behandeln, ohne Überprüfung der Vollständigkeit.

Konsequenz

Für eine ko-r.e.-Menge kann man Nicht-Zugehörigkeit algorithmisch zertifizieren, indem man den Ko-Erkenner bis zur Akzeptanz laufen lässt; wie bei r.e.-Mengen kann es jedoch sein, dass ohne zusätzliche Struktur keine allgemeine effektive Widerlegung existiert.

Umkehrung

Rekursiv aufzählbar: Mengen, deren Mitgliedschaft semi-entscheidbar ist; entscheidbar: Mengen, die sowohl r.e. als auch ko-r.e. sind; Nicht-ko-r.e.: Komplemente von Mengen, denen jeglicher Aufzähler für Nicht-Mitglieder fehlt.

Abgrenzung

Definiert relativ zu Standardmodellen; die Klasse ist im Allgemeinen nicht abgeschlossen unter Komplement (das Komplement einer ko-r.e.-Menge ist r.e.), viele Mengen sind weder r.e. noch ko-r.e.; Orakelklassen sind ausgeschlossen, sofern nicht angegeben.

Semantische Spannung

Spannung besteht zwischen r.e. und ko-r.e.: Die Asymmetrie, ob positive oder negative Fälle halb-entscheidbar sind, führt zu unterschiedlichen algorithmischen Eigenschaften und Abschlusseigenschaften.

Synthese

Ko-rekursiv aufzählbar formt die algorithmische Erkennbarkeit von Nicht-Zugehörigkeit: Während die Mitgliedschaft unzugänglich bleiben kann, lässt sich Nicht-Zugehörigkeit durch ein haltendes Verfahren zertifizieren, wenn die Menge in dieser Klasse liegt.