Indexmenge (Berechenbarkeitstheorie)

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

Definition

Sei $\lbrace \varphi _{n}\rbrace _{n\in \mathbb {N} }$ eine effektive Nummerierung aller partiell berechenbarer Funktionen. Eine Menge $A\subseteq \mathbb {N}$ heiße semantisch falls gilt:

$\forall n;m\in \mathbb {N} \colon \varphi _{n}=\varphi _{m}\land n\in A\Rightarrow m\in A$

Falls also zwei Indizes die gleiche Funktion beschreiben, liegen entweder beide in $A$ 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

Es bezeichne ${\mathcal {P}}$ die Gesamtheit aller partiell berechenbaren Funktionen, zu jeder Funktionsklasse ${\mathcal {S}}\subseteq {\mathcal {P}}$ gibt es genau eine Indexmenge, die die Nummern von Funktionen aus ${\mathcal {S}}$ 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 ${\mathcal {S}}$ vollständig bestimmt ist, daraus ergibt sich auch die Bezeichnung.

Beispiele

Die folgenden Mengen sind Indexmengen:

• das $\varepsilon$-Halteproblem $H_{0}=\{n\mid \varphi _{n}(0)\downarrow \}$
• die Menge $TOTAL=\{n\mid \forall k\colon \varphi _{n}(k)\downarrow \}$ der Gödelnummern aller überall definierten berechenbaren Funktionen

Diese Mengen sind keine Indexmengen:

• das (allgemeine) Halteproblem $H=\{\langle n,k\rangle \mid \varphi _{n}(k)\downarrow \}$ mit $\langle \cdot ~,\cdot \rangle :\mathbb {N} ^{2}\rightarrow \mathbb {N}$

Die Elemente dieser Menge definieren keine Funktionen. Es kann zum Beispiel $\varphi _{\langle n,k\rangle }\uparrow$ gelten.

• das spezielle Halteproblem $K=\{n\mid \varphi _{n}(n)\downarrow \}$

$\varphi _{n}=\varphi _{n'}\nRightarrow n,n'\in K$, da im Allgemeinen $\varphi _{n}(n)\downarrow \nLeftrightarrow \varphi _{n}(n')\downarrow$. Zum Beispiel für die Funktion, welche nur an der Stelle $n$ definiert ist.

Eigenschaften

• 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 $\mathbb {N}$.
• Indexmengen sind dann und nur dann entscheidbar, wenn sie trivial sind (d. h. $\emptyset$ oder ganz $\mathbb {N}$), 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

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