Reduktionen

Motivation

Intuitiv können wir uns vorstellen: Einige Mengen sind komplexer als andere. Die Elemente mancher Mengen zu finden ist schwerer als das bei anderen der Fall ist. Mit dem Konzept der Entscheidbarkeit und Semientscheidbarkeit haben wir bereits eine Kategorisierung geschaffen, die uns ermöglicht Sprachen¹ bezüglich ihrer »Schwierigkeit« einzuordnen. Nun gibt es viele Sprachen, die gar nicht semientscheidbar sind und sich deswegen untereinander nicht durch Entscheidbarkeitsbegriffe ordnen lassen. Das ist ganz schön doof.

Definition und Intuition

Um dieses Problem zu lösen führen wir Reduktionen ein. Wenn eine Menge auf eine andere reduzierbar ist, dann heißt das quasi, dass sie aus berechenbarkeitstheoretischer Sicht »leichter« ist als die andere.

Eine Menge $L$ ist für uns leichter als eine Menge $M$, wenn es eine total berechenbare Funktion gibt, die Elemente aus $L$ zu Elementen in $M$ abbildet und Nicht-Elemente von $L$ zu Nicht-Elementen von $M$. Wir schreiben $L \le M$. Wer mehr Formeln mag kann folgendes lesen:

\[L \le M \iff (\exists f \in \mathcal{R}: \forall x \in \mathbb{N}: x \in L \iff f(x) \in M)\]

Diese Definition mag zunächst willkürlich erscheinen. Ich möchte versuchen Dir eine Intuition dafür zu geben. Schauen wir uns zunächst die Definition von Mengengleichkeit an:

\[L = M \iff (\forall x \in \mathbb{N}: x \in L \iff x \in M)\]

Die sieht ja aus wie die andere nur ohne die Funktion $f$! Wir sehen außerdem, dass alle gleichen Mengen durch die Identitätsfunktion $\Delta: x \mapsto x$ auf einander reduziert werden. Die Reduzierbarkeit ist also ein schwächeres Kriterium als die Gleichheit.

Wem Ähnlichkeiten in Formeln nicht weiterhelfen,² der kann sich Reduktionen wie folgt vorstellen. Eine Menge $L$ ist reduzierbar (»leichter«) als eine Menge $M$, wenn wir, wenn wir eine Maschine haben, uns sagt, ob ein Element in $M$ ist, diese auch verwenden können, um raus zu finden, ob ein Element in $L$ ist.

Wenn $L \le M$ gibt es ja die totale Funktion $f$ die diese Reduktion vollzieht. Wenn wir wissen wollen, ob ein Element in $L$ ist, dann stecken wir es einfach in die Funktion und stecken das Ergebnis dann in die Orakel-Maschine für $M$. Aus der Antwort des Orakels können wir dann ableiten, ob das Element in $L$ war. Das klappt weil $f$ total berechenbar ist. Wir bekommen also immer ein Ergebnis.

Wie beweist man das?

Bei Beweisen, dass eine Reduktion geht, hilft uns oft das S-m-n-Theorem. Bei Beweisen, dass eine Reduktion nicht geht, hilft oft Kleenes Rekursionstheorem (KRT). Ich möchte das gerne an einem Beispiel illustrieren: Wir werden zeigen, dass es leichter ist zu entscheiden, ob ein Programm nie hält als zu entscheiden ob es unendlich oft hält. Sei $L = \{ e \mid \text{range}(\varphi_e) = \emptyset \}$ die Menge der Programme, die nie halten, und $UD = \{e \mid \text{domain}(\varphi_e) \text{ unendlich}\}$ die Menge der Programme, die unendlich oft halten. Also $L < UD$. (Wir schreiben $L < M$ wenn $L$ auf $M$ reduzierbar ist aber nicht umgekehrt.)

Hinrichtung

Wir zeigen zunächst $L \le UD$.

Laut S-m-n gibt es eine total berechenbare³ Funktion $f \in \mathcal{R}$ sodass für alle $t$:

$$\varphi_{f(e)}(t) = \begin{cases} 0 \text{, falls } \forall x \le t: U'(e, x, t) = 0 \\\\ \uparrow \text{ sonst} \end{cases}$$

gilt.

Wir argumentieren nun, dass dieses $f$ die reduziernde Funktition ist.

Nehmen wir an $e$ sei in $L$. Dann ist $\varphi_e$ überall undefiniert. Damit wird $U'$ immer 0 zurückgeben. Damit wird $\varphi_{f(e)}$ immer 0 zurückgeben. Damit ist $f(e)$ in $UD$.

Nehmen wir an $e$ sei nicht in $L$. Dann ist $\varphi_e$ irgendwo definiert. Dann gibt es $x$ und $t$, sodass $U'(e,x,t) \ne 0$. Dann ist $\varphi_{f(e)}$ für alle $t' \ge \max \{t,x\}$ undefiniert. Damit hat $\varphi_{f(e)}$ nur einen endlichen Definitionsbereich. Damit gilt $f(e) \not \in UD$.

Wir haben $e \in L$ die Aussage $f(e) \in UD$ und aus $e \not \in UD$ abgeleitet. Also haben wir $e \in L \iff f(e) \in UR$. Damit ist $f$ die gesuchte reduzierende Funktion.

Rückrichtung

Wir wollen $UD \nleq L$ zeigen. Wir führen einen Widerspruchsbeweis. Nehmen wir also $UD \le L$ an. Dann gibt es eine total berechenbare Funktion $f \in \mathcal{R}$, sodass $e \in UD \iff f(e) \in L$.

Sei für alle t: $$ \varphi_{g(e)}(t) = \begin{cases} \uparrow \text{, falls } \forall x \le t: U'(f(e), x, t) = 0 \\\\ t \text{ sonst.} \end{cases} $$

Dann gibt es nach KRT bzw. nach Rogers Fixpunktsatz ein $e$, sodass $\varphi_e = \varphi_{g(e)}$.

Nun müssen wir eine Fallunterscheidung durchführen.

Fall 1: Sei $e \in UD$. Dann gilt $f(e) \in L$. Dann wird für alle $x, t$ der Term $U'(f(e), x, t)$ immer zu 0. Damit gilt für alle $t$: $\varphi_{g(e)}(t) \uparrow$. Damit gilt $g(e) \not \in UD$. Damit folgt $e \not \in UD$. Das ist unser Widerspruch.

Fall 2: Sei $e \not \in UD$. Dann gilt $f(e) \not \in L$. Dann gibt es $x, t$, sodass $U'(f(e),x,t) \ne 0$. Dann wird für alle $t' \ge \max \{x,t\}$ das Programm $g(e)$ auf der Eingabe $t$ zu $t$. Damit hat $g(e)$ einen unendlichen Definitionsbereich. Damit gilt $g(e) \in UD$. Damit gilt $e \in UD$. Das ist unser Widerspruch.

Übungen

Das ist ja alles schön und gut, was ich hier aufgeschrieben habe, aber wie kommt man auf die Funktionen, die man für den Beweis braucht? Die habe ich ja einfach aus dem Hut gezaubert und dann gezeigt, dass sie richtig sind, aber wie ich auf sie gekommen bin habe ich nicht gezeigt. Das kann ich auch nicht wirklich. Ich glaube das einzige, was da hilft ist Übung, Übung und noch mal Übung. Deshalb hier ein paar Reduktionen.

Hinweis: Wir schreiben $L \equiv M$, wenn die Reduktion in beide Richtungen möglich ist.

$$ 2 \mathbb{N} \equiv 3 \mathbb{N} \\\\ Bijektiv \le Surjektiv \\\\ L < T \\\\ \{e \mid \exists x: \varphi_e(x) = 1 \} < \{e \mid \text{es gibt unendlich viele } x \text {, sodass } \varphi_e(x) = 1 \} $$

Es handelt sich hier ganz normal um Mengen. Im Formalismus der (total) berechenbaren Funktionen reden wir konkret über Mengen von natürlichen Zahlen. Der Begriff Sprache ist historisch gewachsen und kommt aus der Automatentheorie. Dort sind nicht Zahlen, sondern Zeichenketten aus einem Alphabet teil der Mengen. Diese Zeichenketten nennt man naheliegenderweise Wörter und Mengen von ihnen dann eben Sprachen. Das ist für unsere Zwecke aber komplett irrelevant.

Das kann ich gut nachvollziehen!

Die Berechenbarkeit folgt hier sofort daraus, dass $U'$ total berechenbar ist. In einer Klausur wäre es vielleicht gut, dazu nochmal einen Satz zu schreiben.