Indexmenge (Berechenbarkeitstheorie)

Eine Indexmenge (von engl. index set), auch semantische Menge[1] genannt, ist in der Berechenbarkeitstheorie eine Vereinigung von Gödelnummern berechenbarer Funktionen, die alle Indizes von Funktionen einer bestimmten Klasse enthalten.

Definition

Bearbeiten

Sei   eine effektive Nummerierung aller partiell berechenbarer Funktionen. Eine Menge   heiße semantisch falls gilt:

 

Falls also zwei Indizes die gleiche Funktion beschreiben, liegen entweder beide in   oder keiner von ihnen.

Dabei heißen zwei partielle Funktionen gleich, wenn sie an denselben Stellen (un)definiert sind und wann immer sie definiert sind, auch stets das gleiche Ergebnis liefern.

Charakterisierung

Bearbeiten

Es bezeichne   die Gesamtheit aller partiell berechenbaren Funktionen, zu jeder Funktionsklasse   gibt es genau eine Indexmenge, die die Nummern von Funktionen aus   enthält.

Umgekehrt lässt sich zu jeder semantischen Menge auch eine entsprechende eindeutige Klasse von Funktionen finden.

Das bedeutet, dass eine Indexmenge durch die semantischen Eigenschaften der Funktionen aus   vollständig bestimmt ist, daraus ergibt sich auch die Bezeichnung.

Beispiele

Bearbeiten

Die folgenden Mengen sind Indexmengen:

  • das  -Halteproblem  
  • die Menge   der Gödelnummern aller überall definierten berechenbaren Funktionen

Diese Mengen sind keine Indexmengen:

  • das (allgemeine) Halteproblem   mit  
Die Elemente dieser Menge definieren keine Funktionen. Es kann zum Beispiel   gelten.
  • das spezielle Halteproblem  
 , da im Allgemeinen  . Zum Beispiel für die Funktion, welche nur an der Stelle   definiert ist.

Eigenschaften

Bearbeiten
  • Jede nicht-leere Indexmenge besitzt eine unendliche rekursiv aufzählbare Teilmenge (und ist daher selbst unendlich), dies folgt aus dem Padding-Lemma.
  • Komplemente sowie beliebige Schnitte und Vereinigungen semantischer Mengen sind wieder semantisch.
    • Das System der Indexmengen bildet also sowohl eine σ-Algebra als auch eine Topologie auf  .
  • Indexmengen sind dann und nur dann entscheidbar, wenn sie trivial sind (d. h.   oder ganz  ), dies ist der Satz von Rice.
  • Eine Menge ist genau dann many-one-reduzierbar auf eine Indexmenge, wenn sie auf diese one-one-reduzierbar ist, alle semantische Mengen sind daher Zylinder.

Literatur

Bearbeiten
  • H. Rogers jr.: Theory of recursive functions and effective computability. 2nd ed., 3rd printing (1992), MIT Press, Cambridge MA, ISBN 0-262-68052-1

Einzelnachweise

Bearbeiten
  1. Bez. bspw. bei T. Kötzing: Berechenbarkeitstheorie. Vorlesung an der Friedrich-Schiller-Universität Jena im Sommersemester 2013.