Update: Kleine Korrektur nach Einwand von Phil in den Kommentaren.

Update: es hat sich ein Fehler eingeschlichen bei der Definition der Dualnotation. Sollte nun behoben sein. Danke Thomas.

Update: das ist nun der letzte Beitrag, der auf die Lernziele gemünzt wird. Irgendwie verlässt mich immer kurz vor Schluss die Lust mich durch die quälenden Definitionen zu... ähm... nunja... quälen.

Da ich im Moment mit KE4 von 1658 (TIB) nicht weiterkomme, bin ich mal der Bitte von Marco nachgekommen und habe die Zusammenfassung von KE7/1657 fertig gemacht. Hoffentlich hilft sie euch etwas.

Lernziel 3

Erklärung der Reduzierbarkeit und Äquivalenz von Nummerierungen

Die Reduzierbarkeit haben wir bereits im Beitrag zu KE6 gehabt. Ähnlich verhält es sich hier.

Wir machen es uns am liebsten leicht: wozu die Berechenbarkeitsmodelle aller Nummerierungen durchgehen wenn wir sie aufeinander reduzieren und so ihre Äquivalenz nachweisen können? So können wir uns einfach, wie im Falle der Standardnummerierung $\varphi$, unter bestimmten Bedingungen auf eine Nummerierung festlegen wenn wir zeigen können, dass die anderen Nummerierungen zu dieser äquivalent sind oder auf unsere reduziert werden können.

Da jede Menge $M$ mit mind. zwei Elementen sehr viele Nummerierungen hat, die Berechenbarkeitskonzepte (siehe vorheriger Beitrag) auf diesen Mengen festlegen, brauchen wir was um diese zu vergleichen. Das Konzept der Reduzierbarkeit erscheint noch etwas willkürlich, wir werden es aber im Teil B der theoretischen Informatik im Rahmen der Komplexitätstheorie wieder treffen und anwenden. Also am besten nicht überspringen.

Beispiel: $id_{\mathbb{N}}\leq\nu_{\mathbb{Z}}$

Wir wollen hier zeigen, dass wir $id_{\mathbb{N}}$ auf $\nu_{\mathbb{Z}}$ reduzieren können, d.h. wir brauchen eine Funktion die als Definitionsbereich $id_{\mathbb{N}}$ und als Bildbereich $\nu_{\mathbb{Z}}$ hat. Dazu müssen wir nur eine einstellige und totale  Funktionen $f$ aus $R^{(1)}$ wählen, die das für uns erledigt. Selbstverständlich muss sie auch berechenbar sein.

Wir rekapitulieren nochmal die zwei Nummerierungen :

$id_{\mathbb{N}}: \mathbb{N}\Rightarrow\mathbb{N},id_{\mathbb{N}}(k) = k$ für alle $k\in\mathbb{N}$

Identitätsfunktion also. Wir bilden eine Zahl aus $\mathbb{N}$ auf sich selbst ab, z.B. $id_{\mathbb{N}}(5)=5$. That's it. Wie man sieht ist die Nummerierung total (für jedes Element aus der Definitionsmenge haben wir ein  Element aus der Bildmenge) und bijektiv (das Bild ist sogar eindeutig, d.h. wir können auch eine Inverse draus basteln).

$\nu_{\mathbb{Z}}: \mathbb{N}\Rightarrow\mathbb{Z},\nu_{\mathbb{Z}}<i,j> = i-j$ für alle $i,j\in\mathbb{N}$

Wir bilden eine Zahl aus $\mathbb{N}$ auf eine Zahl auf $\mathbb{Z}$ ab, z.B. $\nu_{\mathbb{Z}}(500)=<27,4>=27-4=23$ (falls bei euch nun wieder Fragezeichen über euren Köpfen auftauchen, erinnert euch bitte an die Inverse der Cantorschen Tupelfunktion).

Wie man sieht ist die Nummerierung auch total (für jedes Element aus der Definitionsmenge haben wir ein  Element aus der Bildmenge), aber nicht bijektiv, wie man leicht am folgenden Beispiel sieht:

$\nu_{\mathbb{Z}}(277)=<24,1>=24-1=23$

$\nu_{\mathbb{Z}}(500)=<27,4>=27-4=23$

Damit würden die Zahlen $500$ und $277$ aus dem Definitionsbereich $id_{\mathbb{N}}$ auf die gleiche Zahl im Bildbereich $\nu_\mathbb{Z}$ unserer "Übersetzungsfunktion" abgebildet, eine Inverse können wir so zwar nicht angeben, ist aber nicht schlimm. Die brauchen wir hier ja auch nicht.

Besorgen wir uns also eine Funktion $f: id_\mathbb{N}\Rightarrow\nu_{\mathbb{Z}}$.

Es gilt also $Def(f)=id_{\mathbb{N}}$ und $Bild(f)=\nu_{\mathbb{Z}}$: zu jedem Element der einen Nummerierung gibt es ein Element aus der anderen Nummerierung. Eine Möglichkeit für die Übersetzungsfunktion $f$ wäre z.B. $f(i) = <i,0>$. Versuchen wir es doch einfach mal:

$id_{\mathbb{N}}(500) = 500$

$f(500) = <500,0> = 124251$

$\nu_{\mathbb{Z}}(124251) =<500,0>=500-0=500$

Sieht gut aus. Damit ist $id_{\mathbb{N}}\leq\nu_{\mathbb{Z}}$. In Worten: $id_{\mathbb{N}}$ ist reduzierbar auf $\nu_{\mathbb{Z}}$.

Diese Nummerierungen haben einige wichtige Eigenschaften, die wir hier festhalten wollen:

$(\nu_1\leq\nu_2$ und $\nu_2\leq\nu_3)\Rightarrow\nu_1\leq\nu_3$

$(\nu_1\equiv\nu_2$ und $\nu_2\equiv\nu_3)\Rightarrow\nu_1\equiv\nu_3$

Die beiden Eigenschaften der Reduzierbarkeit und Äquivalenz der Nummerierungen basieren auf der Transitivität. Also nichts neues.

Was vielleicht noch erwähnenswert ist: Bei der Übersetzung durch die totale Übersetzungsfunktion $f$ gehen Berechenbarkeitsinformationen verloren geht. Damit ist die überführte Nummerierung "reichhaltiger", die Ziel-Nummerierung "ärmer".

Erst wenn wir zwei Nummerierungen haben, die Äquivalent sind, so induzieren Sie das selbe Berechenbarkeitskonzept. Wir erinnern uns nochmal an die Definition aus Kurseinheit 5:

Es seien $\nu_1:\subseteq\mathbb{N}\rightarrow{M_1}$ und $\nu_2:\subseteq\mathbb{N}\rightarrow{M_2}$ Nummerierungen.

1. $\nu_1\leq\nu_2$ ($\nu_1$ ist reduzierbar/übersetzbar auf $\nu_2$) genau dann wenn es ein $f\in P^{(1)}$ gibt mit $\nu_1(i)=\nu_2\circ f(i)$ für alle $Def(\nu_1)$

2. $\nu_1\equiv\nu_2$ ($\nu_1$ ist äquivalent zu $\nu_2$), genau dann wenn $\nu_1\leq\nu_2$ und $\nu_2\leq\nu_1$.

Unsere Nummerierungen sind also Äquivalent wenn sie ineinander übersetzbar sind. Wir haben damit beide Mengen vollständig nummeriert und kein Element aus ihnen ausgelassen.

Das führt uns zur Kernaussage des Lernziels:

Zwei Nummerierungen einer Menge $M$ induzieren auf $M$ dasselbe Berechenbarkeitskonzept wenn sie äquivalent sind.

Antwort zum Lernziel: Eine Nummerierung ist auf eine andere reduzierbar wenn wir sie durch einen totale, berechenbare Funktion in die andere "übersetzen" können. Leider gehen bei diesem Vorgang evtl. Berechenbarkeitsinformationen verloren, da wir nur noch auf den Nummern der Elemente arbeiten.

Können zwei Nummerierungen gegenseitig aufeinander reduziert werden, so sind diese Äquivalent und induzieren auf der nummerierten Menge dasselbe Berechenbarkeitskonzept

Lernziel 4

Konstruktion einer reellen Zahl $x$ einer Funktion $\nu:\mathbb{N} \rightarrow \mathbb{R}$, die nicht im Bild von $\nu$ liegt

Kommen wir nun zur zentralen Aussage dieser Kurseinheit. Genau darum drehte sich unsere ganze Vorarbeit in den Lernzielen Eins bis Drei.

Die Aussage ist:

Reelle Zahlen können wir nicht nummerieren, da es davon überabzählbar viele gibt.

Ihr erinnert euch sicher an den Überabzählbarkeitsbeweis von $\mathbb{R}$ mittels Diagonalisierung? Wenn nicht, schaut bitte nochmal im Beitrag zu KE4 im Abschnitt "zweites Diagonalisierungsargument von Cantor" nach. Die Menge der reellen Zahlen nicht mehr abzählbar (sie ist mächtiger als $\mathbb{N}$) und kann deswegen durch diese auch nicht nummeriert werden, was wir auf reelle Funktionen übertragen können. Die obige Aussage, formal dargestellt, bedeutet:

Es sei $\nu :\mathbb{N}\rightarrow{\mathbb{R}}$. Dann gibt es eine reelle Zahl $x$ mit $x\notin Bild(\nu)$.

Wenn wir also die reellen Zahlen nummerieren wollen, so gelingt uns das nicht und wir haben immer noch eine reelle Zahl, die nicht nummeriert ist. Der Beweis mittels Diagonalisierung ist im verlinkten Beitrag zu KE4 zu finden.

Ich habe mir das Leben etwas einfacher gemacht und einfach auf das zweite Diagonalisierungsargument verwiesen. Gefragt wurde aber nach einer expliziten Funktion $\nu$, für die ein $x$ zu konstruieren ist, welches nicht im $Bild(\nu)$ liegt. Machen wir das doch.

Konstruktion einer Zahl $x$, die nicht im Bild von $\nu$ liegt

Wir nehmen das gleiche Verfahren, wie im Diagonalisierungsargument und nehmen an, dass $\nu$ alle Zahlen im geschlossenen, reellen Intervall zwischen $0$ und $1$ nummeriert.

$\nu(0)=0,000001...$

$\nu(1)=0,000002...$

Das ist etwas komisch dargestellt und sicherlich keinesfalls mathematisch korrekt. Aber da die Zahlen unendlich lang sind, kann ich sie natürlich nicht ausschreiben. Das sollte nur verdeutlichen was wir nummerieren.

Wir tun also einfach mal so, als hätten wir alle Zahlen aus dem Intervall nummeriert.

Nun basteln wir uns eine Funktion $h$, die alle natürlichen Zahlen $i\in\mathbb{N}$ durchgeht, die nummerierten Elemente $\nu(i)\in\mathbb{R}$ nimmt und die $i$-te Stelle nach dem Komma dieses Elements um eines hochzählt und so daraus eine neue Zahl $x\in\mathbb{R}$ bastelt.

Offensichtlich ist diese Zahl $x$ mit $\nu(?)=x$ an jeder Stelle $i$ von der Stelle $i$ eines jeden $\nu(i)\in\mathbb{R}$ verschieden. Wir haben also tatsächlich eine neue Zahl $x\in\mathbb{R}$ gefunden, die wir nicht nummeriert haben. Obwohl wir von der Vollständigkeit unserer Nummerierung ausgegangen sind (daher das $?$ in $\nu(?)=x$).

Antwort zum Lernziel: Aufgrund der Überabzählbarkeit der reellen Zahlen ist es uns nicht möglich diese durch die natürlichen Zahlen zu nummerieren. Das führt uns selbstverständlich zu einem kleinen Problem: wir haben unser Berechenbarkeitskonzept durch Registermaschinen nur auf den natürlichen Zahlen und durch Turingmaschinen auf den Wortfunktionen aufgebaut.

Was wir dagegen tun können, steht im nächsten Lernziel.

Lernziel 5

Definition berechenbarer Funktionen $f \subseteq {({\Sigma}^{\omega})}^k \rightarrow{\Sigma}^{\omega}$

Um was geht es hier? Um Funktionen, die mittels "real RAMs" berechnet werden können. Diese Maschinen haben, im Gegensatz zu unseren Registermaschinen auf natürlichen Zahlen, reelle Zahlen im Speicher.

Leider können wir sie physikalisch nicht realisieren (wir können keine reellen Zahlen in Registern speichern), da wir nur auf $1$ und $0$ arbeiten und die Menge der reellen Zahlen -wie wir oben gesehen haben- nicht nummerieren können. Was tun?

Kümmern wir uns zunächst um das Berechenbarkeitskonzept von Grzegorczyk und Lacombe aus 1955. Im Prinzip ist das nichts anderes als die Erweiterung unserer Turing-Maschine, so dass sie statt auf natürlichen Zahlen nun auf reellen arbeitet. Aber das geht doch nicht! Haben wir das nicht gerade gesagt? Doch, haben wir. Aber es gibt da eine Möglichkeit die Menge der reellen Zahlen doch zu nummerieren, so dass wir auf ihnen rechnen können.

Zunächst brauchen wir ein genügend großes Alphabet $\Sigma$. Dann werden mit $\Sigma^{\omega}$ unendliche Folgen definiert (im Gegensatz zum Skript, hätte ich hier direkt mit Cauchy angefangen... aber ist nun egal, welche als Namen für unsere reellen Zahlen dienen). Diese unendlichen Folgen sind unsere "Namen" für die reellen Zahlen.

Nachdem wir nun unsere Eingabewerte, die reellen Zahlen durch eine unendliche Folge von Symbolen über $\Sigma$ nummeriert haben haben, brauchen wir noch eine Maschine, die darauf rumrechnen kann.

Dazu nutzen wir eine sog. Typ-2-Maschine, wie sie im Skript genannt wird und definieren die Eingabebänder als unendlich (logisch, denn eine reelle Zahl in Dezimaldarstellung ist unendlich).

Auf diesen stehen dann die Namen der reellen Zahlen, eben Elemente aus der Menge $\Sigma^{\omega}$. Zu den $k$ Eingabebändern für unsere $k$ Worte hat die Maschine auch noch weitere, unendliche Arbeitsbänder, wie viele ist uns egal. Und natürlich besitzt sie auch ein Ausgabeband, wo am Ende die Ausgabe $q$ auftaucht, man diese jedoch nicht mehr verändern kann wenn man ein Zeichen der Ausgabe auf dem Band platziert hat (das ist eine wichtige Einschränkung, bitte merken!).

Wenn wir nun einen unendlichen Dezimalbruch z.B. durch 3 dividieren, werden in jedem Schritt eine Zahl der Eingabe gelesen und ggf. eine Zahl der Ausgabe geschrieben. Da die Berechnung unendlich ist, nähren wir uns so dem idealen Ergebnis (d.h. wir runden nicht) beliebig nah an.

Und diese Maschinen sind realisierbar! Das sin nämlich nichts anderes als unsere Computer.

Probleme bekommen wir, wenn wir multiplizieren wollen. Denn wenn wir als Eingabe z.B. $0,333334$ haben, so wurde auf das Eingabeband bereits eine $0,9...$ geschrieben. Wenn dann die $4$ hinter dem Komma zur Berechnung eingelesen wird, kann die Maschine auf dem Ausgabeband aber nicht mehr zurück um die (fälschlicherweise bereits geschriebene) $0,...$ durch eine $1,...$ ersetzen. Damit haben wir ein massives Problem.

Wir brauchen hier also unbedingt eine Lösung, denn ohne können wir z.B. nicht auf $\pi$ oder $e$ rechnen (wobei man $\pi$ auch anders approximieren kann). Um diese kümmern wir uns im nächsten Lernziel.

Antwort zum Lernziel: Wir definieren diese berechenbaren Funktionen über einer unendlichen Folge von Zeichen aus einem Alphabet $\Sigma$. Diese unendlichen Folgen dienen uns als Namen für die Elemente einer Menge, auf der wir tatsächlich rechnen wollen, aber mangels passender Darstellung nicht können!

Diese Funktion wird von einer Turingmaschine, einer sog. Typ-2-Maschine berechnet, die auf $k$ unendlichen Eingabebändern für die unendlichen Symbolfolgen unserer $k$ Eingabewerte rechnet und am Ende die Ausgabe auf ein unendliches Ausgabeband schreibt, auf dem die Schränkung gilt, dass man auf diesem nicht wieder nach links laufen und seine Ausgabe im Nachhinein korrigieren kann (Einweg-Ausgabe).

Lernziel 6

Definition der Cauchy-Darstellung der reellen Zahlen

Diese Berechenbarkeit können wir auf andere Mengen ausweiten wenn wir eine Funktion haben, die die Elemente dieser Menge quasi nummeriert, d. h. ihnen Namen gibt wie wir das mit $\Sigma^{\omega}$ getan haben.

Und genau das haben Grzegorczyk und Lacombe unabhängig von einander getan. Aber nicht mit einem Alphabet $\Sigma$, sondern mit sog. Cauchy-Folgen. Diese haben sie verwendet um die reellen Zahlen (aber Achtung: nicht alle reellen Zahlen sind effektiv berechenbar, aber dazu gleich mehr)  zu repräsentieren und umgingen so das oben angesprochene Problem mit der Multiplikation.

Die Typ-2-Maschine gibt bei der Eingabe einer nach $x$ konvergierenden Cauchy-Folge ebenfalls eine nach $f(x)$ konvergierende Cauchy-Folge aus.

Die Darstellung dieser Cauhy-Folge selbst ist wie folgt definiert:

$\rho:\subseteq\Sigma^{\omega}\rightarrow\mathbb{R}$:

$\rho(p)=x:\Leftrightarrow$ es gibt $u_0,u_1,...\in Def(\nu_{rat})$, so dass $p=u_0\#u_1\#...$, und $\forall k\in\mathbb{N}\mid x-\nu_{rat}(u_k)\mid\leq 2^{-k}$

Klopper! Macht nichts.

Zunächst: $\nu_{Du}$ ist die Darstellung (Dualnotation) der natürlichen Zahlen in Form von:

$\nu_{Du}(a_n...a_0):=\sum_{i=0}^n a_i 2^i$

Beispiel: $102$ in Dual ist $1100110$. Das, eingesetzt in die Formel ist: $0*2^0+1*2^1+1*2^2+0*2^3+0*2^4+1*2^5+1*2^6=102$.

Und damit ist $\nu_{Du}(1100110)=102$.

Ganz einfach. Ist also nichts weiter als die duale Darstellung einer natürlichen Zahl, bzw. die Nummerierung einer dualen.

$\nu_{rat}$ ist die (rationale) Darstellung der rationalen Zahlen in Form von:

$\nu_{rat}(u{c\!\!\!/}v):=\nu_{Du}(u)/\nu_{Du}(v)$.

Beispiel: $3\over{5}$ mit $11\over{101}$. Das, eingesetzt in die Formel bedeutet schlicht und ergreifend:

$\nu_{rat}(11{c\!\!\!/}101):=\nu_{Du}(11)/\nu_{Du}(101)=3/5$

Auch nicht viel schwerer. Nachdem wir das haben ist die Definition oben ein Stück deutlicher geworden.

Fragen wir uns zunächst, warum Cauchy?! Das Problem ist, dass diese Folge, auf der wir rumrechnen wollen eine Eigenschaft haben muss, die für uns unverzichtbar ist. Und zwar, dass sie schnell gegen unser gesuchtes $x$ konvergiert. Mit jedem Folgeglied kommen wir näher und näher an $x$ heran.

Suchen wir uns dazu eine Folge, die nicht schnell konvergiert, so haben wir nicht schnell genug Informationen zu unserem $x$, so dass wir evtl. in Probleme laufen, wie wir das mit der Multiplikation gesehen haben.

Aber Achtung, $\rho$ ist nicht injektiv, so dass es viele Cauchy-Darstellungen einer reellen Zahl $x$ gibt, d. h. jede reelle Zahl hat viele "$\rho$-Namen". Für uns ist nur wichtig, dass die gewählten Darstellungen das Cauchy-Kriterium erfüllen.

Dass es solche langsamen Folgen gibt, hat uns Hr. Specker in seinem Satz gesagt:

Es gibt eine wachsende, berechenbare Folge rationaler Zahlen, die nicht schnell konvergiert.

Wir brauchen also nicht nur eine Folge, sondern eine schnell konvergierende Folge. Und genau dazu ist das Cauchy-Kriterium da. Reden wir also zunächst über Cauchy bevor wir fortfahren.

Viele hatten das bereits in 1141, Grundlagen der Mathematik. Aber eine Wiederholung schadet sicher nicht:

$\forall\epsilon>0\exists n_0\in\mathbb{N}:\forall n,m>n_0:\mid a_{n}-a_{m}\mid<\epsilon$

Kommen da Erinnerungen hoch? Das bedeutet, dass für jedes $\epsilon$ ein Index $n_0$ existiert, so dass für alle anderen Indizes, die größer als $n_0$ sind gilt, dass der Abstand zwischen den Gliedern der Folge $a_n$ und $a_m$ kleiner ist als $\epsilon$. Die Glieder der Folge liegen also beliebig dicht. Das beliebig dicht ist das Zauberwort.

Sehr Ihr dieses hübsche $\epsilon$? Und nun schaut mal in die Definition unserer Cauchy-Darstellung: wir fordern dort, dass der Abstand zwischen unserem $x$ und einem Glied der Folge mit einer bestimmten Geschwindigkeit immer kleiner wird, eben unser $\epsilon$ mit $2^{-k}$. Das ist unsere Konvergenzgeschwindigkeit, die wir min. benötigen um genügend schnell genug Informationen zu unserem $x$ zu bekommen.

Die Cauchy-Darstellung einer Zahl $x$ ist also der "Name" dieser Zahl, die wir zum Rechnen benutzen. Die Glieder konvergieren so schnell gegen $x$, dass wir schon nach kurzer Zeit genug Informationen zu der Zahl haben, dass uns z.B. das Multiplikations-Problem von oben nicht passieren kann.

Und das ist auch der Satz von Prof. Weihrauch, der auch in der Literatur zitiert wird. Es geht aber nicht mehr um Zahlen, sondern um Funktionen auf reellen Zahlen:

Eine Funktion $f\subseteq\mathbb{R}\rightarrow\mathbb{R}$ ist berechenbar, wenn es eine Typ-2-Turingmaschine $M$ gibt, die jeden Namen von $x\in{Def(f)}$ (unsere Cauchy-Folge, die gegen $x$ konvergiert) in einen Namen von $f(x)$ (unsere Cauchy-Folge, die gegen $f(x)$ konvergiert) überführt.

Wir rechnen also ab jetzt auf Gliedern einer Folge und brauchen dazu eine Typ-2-Turingmaschine, die uns zu einer reellen Zahl $x$ eine Cauchy-Folge ausgibt, darauf herumreitet und uns die Cauchy-Folge zum Ergebnis $f(x)$ ausspuckt. Ich wiederhole mich, oder

Dieser Satz ist im Skript auch in Prosa beschrieben:

Die reelle Funktion $f$ ist dann berechenbar wenn wir ein Verfahren angeben können, dass eine gegen $x$ aus der Definitionsmenge von $f$ konvergierende Folge (d.h. unser Name für $x$) in eine schnell gegen $f(x)$ konvergierende Folge überführt, die ein Name für unser Ergebnis ist.

Also genau das, was wir gerade bereits gesagt haben.

Man macht sich leicht klar, dass die Folgen nichts anderes sind als die (unendliche) Darstellung unseres Parameter, mit dem wir die Funktion füttern und unseres Ergebnisses. Sie können nie größer sein als das Ergebnis $f(x)$ oder der Parameter $x$ (die sind unsere Limes) und nähren sich diesen beliebig (unendlich) nah an. Und das auch noch so schnell, dass wir garantiert kein Falschergebnis bekommen wie z.B. bei bei der Multiplikation von oben.

Aber Moment mal: wir brauchen eine Typ-2-Turingmaschine, die uns eine Cauchy-Folge für eine reelle Zahl $x$ berechnet? Fällt euch jetzt schon das Problem auf? Wir haben nur eine abzählbare Anzahl an Turingmaschinen und damit auch eine abzählbare Anzahl an Typ-2-Maschinen. Aber eine überabzählbare Anzahl an reellen Zahlen. Was folgt daraus? Ein etwas beängstigender Satz:

Es gibt reelle Zahlen, die nicht berechenbar sind.

Diese berechenbaren Zahlen bilden also einen Teilkörper (in der Literatur wird er $EC$ - effectively computable - genannt) der reellen Zahlen.

Bleiben wir auf dem mathematischen Boden, so sind folgend einige Beispiele von reellen, berechenbaren Funktionen aus dem Skript:

• $f(x)=-x$
• $f(x,y)=x+y$
• $f(x,y)=max(x,y)$
• $f(x,y)=xy$
• $f(x)=1/x$
• $f(x)=\sqrt{x}$
• $f(x)=e^x$
• $f(x)=sin(x)$
• $f(x)=log(x)$

Wichtig: der fundamentale Stetigkeitssatz besagt, dass Stetigkeit eine notwendige Voraussetzung für $\rho$-Berechenbarkeit ist. Die Funktion darf also keine Sprungstellen haben. Eine Heaviside-Funktion (Sprungfunktion) ist damit also z.B. nicht $\rho$-berechenbar.

Antwort zum Lernziel: Um uns die Möglichkeit zu verschaffen mit reellen Zahlen zu rechnen, was wir offenbar tun und müssen, ist es notwendig diese in einer bestimmten Form darzustellen (da wir in Registern keine reellen Zahlen speichern können) und sie auf ein Berechenbarkeitsmodell zurückzuführen. Basis dieses Modell ist die bereits erwähnte Typ-2-Maschine.

Jedoch haben wir mit der Darstellung der reellen Zahlen als Dezimalzahlen ein Problem (siehe Multiplikation), dass wir nur lösen können wenn wir diese so codieren, ihnen also Namen geben, die uns die notwendigen Informationen der Dezimalstellen der reellen Zahlen so schnell wie möglich liefern.

Wir haben die Möglichkeit die reellen Zahlen als Folgen zu codieren, die gegen diese Zahlen konvergieren. Aber nicht als irgendwelche Folgen, sondern als Folgen mit einem bestimmten Geschwindigkeitskriterium: der Cauchy-Eigenschaft um uns so schnell wie möglich mit den notwendigen Informationen versorgen damit wir nicht in Probleme wie mit der Multiplikation laufen.

Dieses so schnell wie möglich wird mit dem Faktor $2^{-k}$ für jedes Glied der Folge spezifiziert, es bezeichnet den Abstand zwischen der abgebildeten, reellen Zahl $x$ und dem Glied der Folge $a_k$. Solange dieses Kriterium gilt, können wir uns mit $\rho$ eine beliebige Folgen-Darstellung einer reellen Zahl $x$ aussuchen. Denn durch die Nicht-injektivität von $\rho$ kann eine reelle Zahl $x$ mit mehreren Cauchy-Folgen dargestellt werden.

Lernziel 7

Zeigen, dass z.B. $x \mapsto x+5$ $(\rho,\rho)$-berechenbar ist

Was tun wir, wenn wir die Berechenbarkeit einer Funktion zeigen wollen? Wir verweisen auf die obigen Beispiele Und wenn wir dazu gezwungen werden, das selbst zu tun? Dann versuchen wir es doch:

Um zu zeigen, dass $f(x) = x+5 (\rho,\rho)$-berechenbar ist, müssen wir eine "Typ-2-Maschine" angeben, die als Eingabe das codierte Wort $p$, d.h. die Cauchyfolge $u_0\#u_1\#...$ (Eingabeparameter $x$) als Darstellung der reellen Eingabe $x$ annimmt und in eine Folge $q=\omega_0\#\omega_1\#...$ (reelles Ergebnis $f(x)$) umwandelt, so dass gilt:

$\rho(p)+5=\rho(q)$.

Die $5$ können wir auch mit auf das Eingabeband schreiben, getrennt durch $\#\#$ von $p$, der Folge für $x$.

Ebenfalls muss es möglich sein, die $5$ durch eine Cauchy-Folge $v_0\#...\#v_k$ zu codieren und dann $\nu_{rat}(\omega_k) = \nu_{rat}(u_k)+\nu_{rat}(v_k)$ ausgeben zu lassen. Aber ihr habt den Ansatz nachvollziehen können, hoffe ich.

Die gesuchte Maschine $M$ gibt dann die Worte $\omega_k$ aus, so dass $\nu_{rat}(\omega_k) = \nu_{rat}(u_k)+5$ gilt.

Um das Cauchy-Kriterium, die geforderte Konvergenzgeschwindigkeit $2^{-k}$ zu erfüllen, gilt:

$\mid x-\nu_{rat}(u_k)\mid\leq2^{-k}$

Wir wollen ja, dass die Glieder unserer Folge gegen der Eingabe gegen $x$ konvergieren.

$\mid (x+5)-\nu_{rat}(\omega_k)\mid\leq2^{-k}$

Und auch die Glieder der Folge unseres Ergebnisses sollen gegen das Ergebnis $f(x) = x+5$ konvergieren.

Damit ist $x \mapsto x+5$ $(\rho,\rho)$-berechenbar. Oder zumindest wäre das auf die Schnelle der Ansatz, den ich fahren würde.

Eventuell trage ich eine ausführliche Darstellung im Rahmen der Prüfungsvorbereitung hier nach.

Antwort zum Lernziel: Um zu zeigen, dass eine Funktion $f$ $\rho,\rho$-berechenbar ist, muss man die reellen Eingabeparameter mittels einer Folge codieren, deren Glieder $a_k$ das Cauchy-Kriterium mit der Konvergenzgeschwindigkeit $2^{-k}$ erfüllen. Das gilt ebenfalls für die Glieder der Ausgabe $f(x)$.

Erfüllen diese das Kriterium und ist die Funktion selbst berechenbar, so ist die Funktion $f$ ebenfalls $\rho,\rho$-berechenbar.

Wer Fehler findet (vor allem im letzten Abschnitt), ASAP in die Kommentare damit ich das schnell berichtigen kann.

Update: durch den Hinweis von Philipp ist mir noch etwas aufgefallen. Der Vergleich von deterministischen Turingmaschinen zu nichtdeterministischen ist nicht ganz deutlich rüber gekommen. Daher habe ich den Abschnitt noch einmal überarbeitet (Lernziel 2, 3 und 4).

Update: Antworten zu den Lernzielen.

Das ist ein schönes Thema. Wirklich. Auch keinerlei Sarkasmus hier drin versteckt. Ich möchte - wie im Skript auch - zunächst den Nichtdeterminismus anhand eines klassischen Problems erläutern:

Hamiltonkreisproblem

Zunächst: was ist ein Hamiltonkreis? Ein Hamiltonkreis ist ein Weg in einem Graphen, der jeden Knoten genau 1x enthält. Es ist ein Problem aus der Graphentheorie. Ich klaue mir wieder ein Bild aus der zugehörigen Wikipedia-Seite um das zu verdeutlichen:

Quelle: Wikipedia 

Das Problem ist es diesen Weg in so einem Graphen zu finden (sinniger Weise ist einer schon im Bild eingezeichnet). Problem? Wir könnten alle Wege durchprobieren. Jeden Knoten mal durchtesten. Das Problem hierbei ist jedoch, dass der Aufwand exponentiell ist (in Abhängigkeit von der Anzahl der Knoten). Was wir brauchen ist jedoch ein effizienter Algorithmus.

Hier kommt unser Nichtdeterminismus ins Spiel, denn uns interessieren ja vielleicht nicht alle Hamiltonkreise im Graphen, sondern einfach nur ob es einen gibt. Was wäre dann der Ansatz? Raten und Prüfen! Wir raten eine Knotenfolge und prüfen ob sie uns in einem Hamiltonkreis bringt. Und das geht in Polynomialzeit mittels einer nichtdeterministischen TM, einer $NTM$.

Lernziel 1

Erklärung der Modelle der KTM und der NTM

Die Kontrollturingmaschine (KTM) aus dem Skript tut nichts weiter als das zu prüfen. Es bekommt zwei Eingaben, nämlich $x$ (auf dem Eingabeband) und $y$ (auf Band 0, was als Ausgabeband ausgezeichnet ist, aber nicht benötigt wird), wobei $y$ ein Beweis dafür sein soll, dass $x\in{L}$. Hält die Maschine also in dem ausgezeichneten Endzustand $q_{+}$, so ist $y$ ein Beweis, dass $x\in{L}$. Wir müssen hier aber jedes Mal das $y$ (z.B. die zu testende Knotensequenz) auf Band 0 schreiben.

Wir können das $y$ aber auch raten lassen. Hierfür ist unsere nichtdeterministische Turingmaschine (NTM) da. Statt einer Übergangsfunktion (bei einem entsprechenden Zustand und einem entsprechenden Zeichen unter dem Lesekopf wird spezifiziert was unter den Lesekopf geschrieben, in welche Richtung sich bewegt und welcher Zustand als nächstes eingenommen werden soll) wird hier eine Übergangsrelation (es gibt mehrere Übergänge, die zufällig ausgeführt werden) verwendet. Jetzt zieht Ihr die Augenbrauen zusammen, richtig? Das liegt daran, dass dieses Modell kein Modell ist, welches man real implementieren kann: es ist rein theoretischer Natur. Löst euch also etwas von eurer "Hardware" Wenn man also irgendwelche Abzweigungen nimmt und am Ende in einem der Endzustände landet, so ist $x\in{L}$. Es zählt also einfach nur, dass es einen Weg, der die Maschine in einen Endzustand führt gibt wenn $x\in{L}$ ist.

Durch die Verzweigungen bilden die Berechnungen am Ende einen Baum, dessen Rechenzeit $t_M$ die Tiefe des Baums darstellt. Der Bandbedarf $s_M$ ist das Maximum des Bandbedarfs aller Knoten in diesem Baum.

Antwort zum Lernziel: mit der Kontrolltunringmaschine (KTM) prüfen wir eine vorgegebene Lösung auf ihre Richtigkeit. Die vorgegebene Lösung wird Hilfseingabe genannt und muss immer manuell eingegeben werden.

Mittels nichtdeterministischer Turingmaschine (NTM) können wir diese Hilfseingabe auch raten lassen: dabei bekommt die NTM eine Übergangsrelation, die nicht eindeutig ist. Bei einer Belegung und einem Zustand kann kann es also mehrere Folgezustände geben, so dass eine zufällige Auswahl erfolgt (oder alle möglichen Pfade parallel durchlaufen werden).

Lernziel 2

Äquivalenz der Modelle begründen

Spannend ist, dass beide Modelle (KTM und NTM) äquivalent sind. Vor allem, dass man sie gegenseitig innerhalb der gleichen Zeit- und Bandschranken ineinander überführen kann. Die Überführung einer KTM in eine NTM geschieht zunächst wie folgt:

KTM nach neue KTM mit Hilfsalphabet $\{0,1\}$

 1. die KTM wird in eine neue KTM mit dem Alphabet $\{0,1\}^m$ überführt ($2^m$ wenn die Anzahl der Zeichen nicht bereits eine Zweierpotenz darstellt)

2. die Befehle der alten KTM werden durch Befehlsfolgen ersetzt, wo der Befehl $m$ aufgerufen wird. Ebenso ergeht es den Tests

Die Laufzeit erhöht sich hier nur um einen konstanten Faktor. Und da dieser uns bei der Betrachtung der Schranke nicht interessiert, bleiben wir innerhalb der Laufzeit der alten KTM. Ebenso beim Bandbedarf.

Neue KTM nach NTM

Nun erzeugen wir aus der neuen KTM mit Hilfsalphabet $\{0,1\}$ eine NTM. Das Problem hierbei: wir müssen $y$, die Eingabe, nun erzeugen und kennen ihre Schranke nicht. Dazu wird auf dem Arbeitsband $k+2$ ($k$ ist die Anzahl der Arbeitsbänder der neuen KTM) die Kontrolleingabe $y$ während der Simulation der neuen KTM erzeugt. Jeder Schritt der neuen KTM wird durch maximal 4 Schritte simuliert und der Bandbedarf vergrößert sich um 1. Alles konstante Faktoren und unwichtig.

NTM zur alten KTM

Um den Bogen wieder zurück zu schlagen müssen alle Verzweigungen durch einen Test auf dem Eingabeband 0 ersetzt werden.

Antwort zum Lernziel: Die Äquivalenz von Kontrollturingmaschinen und nichtdeterministischen Turingmaschinen begründet sich darin, dass man beide ineinander überführen kann und die Simulation innerhalb der gleichen Band- und Zeitschranken geschieht (wenn man von den konstanten Faktoren mal absieht).

Achtung: Bitte verwechselt nicht KTMs und DTMs. Nichtdeterministische Turingmaschinen (NTMs) sind zwar ebenfalls äquivalent zu deterministischen Turingmaschinen (DTMs), da man NTMs in DTMs überführen kann. Aber das geschieht nicht innerhalb der gleichen Zeit- und Bandschranken!

Nach dem Satz von Savich gilt, dass wenn eine NTM ein Problem polynomiell lösen kann, kann eine äquivalente DTM das Problem in exponentieller Zeit lösen. Der Speicherplatzbedarf erhöht sich ebenfalls: er wird quadratisch.

Exkurs: Hamiltonkreisproblem in der KTM

Um z.B. das Hamiltonkreisproblem in einer KTM zu entscheiden, müssen wir das Problem formalisieren. Dazu wird der Graph als Adjazenzmatrix geschrieben und zeilenweise aufgeschrieben. Als Kontrolleingabe dient dann eine Folge von Knoten und die KTM prüft die Eingabe auf die gesuchte Eigenschaft.

Lernziel 3

Definition nichtdeterministischer Komplixitätsmaße und -klassen

Da wir KTMs durch NTMs mit den gleichen Schranken simulieren können gilt:

$ZEIT(f)\subseteq NZEIT(f)$

$BAND(f)\subseteq NBAND(f)$

sowie

$NZEIT(f)\subseteq BAND(f)$

Definieren wir hier auch $NZEIT(f)$:

$NZEIT(f)\subseteq\bigcup_{c\in\mathbb{N}}ZEIT(c^{f(n)})$

Mit der Menge $NZEIT$ geben wir die Menge der Sprachen an, die von einer nichtdeterministischen Turingmaschine in Zeit $O(f)$ akzeptiert werden können (Wikipedia).

Die Reihenfolge darf hier auch nicht fehlen: $P\subseteq NP\subseteq PSPACE\subseteq\bigcup_{c\in\mathbb{N}}ZEIT(2^{n^{c}})$

Ebenso der nichtdeterministische Bandbedarf:

Sei $log\in O(f)$, so gilt:

$NBAND(f)\subseteq\bigcup_{c\in\mathbb{N}}ZEIT(c^{f(n)})$ und $LOGSPACE\subseteq P$.

Sowie

$NBAND(f)\subseteq BAND(f(n)^2)$ und $NPSPACE = PSPACE$ (Satz von Savitch)

Wichtig: noch ein paar Ergänzungen zum Satz von Savitch: dieser Satz besagt nichts anderes, als dass jedes von einer $NTM$ (nichtdeterministisch, d.h. wir orakeln die Lösungseingabe) lösbares Problem  auch von einer $DTM$ (deterministisch, d.h. wir orakeln nicht) in exponentieller Zeit gelöst werden kann und der Platzbedarf dieser Maschine nur quadratisch höher liegt. Die Folgerung aus diesem Satz bedeutet, dass die Bandkomplexitätsklasse $NPSPACE$ mit der Bandkomplexitätsklasse $PSPACE$ übereinstimmt.

Antwort zum Lernziel: Definitionen siehe oben.

PS: Wie im vorherigen Lernziel angedeutet: verwechselt bitte nicht NTMs/KTMs/DTMs. Und merkt euch den Satz von Savitch

Lernziel 4

Zusammenhang zwischen deterministischen und nichtdeterministischen Komplexitätsklassen

Antwort zum Lernziel: durch die Überführung der nichtdeterministischen Turingmaschinen in deterministische Kontrollturingmaschinen, die die selben Komplexitätsklassen in Zeit und Band inne haben besteht hier ein entsprechend enger Zusammenhang.

Update: Ebenso verhält es sich bei der Überführung von nichtdeterministischen Turingmaschinen in deterministische Turingmaschinen. Nach Savitch haben diese aber nicht die gleichen Zeit- und Bandschranken.

Nach dem Satz von Savich gilt, dass wenn eine NTM ein Problem polynomiell lösen kann, kann eine äquivalente DTM das Problem in exponentieller Zeit lösen. Der Speicherplatzbedarf erhöht sich ebenfalls: er wird quadratisch.

Lernziel 5

Definition von ${}\leq_{pol}{}$

Hierzu bemühen wir noch einmal unsere Definition der Reduzierbarkeit: wenn wir Mengen auf andere Mengen reduzieren könne, so gelten die Eigenschaften der kleineren Menge auch für dir größere. Der Unterschied zu dem Verfahren in der Komplexitätstheorie ist es, dass wir nun Wortfunktionen statt Zahlenfunktionen verwenden und diese Überführungsfunktionen nur aus einer bestimmten Komplexitätsklasse für Funktionen zulassen. Es eignen sich nur Komplexitätsklassen, die unter Komposition (wenn sie $f,g$ enthalten, enthalten sie auch $f\circ g$) abgeschlossen sind. Kämpfen wir uns also durch die Definition:

LOGSPACE und polynomielle Reduzierbarkeit

$L$ heißt $LOGSPACE$-reduzierbar auf $M$ ($L\leq_{log}{}$) wenn es eine Funktion $f$ aus der Klasse $FLOGSPACE$ gibt und für alle $x\in L$ gilt, dass $f(x)\in M$ ist.

$L$ heißt polynomiell-reduzierbar auf $M$ ($L\leq_{pol}{}$) wenn es eine Funktion $f$ aus der Klasse $FP$ gibt und für alle $x\in L$ gilt, dass $f(x)\in M$ ist.

Die Überführungsfunktion muss für die $LOGSPACE$-Reduzierbarkeit also aus der logarithmischen Komplexitätsklasse stammen, während für die polynomielle Reduzierbarkeit gefordert wird, dass die Funktion aus der polynomiellen Komplexitätsklasse kommen muss. Damit haben wir den zentralen Satz für unsere Komplexitätsklassen:

LOGSPACE, NLOGSPACE, P, NP, PSPACE sind abgeschlossen gegen $\leq_{log}{}$, P, NP, PSPACE aber auch gegen $\leq_{pol}{}$

Die meisten von euch werden das "F" vor *SPACE schon korrekt gedeutet haben. Da ich aber selbst kurz drüber nachgedacht habe, es im Skript aber nur in einem Nebensatz gefallen ist, möchte ich noch einmal darauf hinweisen. Während wir in z.B. in LOGSPACE, P, ... Sprachen (die in der Zeit entschieden werden können) drin liegen haben, haben wir in FLOGSPACE, FP, ... aber Funktionen. Diesen Unterschied solltet Ihr im Kopf behalten (Danke Barbara).

Antwort zum Lernziel: Mit der polynomiellen Reduktion ist es uns möglich mit Angabe einer Funktion (die innerhalb der polynomiellen Komplexitätsklasse ist) eine Menge auf eine andere zu reduzieren und so Eigenschaften der Menge quasi zu "vererben". Das spielt eine wichtige Rolle bei dem Beweis der $NP$-Vollständigkeit von Mengen.

Lernziel 6

Erklärung der Vollständigkeit

Kümmern wir uns zunächst um die Definition aus dem Skript:

$M$ ist $NP$-hart wenn $L\in{NP}$, $L\leq_{pol}{M}$

Bedeutet: $M$ ist $NP$-hart wenn es eine Menge $L$ in $NP$ gibt, die wir auf die Menge $M$ in polynomieller Zeit reduzieren können. Haben wir also eine Menge $L$, die nachgewiesen $NP$-hart ist, und können wir mit einer polynomiellen Überführungsfunktion $f\in{FP}:L\rightarrow M$ (zu einem $x$ aus $L$ bekommen wir mit $f(x)=y$ ein $y$ aus $M$) diese Menge auf $M$ reduzieren, so ist die Menge $M$ eben $NP$-hart.

Noch einmal drüber nachdenken, was $NP$-hart bedeutet? Das Problem ist mit einer nichtdeterministischen Turingmaschine (NTM) in polynomieller Zeit lösbar. Das Problem ist dann $NP$-hart wenn sich alle nichtdeterministisch polynomiell lösbaren Probleme darauf reduzieren lassen (danke Barabara). Wie z.B. unser Hammiltonkreisproblem (das ist zudem auch noch $NP$-vollständig, aber dazu gleich mehr). Definition gemerkt und verstanden? Gut, dann weiter.

$M$ ist $NLOGSPACE$-hart wenn $L\in{NLOGSPACE}$, $L\leq_{log}{M}$

Das Selbe in Grün. Nur wird hier die logarithmische Reduzierbarkeit der Menge gefordert. Jetzt kommt das, warum es diesen Abschnitt überhaupt gibt. Die Vollständigkeit:

$M$ heißt $NP$-vollständig wenn: $M$ $NP$-hart und $M\in{NP}$

Wir sprechen hier also von Vollständigkeit wenn $M$ zu der Klasse $NP$ gehört (eine $DTM$ kann in polynomieller Zeit die Richtigkeit der geratenen Lösung verifizieren) und alle anderen Mengen aus $NP$ mittels einer Überführungsfunktion $f$ in polynomieller Zeit (d.h. $f\in{FP}$) auf die Menge $M$ überführt werden können. Ist ein langer Satz, lest ihn ein paar Mal langsam durch bis sich bei euch im Kopf ein Bild zeichnet. Damit sind alle $NP$-vollständigen Probleme auch $NP$-hart. Das gleiche gilt dann für $NLOGSPACE$ und $P$:

$M$ heißt $NLOGSPACE$-vollständig wenn: $M$ $NLOGSPACE$-hart und $M\in{NLOGSPACE}$

$M$ heißt $P$-vollständig wenn: $M$ $P$-hart und $M\in{P}$

Das war schon etwas entspannter als der vorherige Beitrag zu KE2, oder?

Antwort zum Lernziel: die Vollständigkeit einer Menge zu einer Komplexitätsklasse bedeutet nicht nur, dass die Menge mit einer Turingmaschine erkannt werden kann, deren Schranke innerhalb der Komplexitätsklasse liegt. Sondern auch, dass sich alle anderen, vollständigen Probleme aus dieser Komplexitätsklasse darauf reduzieren lassen. Alle Eigenschaften, die wir für eine Klassen-vollständige Menge darlegen gelten auch für alle anderen Klassen-vollständigen Mengen.

Der Vorteil bei vollständigen Problemen in einer Klasse ist, dass wenn wir es z.B. schaffen für ein $NP$-Vollständiges Problem einen polynomiellen Algorithmus anzugeben, der das Problem entscheidet, so haben wir gleichzeitig für alle $NP$-vollständigen Probleme einen Lösungsweg gefunden, da sich diese polynomiell aufeinander (wenn auch mit Zwischenschritten) reduzieren lassen.

Da wir noch bisschen Platz im Beitrag haben, würden sich vielleicht einige Details zum Begriff Vollständigkeit hier gut machen:

Rekapitulation: wozu ist die Vollständigkeit gut?

(dieser Abschnitt hat das rechts oben verlinkte Buch von Dirk. W. Hoffmann - absolute Kaufempfehlung - und diverse Internet-Artikel als Informationsbasis)

Die Vollständigkeit ist ein zentrales und wichtiges Werkzeug der theoretischen Informatik. Sie vereinfacht eine Dinge ungemein. Durch die Reduktion können wir alte Probleme auf neue reduzieren, d.h. wir vererben quasi Komplexitätsaussagen von einer Menge auf eine andere. Was ist hier also der Unterschied zwischen hart und vollständig? Ein Problem/eine Menge $M$ ist z.B. $NP$-hart wenn sich alle Probleme aus der Klasse $NP$ auf dieses reduzieren lassen. Die Menge $M$ selbst muss nicht in $NP$ liegen. Erst wenn die Menge selbst in $NP$ liegt, spricht man von Vollständigkeit.

Wie zeigen wir Vollständigkeit?

1. Zunächst müssen wir zeigen, dass ein z.B. Problem in der Klasse $NP$ liegt: Wir geben eine $NTM$ an (eine $DTM$ würde sogar auch reichen), die die Eingabe in polynomieller Zeit auf Richtigkeit prüft. haben wir das getan, so fehlt uns nur noch der Nachweis der Reduktion:
2. Nun zeigen wir die $NP$-Härte: dass mittels polynomieller Reduktion sich alle Mengen aus $NP$ auf unsere untersuchte Menge $M$ reduzieren lassen. Das machen wir, indem wir irgendeine Menge aus $NP$ nehmen, die selbst bereits als vollständig eingestuft wurde. Warum können wir das tun? Durch die Transivität der Überführungsfunktion.

Done. Ist kein vollständiges Problem für eine Klasse bekannt, so wird die generische Reduktion angewandt. Ein Beispiel hierzu gab Stephen A. Cook (der lebt noch) in seinem berühmten Satz (für den er auch den Turing-Award bekam). Er zeigte, dass das SAT-Problem $NP$-Vollständig ist. Fortan konnte man für andere Mengen mittels Reduktion von SAT auf diese die $NP$-Vollständigkeit einfach nach dem oben beschriebenen Verfahren gezeigt werden. Im nächsten Beitrag werden wir versuchen $SAT$ als $NP$-hart zu beweisen ohne die Abkürzung mittels Reduzierbarkeit zu nehmen.

Welche Vorteile hat die Vollständigkeit noch?

Einer der Vorteile der Vollständigkeit ist die Beziehung zu allen anderen vollständigen Problemen in der Komplexitätsklasse. Nehmen wir z.B. $NP$: gelingt es uns für ein $NP$-vollständiges Problem zu zeigen, dass es in polynomieller Zeit lösbar ist (schaffen wir z.B. das Hamiltonkreisproblem in deterministischer, polynomieller Zeit zu lösen), so sind auch direkt alle anderen vollständigen Probleme aus der Klasse $NP$ deterministisch polynomiell lösbar. Damit wäre die Beziehung $P=NP$ positiv bewiesen, was als eines der wichtigsten, mathematischen Probleme unserer Zeit gilt. Aus diesem Grund wurde es auch in die Liste der Millenium-Probleme aufgenommen. Neben Ruhm und Ehre gibt es oben drauf noch eine Million USD vom Clay Mathematics Institute.

Damit sind wir auch mit der Kurseinheit 3 durch.

Auch wenn ich mich mittlerweile wie eine Schallplatte anhöre: wer Erklärungs-Fehler findet, bitte ASAP melden damit ich das sofort korrigieren kann.

Buchempfehlung

Update 4: MathJax wollte nicht so, wie ich oder einige Leser des Blogs. Nun sollten alle Symbole wieder angezeigt werden.

Update 3: Ein kleiner Exkurs zum Thema $P-NP$ wurde hinzugefügt.

Update 2: Zwei Fehler in der Berechnung im Lernziel 3 sind nun gefixt.

Update: Antworten zu Lernzielen hinzugefügt. Soweit möglich.

Lernziel 1

Verstehen des Verfahrens von Separations- und Hierarchiesätzen

(Großer Dank an Barbara, Oliver, Björn und Lothar aus der NG für die Tipps zu diesem Thema).

Zunächst: was sind Hierarchiesätze und wofür werden sie gebraucht? Der Satz aus der Wikipedia ist hier durchaus hilfreich:

Für die gebildeten Klassen möchte man möglichst beweisen, dass durch zusätzlich bereitgestellte Ressourcen tatsächlich mehr Probleme gelöst werden können. Diese Beweise bezeichnet man als Hierarchiesätze (auch Separationssätze genannt), da sie auf den Klassen der jeweiligen Ressource eine Hierarchie induzieren. Es gibt also Klassen, die in eine echte Teilmengenbeziehung gesetzt werden können. Wenn man solche echten Teilmengenbeziehungen ermittelt hat, lassen sich auch Aussagen darüber treffen, wie groß die Erhöhung einer Ressource sein muss, um damit eine größere Zahl von Problemen berechnen zu können.

...

Die Hierarchiesätze bilden letztlich das Fundament für die Separierung von Komplexitätsklassen. Sie bilden einige der frühesten Ergebnisse der Komplexitätstheorie.

...

D.h. wir haben hier die Möglichkeit Komplixitätsklassen von einander trennen zu können (wenn bestimmte Vorbedingungen erfüllt sind), so dass eine echte Inklusion erfüllt ist.

Bevor wir hier weitermachen, wiederholen wir noch einmal ein paar Kleinigkeiten aus den vorhergehenden Beiträgen zum Thema Sprache:

Eine Sprache $L(M)$ ist entscheidbar wenn die charakteristische Funktion

$\chi_L(\omega)=\begin{cases}1&\text{ falls }\omega\in{L}\\0&\text{ falls }\omega\notin{L}\end{cases}$

berechenbar ist. Es gibt noch die Definition mit "...hält für jede Eingabe.", was natürlich auch korrekt ist.

Wir können diese Maschine so modifizieren, dass sie eine $1$$ ausgibt bevor sie im akzeptierenden Zustand hält oder in einem nicht-akzeptierenden Zustand hält und eine $0$ vorher ausgibt. Wie wir bald erfahren werden, ist das Wortproblem für $Typ-1$-Sprachen entscheidbar.

Beispiel: $L=\{a^n\mid n>10\}$. Wir können für jede Eingabe $x$ entscheiden ob $x$ den Einschränkungen genügt oder nicht.

Eine Sprache $L(M)$ ist aufzählbar wenn die charakteristische Funktion

${\chi_L}^{'}(\omega)=\begin{cases}1&\text{ falls }\omega\in{L}\\\perp&\text{ falls }\omega\notin{L}\end{cases}$

berechenbar ist. Auch hier greife ich etwas vor: das Wortproblem für $Typ-0$-Sprachen ist nur semi-entscheidbar.

Beispiel: Halteproblem$L=\{i\#x\mid M_i\text{ haelt auf }x\}$ ist rekursiv aufzählbar. Hier besteht das Wort unserer Sprache aus $i\#x$, wobei $i$ die Codierung einer $TM$ ist und $x$ die Eingabe dazu. Da wir nicht entscheiden können, ob die Maschine $M_i$ bei der Eingabe von $x$ nicht hält, ist auch unsere daraus erstellte Sprache nur rekursiv aufzählbar.

Nun haben wir uns noch einmal klar gemacht, was eine Sprache ist und wann man sie als entscheidbar/rekursiv aufzählbar klassifizieren kann. Jetzt können wir über Komplexitätsklassen reden.

Beweis: Unterschiedlichkeit der Komplexitätsklassen

(Danke an Lothar für die geduldige Erklärung der Vorbedingungen)

Wie beweisen wir die Unterschiedlichkeit von Komplexitätsklassen? Dass z.B. $ZEIT(n)\subsetneqq ZEIT(n^2)$ ist? Mittels Diagonalisierung und universellen Maschinen. Bei dem Diagonalisierungsbeweis wird ein ähnliches Verfahren verwendet wie beim Selbstanwendbarkeitsproblem (spezielles Halteproblem, wir erinnern uns?): die Diagonalisierung erfolgt nicht über alle rekursiven Mengen, sondern über die Mengen in $ZEIT(f)$. Benötigt wird hierzu:

1. eine universelle, $f$-zeitbeschränkte Maschine (diese wird verwendet um zu prüfen, ob sich eine Menge in einer bestimmten Zeitschranke befindet)

2. ein Komplexitätsklasse mit Zeitschranke $g$

Der Beweis beim Zeitseparationssatz ($ZEIT(g)\nsubseteqq ZEIT(f)$) besteht im Grunde darin eine Menge $D$ zu konstruieren, die zwar in $ZEIT(g)$ liegt, aber nicht in $ZEIT(f)$. Das erfolgt als Diagonalbeweis indem man durch einen Widerspruch zunächst zeigt, dass die Menge $D\notin{ZEIT(f)}$ ist, was durch unsere universelle Maschine mit Laufzeit $f(n)\cdot log\text{ }f(n)$ entschieden wird.

Fazit: wir simulieren also eine Maschine, die die Sprache aus der Menge $ZEIT(g)$ (also eine Sprache, die in Laufzeit $O(g)$ entschieden wird) auf einer universellen Maschine entscheidet, die durch $f$ beschränkt ist. Wenn wir über die Beschränkung, die uns $f$ auferlegt laufen, so ist die Sprache nicht in $ZEIT(f)$.

Die schnellste Simulation einer $k$-Band Maschine durch eine universelle $2$-Band Maschine hat die Laufzeit $O(f(n)\cdot log\text{ }f(n))$, was klar ist: wir müssen zunächst die Maschine selbst simulieren (Faktor $f(n)$) und dann die $k$ Bänder auf 2 Bänder verkleinern (Faktor $log f(n)$). Würden wir nur ein Arbeitsband verwenden, so wäre der Aufwand nicht mehr $log\text{ }f(n)$, sondern $f(n)^2$ (siehe KE1).

Aus diesem Grund fordern wir auch, dass $g\notin O(f(n)\cdot log\text{ }f(n))$ ist damit wir die Sprache mit der Schranke $g$ auf unserer Maschine entscheiden können. Wäre $g\in O(f(n)\cdot log\text{ }f(n))$, so könnten wir nicht prüfen ob die Sprache akzeptiert wird, da unsere universelle Maschine für die Prüfung zu langsam ist, denn die hat genau die Laufzeit, wo auch $g$ drin wäre. Die universelle Maschine hätte also nicht genug Zeit die zu simulierende Maschine zu simulieren um die Akzeptanz der Sprache zu prüfen. Uah, was für ein Satz!

Anschließend erfolgt der Nachweis, dass $D\in{ZEIT(f)}$ indem wir eine Maschine angeben, die durch $f$ beschränkt ist und dennoch $D$ entscheiden kann und die Unterschiedlichkeit der zwei Komplexitätsklassen ist bewiesen.

Der Beweis für den Zerhierarchiesatz ($ZEIT(f)\subsetneq ZEIT(g)$) erfolgt genauso, nur wird vorausgesetzt, dass $f$ mindestens das gleiche Wachstum, wie $g$ hat: $f\in{O(g)}$.

Antwort zum Lernziel: Zeithierarchie- und separationssätze dienen dazu Komplexitätsklassen von einander zu trennen. Im Endeffekt geht es um Separierung und der Bildung von Hierarchien bei den Ressourcen Band und Zeit.

Was ist also unser Zeithierarchie- oder separationssatz? Schreiben wir sie uns zunächst einmal auf (ich empfehle euch, dass Ihr das auf dem Papier auch macht):

Lernziel 2

Voraussetzung für Separations- und Hierarchiesätze benennen und begründen

Zeitseparationssatz:

Sei $f, g: \mathbb{N}\rightarrow\mathbb{N}$, $g$ zeitkonstruierbar, $n\in O(g)$, $g\notin O(f(n)\cdot\text{ }log f(n))$.

Dann ist $ZEIT(g)\nsubseteqq ZEIT(f)$

Damit $ZEIT(g)$ keine Teilmenge von  $ZEIT(f)$ ist, müssen einige Voraussetzungen erfüllt sein. Diese sind:

1. Wir haben ein $g$, dass zeitkonstruierbar ist (die maximale Schrittzahlfunktion der $TM$ von $g$ hat als obere Schranke das Wachstum von $g$ für alle Eingaben, siehe unten),

2. ein $n\in O(g)$, $n$ bedeutet hier, dass $g$ mindestens linear wächst (könnten wir weglassen, da es bereits beim Lesen der Eingabe auf der universellen Maschine erreicht wird)

3. ein $g$, dass sich nicht in $O(f(n)\cdot log\text{ }f(n))$ befindet. D.h. $g$ hat als obere Schranke nicht $O(f(n)\cdot log\text{ }f(n))$ (der Grund ist, dass sich die durch $f$ beschränkte, zu simulierende Maschine mindestens in $O(f(n)\cdot\text{ }log f(n))$ simulieren lässt. Wäre $g$ noch in der oben angegebenen Schranke, könnten wir nicht entscheiden ob die Sprache aus $ZEIT(g)$ sich in $ZEIT(f)$ befindet).

Wir separieren also die Komplexitätsklassen der beiden Funktionen von einander wenn die oben genannten Voraussetzungen erfüllt sind.

Zeithierarchiesatz:

Sei $g: \mathbb{N}\rightarrow\mathbb{N}$ zeitkonstruierbar, $n\in O(g)$, $f: \mathbb{N}\rightarrow\mathbb{N}, f\in O(g), g\notin O(f(n)\cdot{log\text{ }f(n)})$.

Dann ist $ZEIT(f)\subsetneqq ZEIT(g)$

Damit $ZEIT(f)$ eine echte Teilmenge von  $ZEIT(g)$ ist, müssen auch hier einige Voraussetzungen gelten. Nehmen wir sie auch hier auseinander:

1. Wir haben auch hier ein $g$, dass zeitkonstruierbar ist,

2. ein $n\in O(g)$, $n$ bedeutet hier, dass $g$ mindestens linear wächst

3. ein $f$, dass ${}\in O(g)$ ist ($g$ wächst damit mindestens so schnell wie $f$), während sich das

4. $g$ nicht in $O(f(n)\cdot log\text{ }f(n))$ befindet ($g$ wächst schneller als $O(f(n)\cdot log\text{ }f(n))$).

Wir wir sehen können, sind das fast die selben Vorbedingungen wie für den Separationssatz. Damit $ZEIT(f)$ jedoch eine Teilmenge sein kann, muss sich $f$ zusätzlich in $O(g)$ befinden. Erst dann gilt: $ZEIT(f)\subsetneqq ZEIT(g)$. Was haben wir hier am Ende getan? Wir haben eine Hierarchie zwischen den beiden Komplexitätsklassen geschaffen, so dass $ZEIT(f)$ eine echte Teilmenge von $ZEIT(g)$ darstellt.

Weil es wo schön war: noch einmal den ganzen Spaß mit dem Bandhierarchie- und dem Bandseparationssatz:

Bandseparationssatz:

Sei $g: \mathbb{N}\rightarrow\mathbb{N}$, $g$ bandkonstruierbar, $log\in O(g)$, $f:\mathbb{N}\rightarrow\mathbb{N}$.

Dann gilt $BAND(g)\subseteq BAND(f)\Leftrightarrow g\in O(f)$

Damit $BAND(g)$ eine Teilmenge (im Gegensatz zu "keine Teilmenge" beim Zeitseparationssatz) von  $BAND(f)$ ist und $f$ als obere Schranke für das bandbedarfswachstum $g$ gilt, müssen folgende Voraussetzungen erfüllt sein:

1. ein bandkonstruierbares $g$ ($\tilde{s}_M$, d.h. der maximale Speicher- bzw. Bandbedarf der Maschine muss in der Komplexitätsklasse von $O(g)$ liegen),

2. $log\in O(g)$, $g$ wächst also mindestens logarithmisch und wir haben ein

3. ein $f$ mit Definitions- und Bildmenge aus $\mathbb{N}$.

4. Dazu ist $f$ eine obere Schranke für $g$

Auch hier haben wir eine Separation des Bandbedarfs, genauer der Komplexitätsklassen des Bandbedarfs von Funktionen $f$ und $g$ und können zudem auch sagen, dass die obere Schranke für das Bandbedarfswachstum von $g$ eben $O(f)$ ist. Ist ja auch klar, denn es gilt (wenn die Voraussetzungen erfüllt sind) $BAND(g)\subseteq BAND(g)$.

Kommen wir nun zum Bandhierarchiesatz:

Bandhierarchiesatz:

Sei $log\in O(g)$, $g$ bandkonstruierbar, $f\in O(g)$, $g\notin O(f)$.

Dann gilt $BAND(f)\subsetneqq{BAND(g)}$

Damit $BAND(f)$ also eine echte Teilmenge von  $BAND(g)$ darstellt, kämpfen wir mit den folgenden Voraussetzungen: notwendig sind

1. ein bandkonstruierbares $g$ (siehe oben),

2. $log\in O(g)$, $g$ wächst also mindestens logarithmisch, wir haben ein

3. ein $f\in O(g)$, d.h. $f$ hast $g$ als obere Schranke und

4. ein $g\notin O(f)$, also ist $f$ keine obere Schranke für $g$

Mit dem Hierarchiesatz haben wir es auch hier geschafft eine Hierarchie auf den Komplexitätsklassen des Bandbedarfs herzustellen. Während wir beim Separationssatz durchaus gleiche Mengen haben könnten (z.B. ist $\{1,2,3\}$ eine Teilmenge von $\{1,2,3\}$) , haben wir das beim Hierarchiesatz nicht ($\{1,2\}$ eine echte Teilmenge von $\{1,2,3\}$). Bitte macht euch nochmal den Unterschied klar.

Antwort zum Lernziel: Die Voraussetzungen für Separation und Hierarchie begründen sich in der $TM$, auf denen die Funktion simuliert wird.

Für die Separation von $g$ und $f$ muss $g$ zeitkonstruierbar sein (Schrittzahlfunktion der $TM$ muss noch innerhalb der Schranke der Funktion liegen), min. lineares Wachstum haben (da die Eingabe von der $TM$ gelesen werden muss und wir z.B. beim Lesen von $n$ durch die Unärnotation schon $n$ Schritte verbrauchen) und sich nicht in $O(f(n)\cdot log f(n))$ (da wir die $f$-beschränkte Maschine simulieren müssen und die Simulation bereits in $O(f(n)\cdot log\text{ }f(n))$ erfolgt) befinden.

Bei der Hierarchie haben wir ähnliche Vorbedingungen, müssen aber zusätzlich sicherstellen, dass die zu untersuchende Funktion $f$ innerhalb der Schranke für $g$ liegt.

Die Selbsttestaufgabe aus dem Skript ist hier anschaulich, ich möchte mich daher auch in dem Beitrag daran halten.

Lernziel 3

Anwendung der Sätze zum Beweis von Separationen und echten Inklusionen

Beispiel

$f(n)=\begin{cases}n, &\mbox{falls }n\mbox{ gerade}\\n^3, &\mbox{sonst}\end{cases}$

$g(n) = n^2$

Beide Funktionen sind zeitkonstruierbar. Behauptung:

(1) $ZEIT(f)\subseteq ZEIT(g)$

Wir benötigen hier also unseren Zeitseparationssatz:

Sei $f, g: \mathbb{N}\rightarrow\mathbb{N}$, $g$ zeitkonstruierbar, $n\in O(g)$, $g\notin O(f(n)\cdot\text{ }log f(n))$. Dann ist $ZEIT(g)\nsubseteqq ZEIT(f)$

Fangen wir mit Behauptung (1) an: $ZEIT(f)\subseteq ZEIT(g)$

Wir setzen $g=n$ oder $g=n^3$ je nach Fall. Und $f=n^2$

(im Satz wird ja nicht $ZEIT(f)\nsubseteqq ZEIT(g)$, sondern $ZEIT(g)\nsubseteqq ZEIT(f)$ geprüft).

Vorbedingungen, die wir erfüllen müssen für den Zeitseparationssatz sind also:

1. $g$ muss zeitkonstruierbar sein: check!

2. $g$ muss mindestens lineares Wachstum haben: check!

3. die obere Schranke für $g$ ist nicht $O(f(n)\cdot log\text{ }f(n))$: auch wenn man das sieht, prüfen wir das doch mal:

Fall 1

Wenn $n$ gerade, muss gelten: $n\notin O(n^2\cdot log(n^2))$. Gilt es? Nein!

Fall 2

Ist $n$ ungerade, muss gelten: $n^3\notin O(n^2\cdot log(n^2))$. Gilt dies? Ja! Die Voraussetzung ist hier also erfüllt.

Da bei einem ungeraden $n$ die Voraussetzungen für die Separation gegeben sind, ist $ZEIT(f)\nsubseteqq ZEIT(g)$. Hätten wir nur ein $n$ statt $n^3$, so wäre die Voraussetzung nicht gegeben. Aber so gilt der Separationssatz für ungerade $n$ und damit ist Behauptung (1) falsch.

Antwort zum Lernziel: Siehe oben. Auf zwei gegebene Funktionen $f$ und $g$ kann man die Zeit- und Bandhierarchiesätze anwenden (wenn die Voraussetzungen zutreffen) und so eine Hierarchie oder eine Separierung der Komplexitätsklassen vornehmen.

Lernziel 4

Definition von band- und zeitkonstruierbaren Funktionen

Was ist eine band- bzw. zeitkonstruierbare Funktion? Das Wachstum so einer Funktion entspricht dem Bandbedarf, bzw. der Schrittzahlfunktion eine real existierenden Turingmaschine. Was man sich merken sollte ist, dass zwar alle zeitkonstruierbaren Funktionen bandkonstruierbar sind. Andersherum geht es aber nicht. Das folgt aufgrund des Zusammenhangs zwischen Band und Zeit. Hangeln wir uns an der Definition entlang:

$f: \mathbb{N} \rightarrow\mathbb{N}$ heißt bandkonstruierbar, falls es eine TM $M$ gibt, so dass $\forall n. f_M(0^n) = 0^{f(n)}, \tilde{s}_M\in O(f)$

Was muss vorliegen damit die Funktion bandkonstruierbar ist? $\tilde{s}_M$, d.h. der maximale Speicher- bzw. Bandbedarf der Maschine muss in der Komplexitätsklasse von $O(f)$ liegen.

$f: \mathbb{N} \rightarrow\mathbb{N}$ heißt zeitkonstruierbar, falls es eine TM $M$ gibt, so dass $\forall n. f_M(0^n) = 0^{f(n)}, \tilde{t}_M\in O(f)$

Hier ist es ähnlich. Nochmal zur Erinnerung: $\tilde{t}_M$ ist die maximale Anzahl der Schritte, die die TM $M$ benötigt um bei der Eingabe eines Wertes die Endkonfiguration zu erreichen und $0^n$ ist die Unärnotation von $n$ (z.B. $5 = 00000$).

Nicht vergessen: $t_M \neq \tilde{t}_M$. Ersteres bezeichnet nämlich nur die Anzahl der Schritte bis zur Endkonfiguration bei einer bestimmten Angabe, letzteres die maximale Anzahl der Schritte bei allen Eingaben ($\tilde{t}_M := max\{t_M(x)|x\in \Sigma^n\}$).

Was müssen wir also tun um zu zeigen, dass eine Funktion $f$ zeitkonstruierbar ist? Die Aufgabe im Skript zeigt es relativ anschaulich, dem will ich mich also auch nicht verschließen.

Beispiel: zeigen, dass $f(n) = \lfloor n \cdot \sqrt{n} \rfloor$ zeitkonstruierbar ist.

Wir schauen in die Definition und merken, dass wir eine TM angeben müssen, deren Schrittzahlfunktion für alle Eingaben von $n$ innerhalb der Schranke $O(\lfloor n \cdot \sqrt{n} \rfloor)$ liegt. In dem Beispiel wird auch mit Dualzahlen gerechnet anstatt mit der unären Notation von $n$. Also nicht davon abschrecken lassen, d.h. $d(n)$ ist die Dualnotation von $n$ (z.B. $d(5) = 101$). Lange Rede, kurzer Sinn: es müssen also folgende Voraussetzungen für die Zeitkonstruierbarkeit erfüllt sein:

1. $f_M(0^n) = 0^{f(n)}$, z.B. $f_M(0^5) = 0^{11}$ (die TM berechnet also die Funktion und gibt sie in unärer Notation aus) und

2. $\tilde{t}_M\in O(f)$, die Schrittzahlfunktion der TM liegt innerhalb der Schranke $O(f)$, d.h. $O(\lfloor n \cdot \sqrt{n} \rfloor)$

Nochmal zum selber nachrechnen: $f(\lfloor n \cdot \sqrt{n} \rfloor)$ mit $n = 5 = 0^5 \rightarrow f(5) = 11$, $f(0^5) = 0^{11}$. Die Schritte, die zu der korrekten Berechnung im Skript gemacht werden sind:

1. Berechnung von $a = d(n)$

2. Berechnung von $b= a*a*a$

3. Berechnung von $c=d(\lfloor\sqrt{d^ {-1}(b)}\rfloor)$

4. Ausgabe von $0^{d^{-1}(c)}$

Probieren wir das mal am Beispiel $n = 5$

1. $a = d(5) = 101$

2. $b = 101 * 101 * 101 = 1111101$

3. $c =d(\lfloor\sqrt{d^ {-1}(1111101)}\rfloor) = 1011$

4. Ausgabe von $0^{d^{-1}(1011)} = 0^{11} = 00000000000$

Sieht also gut aus. Damit haben wir eine funktionierende TM für die Funktion und müssen nur noch schauen ob die Schritte bis zur Endkonfiguration, d.h. bis zu unseren Ausgabe auch in der Schranke $O(f)$, d.h. $O(\lfloor n \cdot \sqrt{n} \rfloor)$ liegen:

1. hier brauchen wir $O(n)$ Schritte

2. für die Multiplikation reicht die Schulmethode, welche uns zu $O((log n)^2)$ bringt.

3. mit der Intervallschachtelung kommen wir hier mit $O((log n)^3)$ Schritten aus.

4. für den letzten Schritt, die unäre Ausgabe werden mehr Schritte benötigt als bei den drei Schritten davor: $O(\lfloor n \cdot \sqrt{n} \rfloor)$.

Damit dominiert dieser Schritt die Rechenzeit und wir haben gezeigt, dass $O(f(n)) = O(\lfloor n \cdot \sqrt{n} \rfloor)$ und damit zeitkonstruierbar ist.

Wenn wir das Beispiel nachvollziehen konnten, so ist auch klar geworden, dass z.B. die Funktionen $log n$ und $\lfloor\sqrt{n}\rfloor$ nicht zeitkonstruierbar sind, denn sie benötigen mehr Schritte zur Berechnung als $log n$ und $\lfloor\sqrt{n}\rfloor$ und passen daher nicht in die oberen Schranken, die wir für die Zeitkonstruierbarkeit benötigen.

Antwort zum Lernziel: Für eine Zeit- und Bandkonstruktion bei einer Funktion $f$ müssen wir zeigen, dass die maximale Schrittzahlfunktion $\tilde{t}_M$ und der maximale Speicherplatzbedarf $\tilde{s}_M$ innerhalb der Schranke $O(f)$ liegt. Ist uns das gelungen ist die Funktion $f$ zeit- bzw. bandkonstruierbar.

Lernziel 5

Beschreibung des Beweises von $ZEIT(n)\subsetneqq{ZEIT(n\cdot log\text{ }n)}$

Antwort zum Lernziel: Hier muss ich erstmal passen. Wer eine schöne Beschreibung der Beweisidee hat, bitte melden.

Lernziel 6

Beweis der Beziehungen zwischen den Klassen P, LOGSPACE, PSPACE

Um die Beziehungen zwischen P, LOGSPACE und PSPACE zu verstehen, müssen wir zunächst einmal wissen, was P, LOGSPACE und PSPACE ist. Fangen wir mit der Klasse P an:

$P:=\bigcup_{k\in\mathbb{N}} ZEIT(n^k)$

Was das? Die Klasse $P$ ist die unendliche Vereinigung der Zeitkomplexitätsklassen $ZEIT(f)$. In der Literatur wird sie auch Polynomialzeit genannt. Es bezeichnet die Klasse der effizient lösbaren Probleme. $P$ ist eine Teilmenge von $NP$, d.h. $P\subseteq NP$ (hier kommt auch das berühmte P-NP-Problem her), aber dazu später mehr. Dann haben wir noch:

$PSPACE:=\bigcup_{k\in\mathbb{N}} BAND(n^k)$

Und das ist eine unendliche Vereinigung der Bandkomplexitätsklassen $BAND(f)$. Letztendlich haben wir auch noch:

$LOGSPACE:=\bigcup_{k\in\mathbb{N}} BAND(log)$

$LOGSPACE$ gilt als die kleinste Bandkomplexitätsklasse.

Die Beziehung zwischen diesen ist wie folgt:

$LOGSPACE\subseteq P\subseteq PSPACE$

und

$LOGSPACE\subsetneqq PSPACE$.

Warum das so ist, wird klar wenn man sich die Definition der 4 Komplexitätsklassen anschaut und sich die Beziehungen vor Augen führt:

In $PSPACE$ sind alle Bandkomplexitätsklassen drin, die maximal einen polynomialen Bandbedarf haben. Dass $LOGSPACE$ eine echte Teilmenge davon ist (Unterschied zwischen Teilmenge und echte Teilmenge klar?), sollte einleuchten (logarithmischer Platzbedarf ist zwar ein Teil, aber sicher kleiner als polynomialer Platzbedarf. Daher auch echte Teilmenge und nicht nur Teilmenge). Damit haben wir schon einmal $LOGSPACE\subsetneqq PSPACE$ erklärt.

Durch den Satz aus Kurseinheit 1:

$(1)$ Sei $f:\mathbb{N}\rightarrow\mathbb{N}$. Dann gilt:  $ZEIT(f)\subseteq BAND(f)$

$(1)$ Sei $log\in O(f)$. Dann ist $BAND(f)\subseteq \bigcup_{c\in\mathbb{N}} ZEIT(c^{f(n)})$

haben wir auch unsere Beziehung zwischen $LOGSPACE$, $PSPACE$ und $P$ hergestellt.

Um $(1)$ und $(2)$ nachzuvollziehen müssen wir uns nur noch einmal daran erinnern, dass der Platzbedarf nie größer sein kann als die die Anzahl der maximalen Schritte, die eine Maschine tun kann. Denn in jedem Schritt können wir nur ein Feld beschreiben. Wir beschränken so nicht nur die Maschine, sondern auch ihren Bandverbrauch.

Damit ist $LOGSPACE\subseteq{P}\subseteq PSPACE$.

Wo ist $LOGTIME$? Diese Klasse ist nicht sonderlich spannend, wenn auch vorhanden. In $LOGTIME$ liegt z.B. das Nachschauen in einer sortierten Liste. Wir schauen uns die nicht komplett an, sondern gucken nach einem Element, welches sich irgendwo befinden kann. Die binäre Suche ist ein prominenter Vertreter eines Algorithmus in der Komplexitätsklasse $LOGTIME$.

Der Vollständigkeit halber: die vollständige Beziehung zwischen den einzelnen Komplexitätsklassen ist (nichtdeterministische Problemklassen ausgelassen): $L\subseteq P\subseteq NP\subseteq PSPACE$.

Quelle: Wikipedia

Antwort zum Lernziel: die Beziehungen zwischen den Klassen erfolgen mittels den Hierarchieseätzen für Band und die folgende Teilmengen-Beziehung zwischen Zeit und Band gilt: $ZEIT(f)\subseteq BAND(f)$. Damit bilden wir eine Hierarchie zwischen $LOGSPACE$, $P$ und $PSCAPE$ hergestellt.

Wer noch ein paar Details zum Thema $P-NP$ haben möchte, der kann sich den folgenden Beitrag anschauen und sich schon ein klein wenig auf die nun folgenden Kurseinheiten zu diesem Thema einstimmen.

Wieder gilt: wer Fehler findet, bitte ASAP in die Kommentare oder per Mail damit falsches Zeug nicht zu lange online steht.

Buchempfehlung

Update: auch diesen Beitrag habe ich auf die Lernziele gemünzt und ein paar Fehler behoben.

Bei dieser KE fühlt es sich leicht an wie ein kleiner Bruch. Es ist ein komplett neues Thema und so erschließt sich auf den ersten Seiten nicht unbedingt der Sinn dahinter. Zumindest mir nicht. Erst gegen Ende der Kurseinheit sieht man, wo die Reise hingegangen ist: zu der Berechenbarkeit der reellen Zahlen. Denn vorher haben wir nur die Berechenbarkeit von Wort- und Zahlenfunktionen betrachtet.

Ich werde daher immer ein Stück vorgreifen wenn ich denke, dass es dem Verständnis förderlich ist und mir nicht die Pointe für den Schluss aufheben.

Lernziel 1

Definition der Berechenbarkeitskonzepte, welche durch eien Nummerierung auf einer Menge $M$induziert werden: $\nu$-rekursiv, $\nu$-r.a, $(\nu,{\nu}^{'})$-berechenbar

Wir erinnern uns noch an die Churchsche These? Wenn nicht, bitte nochmal nachlesen. Wird hier noch einmal wichtig werden. Im Grunde geht es hier wieder um die Verschlüsselung von Elementen aus abzählbaren Mengen (hier sei nochmal erwähnt: eine Menge ist abzählbar wenn sie die gleiche Mächtigkeit wie $\mathbb{N}$ hat) durch Zahlen oder Wörter, da wir Zahlen mit Register- und Wörter mit Turingmaschinen berechnen können.

Wir erinnern uns auch an unsere Standardnummerierung $\nu_\Sigma$ oder die Nummerierung der einstelligen berechenbaren Zahlenfunktionen $\varphi$. Diese sind total (überall definiert) und sogar bijektiv (bis auf $\varphi$). Nun führen wir ein weiteres Berechenbarkeitskonzept ein, dass nicht weit weg von dem ist, was wir schon haben. Nehmen wir die Definition also Stück für Stück auseinander.

Es seien $\nu: \subseteq \mathbb{N} \rightarrow M$ und $\nu: \subseteq \mathbb{N} \rightarrow M_1$ Nummerierungen.

Eine Menge $X \subseteq M$ heißt $\nu$-rekursiv, gdw. es eine berechenbare Funktion $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}$ gibt mit:

$g(i)=\begin{cases}1&\text{falls } \nu(i) \in X \\0&\text{sonst }\end{cases}$

für alle $i \in Def(\nu)$.

Das ist das Äquivalent zu unserer Entscheidbarkeit/Rekursivität für Zahlen- und Wortfunktionen. Durch die Nummerierung $\nu$ nummerieren wir alle Elemente aus der Menge $M_1$ und die Funktion $g$ entscheidet für uns ob die gegebene Nummer eines Elements aus $M_1$ uns zu einem Element bringt, dass in der Menge $X$ liegt oder nicht.

Es geht uns also im Endeffekt nur darum die Elemente aus der Menge $X$ zu entscheiden.

Machen wir erst einmal weiter im Text. Anschließend folgt ein Beispiel um es etwas "greifbarer" zu machen.

Eine Menge $X \subseteq M$ heißt $\nu$-rekursiv-aufzählbar, gdw. es eine berechenbare Funktion $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}$ gibt mit:

$g(i)=\begin{cases}existiert&\text{falls } \nu(i) \in X \\div&\text{sonst }\end{cases}$

für alle $i \in Def(\nu)$.

Und hier haben wir das Äquivalent zu unserer Semi-Entscheidbarkeit/rekursiver Aufzählbarkeit.

Wir können zwar immer sagen, ob ein Element zu einer Menge $X$ gehört, haben aber bei der gegenteiligen Aussage ein Problem. Denn hier divergiert die Funktion, sie gibt uns also kein Ergebnis und kann unendlich laufen. Es ist also festgelegt, dass wir im positiven Fall (irgendwann) eine Antwort erhalten, im negativen Fall aber nicht. Prominente Beispiele für die Semi-Entscheidbarkeit sind - wie im verlinkten Beitrag erwähnt - das Halteproblem und der Busy Beaver.

Und nun die letzte Definition für diesen Abschnitt. Hier geht es nicht um eine Menge, sondern um eine Funktion:

Eine Funktion $f \subseteq M_1 \rightarrow M$ heißt $(\nu_1,\nu)$-berechenbar, gdw. es eine berechenbare Funktion $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}$ gibt mit:

$f \circ \nu_1(i) = \nu \circ g(i)$ für alle $i$ mit $\nu_1(i) \in Def(f)$.

Wenn man es ausklammert, hat man vielleicht einen besseren Blick auf die Funktion: $f(\nu_1(i)) = \nu(g(i))$ für alle $i$ mit $\nu_1(i)\in Def(f)$. Okay, das hat nicht unbedingt super geklappt. Diese definition bedeutet, dass eine Menge $(\nu_1,\nu)$-berechenbar ist wenn es ein Verfahren gibt, dass uns zu jeder $\nu_1$-Nummer eines Elements der Definitionsmenge von $f$ eine $\nu$-Nummer der Bildmenge von $f$ berechnet.

Während also die Funktion $f$ auf ihren Mengen (zu einem Definitionswert aus $M_1$ gibt es durch die Funktion einen Funktionswert aus $M$) herumrechnet, kümmern wir uns mit der Funktion $g$ um die Umrechnung der "Nummerierungsnummern" $\nu$ und $\nu_1$ der beiden Mengen $M_1$ und $M$.

Okay, das ist wahrscheinlich nicht sonderlich einleuchtend. Ich würde sagen, wir suchen uns ein nettes Beispiel.

Was wir zum Durchspielen der Definition brauchen sind

• zwei Nummerierungen $\nu$ und $\nu_1$,
• zwei Funktionen $f: \subseteq M_1 \rightarrow M$ (diese Funktion nimmt als Argument ein Element aus der Menge $M_1$ entgegen und gibt uns als Ergebnis ein Element aus der Menge $M$) und
• $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}$ (diese jedoch bekommt als Argument ein Element aus den natürlichen Zahlen $\mathbb{N}$ und gibt uns auch eins als Ergebnis zurück) und
• unsere beiden Mengen $M$ und $M_1$.

Fangen wir einfach mal mit dem Beispiel an und belegen wir unsere Mengen, Funktionen und Nummerierungen mit konkreten Werten:

• $M=\{2,4,6\}$: einfach willkürlich gewählt
• $M_1=\{1,2,3\}$: ebenfalls willkürlich
• $f \subseteq M_1 \rightarrow M: f(x) = 2x$. Willkürlich gewählt. Einzige Bedingung war, dass wir als Definition- und Bildwerte Elemente aus den Mengen $M_1$ und $M$ benutzen müssen. Also habe ich eine Funktion genommen, die Argumente aus $M_1$ auf Ergebnisse aus $M$ abbildet. Ihr könnt einfach mal andere Mengen wählen und die Funktion an diese anpassen. Das Ergebnis ist am Ende gleich.

Wenn wir die Funktion mit unseren Werten aus $M_1$ füttern, so bekommen wir: $f(1) = 2$, $f(2) = 4$ und $f(3) = 6$. Unsere Definitionsmenge $Def(f)$ ist also $\{1,2,3\}$ und entspricht wie gewünscht unserem $M_1$ (die Funktion $f$ ist hier sogar total, denn $Def(f) = M_1$, wie man sieht). Die Bildmenge, unsere Ergebniswerte der Funktion sind $Bild(f) = \{2,4,6\}$ und entsprechen also komplett unserer Menge $M$. Sie ist hier sogar surjektiv (auch rechtstotal genannt), denn $Bild(f) = M$ (jedes Element aus der Menge $M$ wird "getroffen"). Da wir auch noch injektiv (auch linkstotal genannt) sind, ist die Funktion bijektiv. Aber das nur nebenbei.

• $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}: g(x) = 2x$. Diese Funktion muss $f \circ \nu_1(i) = \nu \circ g(i)$ für alle $i$ mit $\nu_1(i) \in Def(f)$ erfüllen. Der Kreis $\circ$ ist ja bekanntlich einfach nur eine Komposition. Es muss also gelten: $f (\nu_1(i)) = \nu(g(i))$. Testen wir das doch gleich mit konkreten Werten. Aber vorher müssen wir unsere Nummerierungen wählen:
• $\nu: \subseteq \mathbb{N} \rightarrow M$. Die Nummerierung von $M$ ist willkürlich gewählt, aber Hauptsache eindeutig und von $\nu_1$ verschieden. Wir nehmen einfach $-12$ für $\nu$, d.h. $\nu(14) = 2$, $\nu(16) = 4$ und $\nu(18) = 6$. Jetzt noch die Nummerierung der Elemente aus der Menge $M_1$.
• $\nu_1: \subseteq \mathbb{N} \rightarrow M_1$. Hier nehmen wir $-6$ für $\nu_1$, d.h. $\nu_1(7) = 1$, $\nu(8) = 2$ und $\nu(9) = 3$. Damit ist auch die Menge $M_1$ nummeriert.

Jetzt können wir mal schauen, ob unsere Funktion $g$ die Bedingung $f \circ \nu_1(i) = \nu \circ g(i)$ erfüllt und probieren alle unsere Werte aus den Mengen $M$ und $M_1$ mal aus:

$\begin{array}{lcl}f(\nu_1(7))&=&f(1)\\{}&=&2\end{array}$

Und nun $g$:

$\begin{array}{lcl}\nu(g(7))&=&\nu(14)\\{}&=&2\end{array}$

Damit ist $f \circ \nu_1(7) = \nu \circ g(7)$ erfüllt. Probiert das doch mal mit den restlichen Werten $8$ und $9$ aus.

Mit dem Beispiel können wir auch die beiden Grafiken nachvollziehen, die im Skript drin stehen (ich habe beide Diagramme ein Stück weiter unten als Textform inkl. Beispiel beschrieben). Diese durch $f \circ \nu_1(i) = \nu \circ g(i)$ induzierte Beziehung bringt uns zu dem im Skript beschriebenen Ausdruck: Das Diagramm kommutiert.

Eine Funktion $f: \subseteq M_1 \rightarrow M$ ist $(\nu_1,\nu)$-berechenbar wenn es ein Verfahren gibt, welches zu jeder $\nu_1$-Nummer eines Elementes $x \in Def(f)$ eine $\nu$-Nummer von $f(x)$ berechnet.

Am obigen Beispiel angelehnt bedeutet es nichts weiter, dass unsere Funktion $f$ dann $(\nu_1,\nu)$-berechenbar ist wenn wir ein Verfahren zeigen können, dass zu jeder $\nu_1$-Nummer (also $,7,8,9$) eines $x \in Def(f)$ (also $1,2,3$) eine $\nu$-Nummer (also $14,16,18$) von $f(x)$ (also $2,4,6$) berechnet. Um es nochmal in Deutsch zu formulieren: wir müssen ein Verfahren angeben, welches uns zu einer gegebenen Zahl $v_1$-Nummer eine $v$-Nummer ausgibt.

Wählen wir z.B. als $\nu_1$-Nummer wieder die $7$, so müssen wir am Ende eine $14$ als $\nu$-Nummer herausbekommen: $\nu_1(7) = 1, f(1) = 2, \nu(2) = 14$. Anhand der Definitionen können wir so einfach ein Verfahren herleiten: $(2(i-6))+12 = 2i$. Damit bekommen wir zu jeder gegebenen $\nu_1$ eines $x \in Def(f)$ die zugehörige $\nu$-Nummer von $f(x)$. Das haben wir in dem Beispiel getan und gezeigt, dass unsere Funktion $f$ $(\nu_1,\nu)$-berechenbar ist.

Diese beiden Vierecke aus dem Skript sehen in Linie dargestellt wie folgt (inkl. Beispiel) aus:

Diagramm: $\mathbb{N}\rightarrow (g)\rightarrow \mathbb{N}\rightarrow (\nu)\rightarrow{M}\leftarrow (f)\leftarrow M_1\leftarrow (\nu_1)\leftarrow \mathbb{N}$

Beispiel: ${7}\rightarrow g(7)\rightarrow 14\rightarrow \nu(14)\rightarrow{2}\leftarrow f(1)\leftarrow 1\leftarrow \nu_1(7)\leftarrow 7$

Diagramm: $i\rightarrow (g)\rightarrow g(i)\rightarrow (\nu)\rightarrow{f(x)}\leftarrow (f)\leftarrow x\leftarrow (\nu_1)\leftarrow i$

Beispiel: $7\rightarrow g(7)\rightarrow 14\rightarrow \nu(14)\rightarrow{2}\leftarrow f(1)\leftarrow 1\leftarrow \nu_1(7)\leftarrow 7$

Beachtet hier bitte die Einschränkung aus dem Skript. Die Funktion $g$ arbeitet nur vernünftig für alle $i$ mit $\nu_1(i) \in Def(f)$. D.h. Das Ergebnis von $\nu_1(i)$ muss im Definitionsbereich unserer Funktion $f$ liegen. Dieser ist wie wir oben gesehen haben ja $Def(f) = M_1$ und $M_1=\{1,2,3\}$. Also muss das Ergebnis von $\nu_1(i)$ $1,2$ oder $3$ sein. Und das geht nur wenn $i \in \{7,8,9\}$ ist. Für alle anderen Werte für $i$ geht das natürlich nicht.

Antwort zum Lernziel: In den vergangenen Kurseinheiten haben wir uns um die Berechenbarkeit auf Zahlen- und Wortfunktionen gekümmert. In dieser Kurseinheit interessieren wir uns auf die Berechenbarkeitsmodelle auf beliebigen Mengen.

Um jedoch eine Berechenbarkeit auf diesen beliebigen Mengen zu induzieren, denn wir können mittels Register- und Turingmaschinen nur auf Zahlen oder Worten rechnen, brauchen wir Nummerierungen dieser Elemente und angepasste charakteristische Funktionen um unsere Definition für Rekursivität und rekursive Aufzählbarkeit auf diese Mengen zu übertragen.

Wir sind auch nicht nur auf eine einzige Nummerierung beschränkt, die uns Definitions- und Wertemenge nummeriert. Durch eine "Übersetzungsfunktionen" können wir diese Nummerierungen ineinander "überführen" und es uns so ermöglichen auf den unterschiedlichen Nummerierungen zweier Mengen rechnen zu können.

Lernziel 2

Nachweis der $\nu$-Rekursivität und $(\nu,{\nu}^{'})$-Berechenbarkeit

Nun haben wie die $\nu$-Rekursivität, -rekursive-Aufzählbarkeit und $(\nu,{\nu}^{'})$-Berechenbarkeit definiert, jetzt wollen wir auch etwas mit unserem Wissen anstellen.

Wollen wir doch mal versuchen das für zwei Beispiele aus dem Skript nachzuweisen.

Aufgabe 1: Nachweis der $(id_{\mathbb{N}},\nu)$-Berechenbarkeit einer Nummerierung $\nu: \subseteq \mathbb{N} \rightarrow M$.

Wir machen uns wieder klar, was wir hier zeigen müssen. Wir müssen zeigen, dass es ein Verfahren gibt, welches zu jeder $id_{\mathbb{N}}$-Nummer eines Elementes $x\in Def(\nu)$ eine $\nu$-Nummer von $\nu(x)$ berechnet. Etwas verwirrend, da die Definition noch ein $f$ verlangt, aber das $f$ ist in diesem Fall einfach nur die Nummerierung $\nu$.

Formal ausgedrückt:

$\nu \circ id_{\mathbb{N}}(i) = \nu \circ g(i)$ für alle $i$ mit $id_{\mathbb{N}}(i) \in Def(\nu)$

(nochmal zur Erinnerung $id_{\mathbb{N}}(k) = k$ für alle $k \in \mathbb{N}$, d.h. $id_{\mathbb{N}}(5) = 5$)

Wir suchen also ein $g$, dass die obige Gleichung erfüllt. Wenn Ihr die Komposition klammert sehr Ihr vielleicht auch schon, was für ein $g$ wir suchen:

$\nu (id_{\mathbb{N}}(i)) = \nu(g(i))$ für alle $i$ mit $id_{\mathbb{N}}(i) \in Def(\nu)$

Schon erkannt, was für ein $g$ wir suchen? Wir wählen als Beispiel wieder unsere Nummerierung $\nu$ von oben ($\nu(14) = 2, \nu(16) = 4,\nu(18) = 6$) und haben bei z.B. $i = 14$ folgende Gleichung (zunächst die linke Seite):

$\begin{array}{lcl}\nu (id_{\mathbb{N}}(14))&=&\nu(14)\\{}&=&2\end{array}$

Wir brauchen die Gleichung hier nur aufzulösen:

Wir müssen also $\nu(g(14)) = 2$ setzen. Was nummeriert mit der $2$ unser $\nu(?)=2$? Genau! Die $14$ wird durch $\nu$ mit der $2$ nummeriert (siehe oben): $\nu(14)=2$. Daher muss unser $g$ die $1$ auf die $14$ abbilden: $g(14)=14$ um die Gleichung zu erfüllen.

Aber jetzt habt Ihr sicher schon gemerkt, welches $g$ wir suchen.

Wir wählen $g=id_{\mathbb{N}}$ und rechnen die rechte Seite aus:

$\begin{array}{lcl}\nu (id_{\mathbb{N}}(14))&=&\nu(g(14))\\{}&=&\nu(14)\\{}&=&2\end{array}$

Passt! Damit ist unser $g$ richtig gefunden und es gilt:

$\nu (id_{\mathbb{N}}(i)) = \nu(id_{\mathbb{N}}(i))$

Die Nummerierung  $\nu: \subseteq \mathbb{N} \rightarrow M$ ist damit $(id_{\mathbb{N}},\nu)$-berechenbar.

Aufgabe 2: zeigen, dass $\mathbb{Z}^+ := \{z\in\mathbb{Z} \mid z > 0\}$ $\nu_{\mathbb{Z}}$-rekursiv ist

Wir schauen nochmal nach oben auf die Definition der $\nu$-Rekursivität und sehen, dass wir eine Funktion $g$ angeben müssen, die für alle $i \in Def(\nu_{\mathbb{Z}})$ entscheidet ob das Element in $\mathbb{Z}^+$ liegt oder nicht.

Die Definition von $\nu_{\mathbb{Z}}$ ist: $\nu_{\mathbb{Z}} : \mathbb{N} \rightarrow \mathbb{Z}$, $\nu_{\mathbb{Z}}<i,j> := i-j$ $\forall i,j \in \mathbb{N}$.

Noch nicht so ganz klar? Kein Problem: schaut euch nochmal den Beitrag zur Cantorschen Tupelfunktion an, insbesondere die Inverse dazu.

Es gilt $\nu_\mathbb{Z}(500)=<27,4>$. Da $(i-j)>0$ gilt, gilt auch $i>j$. Wir geben nun unsere Funktion $g$ an:

$g<i,j>=\begin{cases}1&\text{falls } i > j \\0&\text{sonst }\end{cases}$

Die Funktion ist berechenbar (Ihr könnt ja mal eine Registermaschine angeben, die sie berechnet) und für alle $k \in \mathbb{N}$ gilt: $\nu_\mathbb{Z}(k) > 0\Longleftrightarrow g(k) = 1$. Die Menge ist also $\nu_\mathbb{Z}$-rekursiv.

Damit hätten wir schon fast die Hälfte abgehakt. Ich hoffe es war alles verständlich. Beitrag 2/2 folgt alsbald.

Und wieder ganz wichtig: wer Fehler findet, bitte sofort in die Kommentare damit niemand auf eine ungenaue Fährte gelockt wird.

Antwort zum Lernziel: Für den Nachweis der $\nu$-Rekursivität einer Menge $X$ muss man eine volle charakteristische Funktion $g$ angeben, die zu der Nummerierung $i$ angibt ob das nummerierte Element $\nu(i)$ in der Menge $X$ liegt oder nicht. Der Nachweis der rekursiven Aufzählbarkeit gelingt durch die "halbe" charakteristische Funktion.

Für den Nachweis der Berechenbarkeit benötigen wir ein Verfahren, eine Funktion $g$, dass uns die unterschiedlichen Nummerierungen der beiden Mengen "umrechnet", auf denen die Funktion $f$ eigentlich rechnet (ihre Definitions- und Wertemenge).

Noch ein paar wichtige Definitionen außerhalb der Lernziele, aber nicht weniger wichtig:

Eine weitere, naheliegende Eigenschaft der Nummerierungenen ist auch ihre Transitivität:

Sei $f\subseteq M_1\rightarrow M_2$ $(\nu_1,\nu_2)$-berechenbar und $g\subseteq M_2\rightarrow M_3$ $(\nu_2,\nu_3)$-berechenbar, so ist die Komposition von $g$ und $f$ $g\circ f$ $(\nu_1,\nu_3)$-berechenbar.

Konnte man sich schon fast denken. Braucht sicherlich nicht viele Erklärungen. Man kann direkt sehen, dass wir die Menge $M_2$ als Bindeglied zwischen $f$ und $g$ durch ihre Nummerierung $\nu_2$ haben.

Und nun noch etwas zur Notation:

Eine Notation der Menge $M$ ist eine ggf. partielle, surjektive Funktion $\nu:\subseteq\Sigma^{*}\rightarrow{M}$, wobei $\Sigma$ ein Alphabet ist.

Leuchtet ein. Wir können die Menge $M$ nicht nur nummerieren, wie wir das vorher getan haben und mit Registermaschinen berechnen, sondern wir können diese Menge auch mit Worten über einem Alphabet $\Sigma$ "nummerieren". Nur nennt man das nicht mehr eine Nummerierung, sondern eine Notation!

Weiter geht es im folgenden Beitrag.

Buchempfehlung

Update 6: Große Fehlerkorrektur. Finde ich super, dass Ihr euch die Mühe macht, die Fehler aufzuschreiben. Das hilft dem nachfolgenden Leser ungemein! Danke Walter.

Update 5: Fehlende Marke 4 im Flussdiagramm hinzugefügt. Die Berechnung musste daher geringfügig geändert werden (Danke, Alex).

Update 4: Tippfehler beseitigt in Lernziel 3 nach Kommentar von Carina.

Update 3: Nach dem Einwand von Philipp habe ich das Flussdiagramm abgeändert. Im Skript wird als Ausgabeband 0 verwendet, Band 1 ist das Eingabeband und der Rest sind Arbeitsbänder. Ich habe mich hier nicht so ganz daran gehalten, da es für das Beispiel unwesentlich ist.

Ist aber natürlich nicht schön wenn ich mich nah am Skript bewegen und Details vernachlässige, die das Verständnis erschweren. Daher: Danke für das aufmerksame Lesen Band 0 ist nun das Ausgabeband.

Update: Mittlerweile ist KE7 von TIA bereits fertig.

Update: Hier habe ich bei der Überarbeitung einige Fehler entfernt, die evtl. zu Verständnisproblemen geführt hätten.

Lernziel 1

Definition der Komplexitätsmaße Zeit und Band für Turing-Maschinen

Bevor wir die Komplexitätsmaße definieren können, müssen wir zunächst wissen was Komplexität ist. Hierzu ist im Skript ein schönes Beispiel gegeben: mit der Schrittzahlfunktion haben wir die Güte einer Maschine, bzw. eines konkreten Programms. Wir haben jedoch ein gesteigertes Interesse an der Komplexität des effizientesten Programms für einen Algorithmus. D.h. wir suchen obere (jede Schranke, die über der Schranke eines bereits bekannten Programms für unseren Algorithmus liegt) und untere Schranken (die minimalste Schranke für alle Programme zu unserem Algorithmus).

Zusätzlich dazu wird im Skript der Begriff Sprache definiert:

Sei $M$ eine $TM$ über dem Ein-/Ausgabealphaber $\Sigma$. Dann ist

$L_M := \{x\in\Sigma^{*}\mid f_M(x) = \varepsilon\}$ die von $M$ erkannte Sprache.

Ist $f_M$ total, so sagen wir: $M$ entscheidet die Sprache $L_M$.

Wie wir wissen beinhaltet $\Sigma^{*}$ alle Wörter über dem Eingabealphabet $\Sigma$. Hält die Maschine $TM$ in einem Endzustand wenn ein Wort $x$ aus $\Sigma^{*}$ in diese eingegeben wird, so wird das Wort $x$ von der Maschine $TM$ akzeptiert. Alle von $TM$ akzeptierten Worte aus $\Sigma^{*}$ werden die von $TM$ akzeptierte Sprache $L_M$ genannt.

Erkannte/Akzeptierte Sprachen sind die rekursiv aufzählbaren Sprachen, d.h. sie terminieren ggf. nicht für jede aber in jedem Fall für jede akzeptierte Eingabe. Wir haben also eine Positiv- oder Negativentscheidung für eine akzeptierte Eingabe (aber nicht beides). D. h. die Maschine hält nur bei akzeptierten Eingaben. Bei anderen Eingaben läuft sie ewig weiter. Das Problem dabei ist, dass wir letztendlich nicht wissen, ob eine Eingabe nun tatsächlich erkannt / akzeptiert wird. Evtl. rechnet die Maschine ja noch für die Eingabe...

Die entscheidbaren Sprachen - also bei den Eingaben, wo die Maschine in jedem Fall mit einer Positiv- oder Negativentscheidung terminiert, $f_M$ ist als überall definiert, d.h. total - nennen wir rekursiv. Hier haben wir für jede Eingabe (irgendwann) einen finalen Zustand der Maschine, der uns für eine EIngabe $X$ die Entscheidung mitteilt.

Was sind aber nun Komplexitätsmaße Zeit/Band für $TM$? Eine $TM$ ist ein abstraktes Modell eines Rechners. Mit der Schrittzahlfunktion $t_M$ haben wir unsere Rechenzeit für die Maschine $M$, d.h. $t_M$ ist unsere Zeitkomplexität. Der Bandbedarf ist unser $s_M$, d.h. unsere Bandkomplexität. Sie gibt an wie viele der Felder beim erreichen der Endkonfiguration (d.h. das Ergebnis steht auf dem Ausgabeband) auf den Arbeitsbändern benutzt wurden. Durch die im Skript gemachten Einschränkungen des Befehlssatzes (Ein- und Ausgabeband kann nicht als Arbeitsband missbraucht werden) für die Maschine, brauchen Ein- und Ausgabeband nicht in die Berechnung einbezogen zu werden. Versuchen wir es an einem einfachen Beispiel zur Verdeutlichung.

Beispiel für Band- und Zeitkomplexität

Wir nehmen eine simple Maschine $M$, die uns $f(n) := n+1$ ausgibt.

Funktionsweise: die Maschine tut nichts anderes als die Eingabe von Band 1 (Eingabeband) auf Band 2 (Arbeitsband) zu schreiben, eine 1 hinzuzufügen, dann den Lesekopf wieder an den Anfang von Band 2 zu setzen und seinen Inhalt auf Band 0 (Ausgabeband) zu schreiben. Beachtet: $c$ ist das Anfangs- und $\$$ das Endzeichen. So können wir auf den Bändern von Wortanfang bis Wortende navigieren. Nachdem wir ein Zeichen auf ein Band geschrieben haben müssen wir den Schreibkopf auf Band $0$ auch nicht eine Stelle weiter rücken, da wir im Skript die $TM$ dahingehend erweitert haben, dass das automatisch passiert.

Analysieren wir zunächst die Zeit und nehmen als Eingabe ein $n=2=11$. Nehmt euch am besten Stift und Paper und spielt die Maschine nach. Wir gehen davon aus, dass sich der Lesekopf zu Beginn auf Band 0 bei $c$ befindet, bei Band 1 und 2 jedoch direkt auf dem ersten leeren Feld nach dem Anfangszeichen $c$. Am Ende sollten die Folge der besuchten Marken so aussehen:

0,1,2,3,4,1,2,3,4,1,5,6,7,6,7,6,7,6,8,9,10,11,9,10,11,9,10,11,9,12.

Wenn ich mich nicht verzählt habe sind es genau 30 besuchte Marken.

Fangen wir also mit der Abschätzung an:

• Marke 0 wird immer 1x besucht (1)
• Marken 1, 2, 3 und 4 werden genau $2$ mal besucht und zum Abschluss noch einmal Marke 1 um dann zu Marke 5 zu kommen $(4*2+1) = 9$
• Marke 5 wird immer 1x besucht (1)
• Marken 6 und 7 werden $2*(2+1) = 6$ besucht. Wir haben am Ende unseren Lesekopf auf dem Anfangszeichen $c$ bei Band $2$, wo ja am Ende "$c111\$$" steht. Also laufen wir insgesamt 3 Mal zurück bis wir wieder auf dem Anfangsmarker  $c$ landen. Anschließend wird noch einmal Marke 6 abgefragt und wir kommen auf $7$ Schritte
• Marke 8 wird immer 1x besucht (1)
• Marken 9, 10, und 11 werden $3*(2+1) = 9$ Mal besucht, da wir uns ja auf dem Band 2 3 Mal nach vorne bewegen müssen um den Endmarker $\$$ zu erreichen. Dann wird Marke 9 noch einmal abgefragt und wir sind bei $10$ Schritten
• Marke 12 ist die Abschlussmarke, welche natürlich nur $1$ Mal besucht wird.

Insgesamt sind wir dann also bei 32 Marken, was unserem manuellen Durchlauf entspricht. Hier sieht man direkt ein, dass die Schleifendurchläufe von der Eingabe $n$ abhängen. Ersetzen wir unsere $2$ nun mit $n$, so kommen wir auf die Gleichung:

$1+4n+1+1+2(n+1)+1+1+3(n+1)+1+1=9n+12$.

Das ist unsere - aufgrund der Einfachheit der Maschine ziemlich genaue - Abschätzung der Zeitkomplexität: $t_M(n) = 9n+12$.

Da uns aber in der Laufzeitberechnung die Konstanten kaum interessieren (sie hängen nicht von der Eingabe, sondern nur von der Rechengeschwindigkeit ab), können wir sie streichen. Für uns spielt nur die Komplexität eine Rolle, die von der Eingabe abhängt (zwar bei beliebigen Rechenleistungen vielleicht schneller ist, aber trotzdem gleiche von der Eingabe abhängige Wachstum hat), so dass die Laufzeit unseres einfachen Programmes in die Komplexitätsklasse $O(n)$ fällt und damit ein lineares Wachstum aufweist.

Was ist aber nun mit der Bandkomplexität? Die ist noch einfacher abzuschätzen. Wie sieht denn die bei der Eingabe von $n$ erreichte Endkonfiguration aus? Die Anfangskonfiguration wäre z. B. bei der Eingabe von $n = 2 = 11$: $(0,(c,c11\$,c))$. Die von da aus erreiche Endkonfiguration wäre: $(12,(c111$,c11$,c111$))$. Da wir uns um das Ein- und Ausgabeband nicht kümmern, sondern nur die Arbeitsbänder (davon haben wir nur eines: Band 2) zählen, landen wir bei einem Speicherplatzverbrauch von $n+1$. $s_M(n) = n+1$, was unsere Bandkomplexität in die selbe Komplexitätsklasse befördert wie unsere Laufzeit: $O(n)$.

Fertig!

Antwort zum Lernziel: bei den Komplexitätsmaßen für Turing-Maschinen unterscheiden wir zwischen Band- und Zeitkomplexität. Ersteres ist der Bandverbrauch, der mit $s_M(n)$ bezeichnet wird und die Auslastung der Arbeitsbänder (Eingabe- und Ausgabeband begutachten wir nicht) angibt. Letzteres ist $t_M(n)$ und gibt die Anzahl der Schritte an, die bei der Eingabe von $n$ zur Endkonfiguration führt.

Lernziel 2

Definition der Komplxitätsklassen

Damit sind wir auch schon bei den Klassen angekommen. Oben haben wir die konkrete Komplexität einer Maschine berechnet. Aber was ist wenn wir noch ein paar unsinnige Schleifen in die obige Maschine einbauen, die von der Eingabe $n$ abhängen ? Wir könnten die Berechnung der simplen Funktion $f(n) = n+1$ durch diese Schleifen dann so verlangsamen, dass die Berechnung erst in exponentieller Zeit abgeschlossen wäre. Selbst wenn es totaler Unfug ist.

Ihr ahnt es wahrscheinlich schon: wir haben keinerlei Interesse an der Komplexität einer konkreten Maschine, die unsere Funktion berechnet. Denn davon kann es viele geben. Für uns ist diese Aussage nur in Bezug auf die Funktion selbst spannend: wie komplex (schnell) ist der schnellste Algorithmus, der unsere Funktion berechnet?

Ein Beispiel gefällig? Gerne: Rucksack-Problem

Eine rekursive Implementierung des Algorithmus hat eine Zeitkomplexität aus der Klasse $O(m^n)$ (polynomielles Wachstum) und den Speicherplatzverbrauch von $O(n)$ (lineares Wachstum). Mittels dynamische Programmierung ist es jedoch möglich die Laufzeit auf $O(m*n)$ zu drücken (hierzu bitte den Wikipedia-Artikel studieren, ggf. schreibe ich später auch mal was dazu). Zunächst hatte also unsere Funktion $f_{Rucksack}$ die Komplexität $O(m^n)$. Dann haben wir es geschafft einen Algorithmus (anhand einer Maschine) zu entwerfen, die unsere Funktion $f_{Rucksack}$ in die Komplexitätsklasse $O(m*n)$ brachte. Und wenn wir keinen anderen, effizienteren Algorithmus finden, bleibt sie auch erstmal dort.

Ist nun klar warum wir uns für die maximale/minimale Komplexität der Algorithmen und nicht konkreter Maschinen interessieren?

Antwort zum Lernziel: die Komplexitätsklassen geben an, welche obere Schranke für einen Algorithmus zu erwarten ist und nicht von der konkreten Maschine, vom der der Algorithmus umgesetzt wird. Es interessiert uns also nur der Worst Case. Dieser wird mittels Landau-Notation, auch O-Notation genannt ausgedrückt. In den meisten Fällen ist die Zeit- von höherem Interesse als die Bandkomplexität.

Durch diese Abgrenzung können wir eine Hierarchie auf den Komplexitätsklassen bilden.

Lernziel 3

Zusammenhang zwischen Band- und Zeitkomplexität

Das im Skript beschriebene Phänomen ist der Space Time Trade off. In der technischen Informatik durften wir mit Assembler programmieren und konnten so den Speicher- und Rechenzeitverbrauch unserer Programme konkret nachvollziehen. Der Zusammenhang müsste den meisten daher klar sein: um Speicherplatz zu sparen kann ich z. B. Schleifen ausschreiben. Der Code wird größer aber das Sprungziel der Schleife muss nicht gespeichert werden. Ebenso ergeht es uns mit komprimierten Daten (angelehnt an den Artikel aus der Wikipedia): wir sparen Speicherplatz, vergeuden aber zum Packen und Entpacken Rechenzeit.

Im Skript sind einige Zusammenhänge zwischen Rechenzeit und Speicherbedarf aufgestellt. Es gibt ein Mindestmaß an Speicherplatz, was ein Algorithmus verbraucht und auch ein Maximum.

• $s_M(x) \leq t_M(x) + k$

Da wir Eingabe- und Ausgabeband nicht berücksichtigen ist der Bandbedarf bei der Eingabecodierung festgelegt. Er beträgt die Anzahl der Bänder $k$. Damit ist der Speicherplatzbedarf $S(K_0)$, der Anfangskonfiguration $K_0$ genau gleich $k$. Auch kann er sich in einem Schritt maximal um eines erhöhen, denn wir können ja nur etwas anfügen. Damit sagt der obere Satz nichts weiter aus als: "Der Bandbedarf $s_M$ bei der Eingabe von $x$ ist ${}\leq{}$ der Anzahl der Schritte $t_M$ bei der Eingabe von $x$ plus $k$, eben der Anzahl der Bänder.

• $t_M(x) \leq (lg(x)+1)\cdot {c^{s_M(x)+1}}$

"Die Anzahl der Schritte bis zur Endkonfiguration bei der Eingabe von $x$ ist ${}\leq{}$ der Länge der Eingabe + 1 $\cdot {c^{s_M(x)+1}}$". Wie kommen wir auf $(lg(x)+1)\cdot {c^{s_M(x)+1}}$? Hier müssen wir etwas ausholen:

- $q$ ist die Anzahl der Zustände der Maschine, $g$ die Größe des Arbeitsalphabets + 1. Da wir $q$ Marker haben, haben wir $q$ Zustände.

- Auf dem Eingabeband kann es $lg(x) +2$ Werte für die Kopfposition haben (Länge des Eingabewortes $x$ plus Anfangs- und Endmarker $c$ und $\$$).

- Auf einem Arbeitsband ist die Länge des darauf stehenden Wortes sicher ${}\leq s_M(x)$, d.h. definitiv kleiner/gleich dem kompletten Speicherplatzbedarf am Ende der Berechnung. Damit kann es maximal $s$ Felder auf dem Arbeitsband geben und damit auch $s$ Kopfpositionen. Jedes der Felder kann entweder beschriftet sein oder nicht (wir schauen nach oben: $g$ ist die Größe des Arbeitsalphabets). Diese sind damit durch $s\cdot g^s$ beschränkt.

- Die Möglichkeiten für die Belegung aller Arbeitsbänder ist daher höchstens: ${(s\cdot g^s)}^k$.

Und damit haben wir maximal $q\cdot(lg(x)+2)\cdot{(s\cdot g^s)}^k$ Äquivalenzklassen, was uns zu der obigen Abschätzung bringt: $c := 2q\cdot(2g)^k$.

• $t_M(x) \leq c^{s_M(lg(x))}$

Hier muss ich erstmal passen. Der Beweis erschließt sich mir nicht auf Anhieb. Sobald ich die Zusammenfassung von TIA, KE7 fertig habe werde ich hier nochmal reinschauen. Wer jedoch bis dahin den 3. Teil des Zusammenhangs in klaren Worten ausdrücken kann, kann es bitte in die Kommentare schreiben. Ich pflege das dann sofort ein.

Antwort zum Lernziel: der Zusammenhang zwischen Zweit- und Bandkomplexität begründet sich in dem sog. Time-Space-Tradeoff. Häufig gelingt es uns einen Algorithmus schneller ausführen zu können, was jedoch oft zum Nachteil des Speicherplatzverbrauchs geschieht. Anders herum können wir mit einen höheren Speicherplatzverbrauch durchaus Geschwindigkeitsvorteile erzielen.

Ein prominentes Beispiel ist z.B. der Einsatz von Packern, die Daten komprimieren um Speicherplatz zu sparen, aber Rechenzeit aufwenden, da diese Daten wieder entkomprimiert werden müssen.

Auch gibt es Untergrenzen, z.B. für die Geschwindigkeit: um eine Eingabe der Länge $n$ zu lesen, brauchen wir mindestens $n$ Rechenschritte. Ebenso ergeht es uns mit dem Speicherplatz, denn wir können in jedem Schritt nur ein Feld auf dem Band schreiben. D.h. wir können bei $m$ Schritten bis zur Endkonfiguration nicht mehr als $m$ Felder des Bandes beschrieben haben.

Lernziel 4

Darstellung der Aussage der Bandreduktionssätze und Beweisidee

Bei der Normierung werden (ähnlich wie beim Entfernen der Hilfssymbole) die alten Befehle durch Befehlsfolgen ersetzt. Dabei werden auch die Worte wie gehabt verschlüsselt. Ebenso erhöht sich der Bandbedarf (er wird durch die Mächtigkeit des Arbeitsalphabets der ursprünglichen Maschine bestimmt). Ähnlich verhält es sich mit den Arbeitsbändern: wir können durch Erhöhung des Bandbedarfs die Arbeitsbänder auf Eines reduzieren indem wir die Kopfpositionen durch Markierungen auf dem Band (Spuren) simulieren.

Der Zeit- und Bandbedarf der neuen Maschine kann dann abgeschätzt werden durch:

${t_M}^{'}\leq c\cdot(t_M(x))^2 + c$

${s_M}^{'}\leq c\cdot s_M(x) + c$

Eine Effizienzsteigerung im Bereich Zeit erzielt man hier nur noch mit zwei Arbeitsbändern statt nur einem zur Simulation von $k$ Arbeitsbändern

${t_M}^{'}\leq c\cdot t_M(x)\cdot log\text{ }t_M(x) + c$

${s_M}^{'}\leq c\cdot s_M(x) + c$

Antwort zum Lernziel: Bei der Normierung einer Turing-Maschine, so dass diese nur ein Arbeitsband hat werden alle anderen Arbeitsbänder auf das einzig verbliebene Arbeitsband codiert. Das geschieht in ähnlicher Weise wie bei den Hilfssymbolen: die Symbole aus dem Arbeitsalphabet werden durch Worte verschlüsselt. Bei den Kopfpositionen arbeiten wir mit $+$ und $-$ auf dem Band. Das bringt uns zur oberen Abschätzung wenn wir nur ein Arbeitsband verwenden.

Verwenden wir zwei Arbeitsbänder können wir zumindest im Bereich Zeit die Effizient erhöhen und kommen so zur unteren Abschätzung. Hier werden zusätzlich Teile der Spuren mit dem zweiten Arbeitsband so verschoben, dass die Kopfmarkierungen auf den versch. Spuren stets an der selben Position sind (im Skript ist dazu kein detaillierter Beweis angegeben).

Die Band- und Zeitkomplexität wird durch die Normierung nur durch eine Konstante $c$ erhöht, so dass sie nicht groß ins Gewicht fällt.

Buchempfehlung