Klasse von Mengen (Sprachen), für die es eine Turingmaschine gibt, die alle Elemente aufzählt oder äquivalent genau die Eingaben akzeptiert, die zur Menge gehören, indem sie auf ihnen hält und akzeptiert; bei Nicht-Mitgliedern kann die Maschine unendlich laufen.

Prinzip

Rekursiv aufzählbar (r.e.) bedeutet semi-entscheidbar: Es gibt ein effektives Verfahren, das für jedes Mitglied schließlich terminiert und Mitgliedschaft signalisiert, während Nicht-Mitgliedschaften nicht notwendigerweise zum Halten führen; Aufzählung und Erkennung sind gleichwertige Charakterisierungen.

Demonstration

Die Menge der Sätze, die von einem berechenbar axiomatisierten formalen System beweisbar sind, ist rekursiv aufzählbar: Eine Turingmaschine kann systematisch alle Beweise erzeugen und damit alle beweisbaren Sätze auflisten.

Fehlanwendung

Zu glauben, eine r.e.-Menge sei entscheidbar, weil ihre Elemente aufgelistet werden können; das Nicht-Halten bei einem Nicht-Mitglied als Beweis für Nicht-Zugehörigkeit fehlzuinterpretieren statt als bloßen Mangel an Evidenz.

Konsequenz

Die Zugehörigkeit zu einer r.e.-Menge kann bestätigt werden, indem man den Enumerierer/Recognizer laufen lässt bis zur Akzeptanz; das Ausbleiben einer Akzeptanz liefert ohne Zusatzinformationen jedoch keine definitive Negativauskunft.

Umkehrung

Ko-rekursiv aufzählbar: Mengen, deren Komplement r.e. ist; entscheidbar: Mengen, die sowohl r.e. als auch ko-r.e. sind.

Abgrenzung

Definiert relativ zu einer Standardkodierung und einem Modell (Turingmaschinen); schließt Oracle-Maschinen außer bei expliziter Nennung aus; Abgeschlossenheits-Eigenschaften beinhalten Vereinigung und Schnitt mit entscheidbaren Mengen, nicht jedoch im Allgemeinen das Komplement.

Semantische Spannung

Spannung zwischen r.e. und Entscheidbarkeit: Listbarkeit und Erkennbarkeit erfassen positive Information, während Entscheidbarkeit symmetrische Verfahren für positive und negative Fälle verlangt.

Synthese

Rekursiv aufzählbar fasst die Idee der positiven algorithmischen Erkennbarkeit zusammen: Mitglieder können effektiv erzeugt oder erkannt werden, während ihre Komplemente ohne zusätzliche Struktur algorithmisch unbestätigt bleiben können.