Update 3: Nach Olivers Einwand (Danke hier nochmal!) habe ich den Abschnitt über Hilfssymbole erneut überarbeitet.

Update 2: Wow, beim Durchgehen des Eintrags sind mir massive Schnitzer bei den Hilfssymbolen aufgefallen. Hoffentlich sind die jetzt raus. Sorry!

Update: mit dem Eintrag sollten nun alle Lernziele aus KE3 erschlagen worden sein. Ist zwar etwas lang geworden, aber vielleicht hilft es dem ein oder anderen beim Verständnis. Die neuen Erkenntnisse z.B. bzgl. der Hilfssymbole entstammen dem Mentoriat in Hagen mit Herr Dr. Halbach. Ich kann nur ausdrücklich raten diese Mentoriate in Anspruch zu nehmen und auch immer Fragen zu stellen wenn einem etwas nicht klar sein sollte.

Habe bei vielen Mentoriaten gesehen, dass die Leute auf die fragenden Blicke des Mentors 2 Stunden lang immer nur fleißig nicken. Nach dem Mentoriat schaut man trotzdem in die gleichen, ratlosen Gesichter ein stückweit mehr resignierter Komillitonen. Also fragen bis es "Klick!" macht. Auch sind viele Mitstudenten gerne bereit es einem auch mit anderen Worten zu erläutern. Nur keine Scheu, sitzen doch alle im selben Boot

Einleitung

Aber fangen wir an: während in der Literatur zunächst Einband-Maschinen eingeführt werden um sie dann durch Mehrbandmaschinen zu ersetzen wird das in dem Kurs an der FU hier genau anders rum gemacht (wie vieles andere im Skript auch...). Auch werden die Turing-Maschinen oft als 7-Tupel definiert, im Skript haben wir ein 5-Tupel. Solche Dinge machen es - meiner Meinung nach - dem Leser unnötig schwer sich den sehr wichtigen Stoff zu erarbeiten.

Anstatt dass man vielleicht in Zusatzliteratur einen Sachverhalt in anderen Worten verständlicher nachlesen kann, muss man die Definitionen erst in die Definitionen des Skripts überführen. Dafür muss man aber zuerst verstehen, was im Skript denn steht. Hierfür hat man sich aber speziell die Zusatzliteratur besorgt. Da beißt sich die Katze in den Schwanz.

Ich möchte hier versuchen bei der Definition des Skripts zu bleiben und die Parallelen zur "üblichen" Definition zu ziehen damit man auch mit Fremdliteratur arbeiten kann. Ebenso würde ich auch lieber mit Einbandmaschinen starten, statt wie im Skript sofort Mehrbandmaschinen einzuführen um diese dann durch Einbandmaschinen zu ersetzen...

Darstellungsweise: Zunächst jedoch zur Darstellungsweise. Am häufigsten wird die unäre Darstellungsweise für Turingmaschinen verwendet, d.h. eine 5 auf dem Eingabe- oder Ausgabeband besteht aus fünf Einsen $(11111)$. Die binäre Darstellung ist zwar etwas hübscher und in einigen Bereichen durchaus sinnvoll, aber die Formulierung von Algorithmen ist mit der unären Darstellungsweise meist einfacher.

Einbandmaschinen

Im Gegensatz zu Mehrbandmaschinen besitzt diese nur ein einziges Band, welches als Ein- und Ausgabe- sowie Arbeitsband dient. Die Eingabeworte befinden sich hier zu Beginn rechts von Lesekopf und sind nur Trennzeichen getrennt. Links befindet sich die Ausgabe. Während der Berechnung wird die Eingabe dann durch die Ausgabe ersetzt, d.h. gelöscht. Am Ende steht das Ergebnis links vom Kopf.

Im Skript sind die Einbandmaschinen definiert als:

$M=(F,(\Sigma^*)^k,\Sigma^*,EC^{(k)},AC)$

Wir erklären den Spaß hier einfach mal:

• $F$: das Flussdiagramm der Maschine, in der Literatur werden hier oft Zustände und Überführungsfunktionen verwendet
• $(\Sigma^*)^k$: die Menge aller Wörter mit k Elementen über $\Sigma$. k ist hier wieder die Stelligkeit. Statt einem Zeichen, können wir k auch Zeichen lesen. Ist z.B. das Alphabet $\Sigma^* = \{b,a,c\}$, so wäre $(\sum^*)^2 = \{ba,bb,bc,ab,aa,ac,ca,cb,cc\}$ und $"aa" \in (\Sigma^*)^2$.
• $\Sigma^*$: eben das gerade vorgestellte $\sum^*$, d.h. das Alphabet.
• $EC^{(k)}$: die ggf. k-stellige Eingabecodierung auf dem Band, d.h. die Worte, die durch ein Trennzeichen getrennt rechts vom Lesekopf stehen. Dieses Trennzeichen wird in der Literatur oft als ein Teil im Tupel angegeben. In Wikipedia wird z.B. ein Quadrat als Trennzeichen verwendet. Im Skript ist es ein einfaches $B$ für Blank. Sie sieht dann z.B. so aus: $EC^{(3)}(ab,ac,aa) = (\varepsilon,B,abBacBaa)$
• $AC$: die Ausgabecodierung am Ende einer Berechnung, welches links vom Lesekopf ist und nur Symbole aus $\Sigma$ hat. D.h. man ließ meist einfach zurück bis zum ersten Trennzeichen.

Zusätzlich dazu werden die möglichen Operationen definiert:

• gehe ein Feld nach links
• gehe ein Feld nach rechts
• schreibe a direkt unter den Lesekopf
• prüfe ob a unter dem Lesekopf steht

Das $\Gamma$ wird im Skript als Arbeitsalphabet bezeichnet. D.h. es ist $\Gamma := \Sigma \cup \{B\}$, also alle Symbole des Alphabets $\Sigma$ und das Trennzeichen $B$. Diese werden dann auf dem Band verwendet. Zusätzlich dazu werden in der Literatur und in der Wikipedia Zustände (Anfangs- und Endzustand) und Marken, sowie eine Überführungsfunktion definiert.  In unserer Definition ist die Überführungsfunktion das Flussdiagramm, wo auch unsere Zustände (Marken) drin sind. Einfach merken: $\Sigma$ = komplettes Alphabet ohne Trennzeichen, $\Gamma$ = Bandalphabet mit Trennzeichen.

Mit $\beta$ wird im Skript die Funktion bezeichnet, die uns ein Zeichen auf dem Band ausgibt: $\beta(0)$ ist das Zeichen unter dem Lesekopf, $\beta(m)$ das Zeichen auf dem m-ten Feld rechts davon, $\beta(-m)$, auf dem Feld links davon sein. Im folgenden Bild (p ist der Lesekopf) ist z.B. $\beta(0)=t$, $\beta(-2)=f$ und $\beta(1)=b$ auf einem Band.

Die folgenden Ausführungen basieren nicht auf dem Skript, sondern auf dem Buch von Dirk W. Hoffmann. Die Symbole $\Gamma$, $\Gamma^{*}$ sind minimal anders belegt.

Für die Ausführungen zum Hilfssymbollemma unten, geht Ihr bitte wieder von der Definition im Skript aus.

Mehrspurmaschinen

Zwar wird das im Skript nicht so explizit erwähnt, aber wir reden hier auch über Mehrspurmaschinen. D.h. man hat zwar $k$ Spuren, aber nur einen Lese- und Schreibkopf und somit auch nur ein Band und damit eine $k$-stellige Einbandmaschine. Wir können nur, bei z.B. 3 Spuren, das Tripel lesen. Die $k$ Eingabeworte der Einbandmaschine, welche nur durch ein Trennzeichen getrennt sind, finden sich bei der Mehrspurmaschine nun in $k$ Spuren wieder. In jeder Spur befindet sich somit ein Eingabewort.

Haben wir z.B. folgende Belegung auf den Spuren mit dem Alphabet $\Sigma = \{a,b,c\}$ und dem Arbeitsalphabet $\Gamma = \{a,b,c,B\}$:

So lesen wir $(c,c,B)$ wenn der Lesekopf über der 3. Spalte steht. Wir haben keine 3 Leseköpfe, die wir justieren könnten und müssen das vollständige Band bewegen. Solche Maschinen lassen sich leicht durch Einbandmaschinen simulieren, indem wir das Alphabet $\Sigma$ auf $\Sigma^3$ erweitern und fortan $(c,c,B)$ ein Element, also ein einzelnes Zeichen, aus unserem neuen Alphabet $\Sigma^3$ auf einem einzigen Band ist, d.h. alle Tripel aus den Zeichen a, b, c und dem Blank B bestehen. Damit blähen wir das Alphabet natürlich deutlich auf. Die Restriktion mit den sich nicht bewegenden Köpfen werden wir in den Mehrbandmaschinen entfernen.

Die Mehrspurmaschine mit $k$ Spuren können wir also durch eine $k$-stellige Einbandmaschine simulieren:

Die Restriktion mit den sich nicht bewegenden Köpfen werden wir in den Mehrbandmaschinen entfernen.

Mehrbandmaschinen

Die Mehrbandmaschine besitzt, ähnlich zu den Registermaschinen, folgende Grundfunktionen (welche mittels eines Flussdiagramms und so auch mittels einer Registermaschine nachgebildet werden können):

• gehe auf Band i ein Feld nach links
• gehe auf Band i ein Feld nach rechts
• schreibe a auf Band i direkt unter den Kopf
• prüfe ob a unter dem Lesekopf auf Band i ist

Ausgabeband ist das Band mit der Nr. 0, Bänder $1-k$ sind Eingabebänder. Auf jedem Eingabeband steht eines der $k$ Worte. Man sieht hier sofort, dass wir nun bewegliche Leseköpfe haben, da sie sich auf den unterschiedlichen Bändern unabhängig voneinander bewegen können. Wir können fortan Operationen auf einem Band unabhängig von den anderen Bändern durchführen.

Merksatz: Einbandmaschinen haben nur ein einziges Band, welches als Ein- und Ausgabeband dient. Dort stehen die $k$ Worte durch ein Trennzeichen getrennt auf dem einzigen Band. $k$-stellige Einbandmaschinen können Mehrspurmaschinen mit $k$ Spuren simulieren. Mehrspurmaschinen haben zwar auch nur ein Band, welches jedoch in $k$ Spuren unterteilt ist. Hier gibt es keine beweglichen Lese-/Schreibköpfe. Mehrbandmaschinen verfügen über mehrere Bänder, die sich unabhängig von einander bewegen können und somit über bewegliche Lese-/Schreibköpfe verfügen. 

Lange Rede, kurzer Sinn: Mehrspurmaschinen mit $k$ Spuren können durch das Aufblähen des Alphabets mit $k$-stelligen Einbandmaschinen simuliert werden. Mehrbandmaschinen können wiederum durch Mehrspurmaschinen simuliert werden und letztendlich in eine $k$-stellige Einbandmaschine überführt werden. Dabei werden Markierungen (in der Literatur sind es oft zusätzliche Spuren) der Zeichen für die Position des virtuellen Lese-/Schreibkopfs pro Spur verwendet. 

Beweis der Berechnungsstärke

Die Mehrband-, Mehrspur- und die Einbandmanschinen haben die gleiche Berechnungsstärke. D.h. wir können Mehrbandmaschinen (mit beweglichen Leseköpfen) mit $k$ Bändern durch Mehrspurmaschinen simulieren. Die Mehrspurmaschinen können als Einbandmaschinen formuliert werden. Den Lernzielen nach sollte man den Beweis nachvollziehen und seine Grundidee erläutern können. Der Beweis im Skript basiert auf der gleichen Grundidee, visualisiert die Darstellung der beweglichen Köpfe jedoch sehr bescheiden. Ich werde die Idee des Skripts am Ende aber dennoch kurz skizzieren. Für das Verständnis halte mich aber erstmal an die Zusatzliteratur.

Falls jemand etwas findet, der den Beweis im Skript verständlicher formuliert als das Skript selbst: bitte melden!

Mehrspurmaschine als Einbandmaschine

Hier wollen wir aus einer $k$-stelligen Einbandmaschine (es ist ja ein einziges Band, die Stelligkeit wird aber in "Spuren" dargestellt. Ggf. gibt es noch ein Ausgabeband 0) eine $k$-stellige Turingmaschine mit einem Band (ohne Spuren) basteln. Ist ja kein Problem, da wir hier einfach nur das Alphabet aufblähen müssen. Die Operationen bleiben fast gleich, nur dass sie jetzt nicht auf Spuren, sondern auf einem $k$-Tupel operieren.

1. Als erstes die Anpassung der Eingabe: man kopiert alle Eingabeworte der $k$ Spuren auf das Ausgabeband der Maschine. Beispiel: siehe folgendes Bild.
2. Die Funktionen "L", "R", "a", "a?" werden dann durch "0:L", "0:R", "o:a" und "0:a?" ersetzt, da sie nun nur auf Ausgabeband 0 durchgeführt werden.

Damit haben wir eine $k$-stellige Bandmaschine (bei $k > 1$ auch Mehrspurmaschine genannt) mit einer $k$-stelligen Turingmaschine und nur einem einzigen Band simuliert. Die unbeweglichen Leseköpfe machen es uns hier einfach.

Mehrbandmaschine als Mehrspurmaschine

Und nun anders herum, was etwas schwieriger ist: die Konstruktion einer $k$-stelligen Einbandmaschine (also nur ein Band, aber $k$ Spuren), welche die selbe Funktion der Mehrbandmaschine mit $k$ Bändern berechnet:

Soweit so unklar. Wir haben hier das Problem der beweglichen Leseköpfe. Während wir bei der Mehrbandmaschine oben die Leseköpfe auf dem 2. Feld in Band 1 (a) und auf dem 3. Feld in Band 2 (a) haben könnten, können wir das auf unserer Einbandmaschine aber nicht darstellen. Was also tun? In der Literatur wird hierfür für jedes Band eine neue Spur erstellt, welche alle unterschiedlichen Positionen der Leseköpfe auf dem Band darstellt. Wir tun also folgendes:

1. wir speichern die Position der Leseköpfe einer Spur (Datenspur) auf einer zusätzlichen Spur (Positionsspur).
2. wir erweitern unser Bandalphabet $\Gamma$ in ein neues: unser $\Gamma^{*}$. Zusätzlich zu den Einzelsymbolen im Bandalphabet $\Gamma$ werden dann alle Kombinationen der Zeichen auf den Bändern hinzugefügt.
3. wir simulieren den Befehl für Band $i$ auf unserer Spur $i$.

Im oberen Bild sind die Leseköpfe für Band 1 und 2 auf den ersten Eingabeworten positioniert. Wie ist nun der Ablauf? Zunächst befindet sich das Band ganz am Anfang, d.h. es steht ein $B$ auf jeder Spur (auch wenn ich das $B$ in der ersten Spur/im ersten Band im Bild oben unterschlagen habe, zu faul ein neues zu malen). Wir haben nun z.B. einen Befehl, der auf Band 1 das erste $a$ durch den Wert ersetzen soll, der unter dem Lesekopf auf Band 2 steht. Anschließend soll auf beiden Bändern ein Schritt nach rechts gemacht werden.

Da wir die Leseköpfe nicht mehr unabhängig von einander bewegen können, wird das Band nach rechts gespult bis die beiden Positionsmarkierungen für Spur 1 und 2 gefunden wurden. Die Werte merkt sich die Maschine und führt nun den Befehl statt auf Band 1 nun auf Spur 1 aus. Anschließend werden die Positionsmarkierungen wie gewünscht auf beiden Bändern um eins nach rechts verschoben. Das folgende Bild visualisiert diese Operation auf dem Band.

Soll der nächste Befehl durchgeführt werden, so wird das Band wieder nach rechts gespult bis die Positionsmarkierungen gefunden wurden, der Befehl ausgeführt und die Positionsmarkierungen erneut verschoben. Am Ende steht das Ergebnis auf der 1. (oder einer speziell dafür vorgesehenen) Spur links vom Lesekopf und das Band muss nur noch zurückgespult werden.

Skriptbeweis

Der Beweis im Skript verwendet keine zusätzlichen Spuren, sondern markiert das Zeichen, über welchem der Kopf steht mit einem Querstrich, z.B. $\overline{a}$.  Damit werden z.B. aus dem Symbol $(1,0)$ in der Mehrbandmaschine, wo der Kopf auf $1$ oder $0$ stehen kann nun die folgenden Symbole: $(1,0), (\overline{1},0), (1,\overline{0}), (\overline{1},\overline{0})$ für die Positionierung der virtuellen Leseköpfe. Damit haben wir eine massive Vergrößerung unseres Bandalphabets.

Das Gleiche haben wir im Beweis von oben. Überführen wir die Mehrspur- nun in eine Einbandmaschine, so ist unser Alphabet ebenfalls erweitert: aus $(a,B)$ wird dann $(a,B,b,B), (a,\#,b,B), (a,B,b,\#), (a,\#,B,\#)$.

Alles in allem: die Simulation der Mehrband- in einer Einbandmaschine erfolgt auf Basis eines vergrößerten Alphabets für die Darstellung der Position der Leseköpfe auf den simulierten Bändern.

Beweis der Turing-Berechenbarkeit von Funktionen

Um zu beweisen, dass eine Funktion von der Turingmaschine berechnet wird tut man das gleiche, was man bereits bei Registermaschinen getan hat. Man behauptet, dass das aufgestellte Flussdiagramm (oder die Zustandsübergangstabelle) genau das tut und von einer gegebenen Eingabecodierung auf die gewünschte Ausgabecodierung führt.

Anschließend werden mittels vollständiger Induktion Annahme und Behauptung aufgestellt und das Flussdiagramm entsprechend oft durchgespielt. Am Ende muss dann die Behauptung rauskommen. Man sollte nicht vergessen alle Eingabefälle durchzuspielen.

Schaut dazu einfach mal in den Beitrag für die Einzelschrittfunktion und den Beweis der Addition mittels vollständiger Induktion.

Hilfssymbole

Den Lernzielen nach sollte man den Beweis verstehen, dass man auch ohne Hilfssymbole auskommt. Wir wir oben gesehen haben müssen wir das Alphabet massiv erweitern wenn wir eine Mehrbandmaschine durch eine Mehrspur- und dann durch eine Einbandmaschine simulieren wollen. Diese zusätzlichen Symbole, welche nicht in dem ursprünglichen Arbeitsalphabet inkl. dem Trennzeichen $B$ drin sind werden Hilfssymbole genannt.

Verwendet man wie im Skript-Beweis für die Kopfpositionen markierte Zeichen statt $\#$, so müssen wir diese markierten Zeichen ($\overline{1}$ z.B.) mit in das neue Arbeitsalphabet nehmen. Aber nicht die einzelnen Zeichen, sondern Kombinationen davon.

Beispiel

Besteht unser Alphabet nur aus $\Sigma := \{a,b\}$, unser Arbeitsalphabet somit aus  $\Gamma := \{a,b,B\}$ und wir simulieren unsere Mehrbandmaschine mit $2$ Bändern durch eine Einbandmaschine, so haben wir eine massive Erweiterung unseres Arbeitsalphabets: Ds neue Alphabet $\Gamma^{'}$ ist eine Kombination aus $\Gamma^{'}=\Gamma\cup(\Gamma\cup\overline{\Gamma})^l$, wobei $l$ die ursprüngliche Anzahl der Bänder ist.

Konkret

Haben wir unser $\Gamma := \{a,b,B\}$ und $2$ Bänder, die wir zusammenschmelzen müssen, so sieht unser $\Gamma^{'}$ wie folgt aus:

$\begin{array}{ll}\Gamma^{'}&=\{a,b,B\}\cup(\{a,b,B\}\cup\{\overline{a},\overline{b},\overline{B}\})^2\\{}&=\{a,b,B\}\cup(\{a,b,B,\overline{a},\overline{b},\overline{B}\}\times\{a,b,B,\overline{a},\overline{b}\overline{B}\})\\{}&=\{a,b,B,aa,ab,aB,...,\overline{B},\overline{B}\}\end{array}$

Aus $3$ Zeichen unseren Urspungs-Bandalphabets sind nun insg. $39$ neuen Zeichen geworden.

Achtung: seht z.B. $a\overline{B}$ nicht als Kombination von $a$ und $\overline{B}$ an, sondern als einzelnes Zeichen. Wir verwenden $a\overline{B}$ weil es leichter lesbar ist, wir hätten auch ein chinesisches Schriftzeichen dafür verwenden können, denn es ist wirklich nur ein einzelnes Zeichen aus unserem neuen Arbeitsalphabet $\Gamma$.

Anstatt, dass nun Worte mit $\{a,b,B\}$ auf unserem Band stehen, bestehen sie aus $\{a,b,B,aa,ab,aB,...,\overline{B},\overline{B}\}$.

Mit zwei Bändern uns zwei Zeichen haben wir bereits $39$ neue Zeichen. Mit drei Bändern hätten wir $219$, mit vier bereits $1299$. Etwas viel, nicht? Was können wir dagegen tun? Das Hilfssymbollemma anwenden!

Wie werden wir die neuen Zeichen wieder los? Kommen wir denn nicht mit unserem ursprünglichen Arbeitsalphabet aus? Doch! Wir codieren mit den Zeichen aus unserem Ursprungsalphabet einfach unsere insg. $39$ Zeichen des neuen Arbeitsalphabets.  Wie? Wir variieren einfach die Länge!

Wie viele Kombinationen der Zeichen aus dem Alphabet $\Sigma$ bekommen wir mit der Länge $1$ dargestellt? Genau $2^1$: $a,b$. Und Länge 2? Genau $2^2$: $aa,ab,ba,bb$. Welche Länge brauchen wir um unsere $39$ Zeichen darstellen zu können? Für die Darstellung der Zahl $39$ in binär reichen uns $6$ Bit, also $2^6=64$ ($2^5=32$ wäre uns zu klein).

Also wählt euer $m$ für die Länge $n^m$ ($n$ ist die Anzahl der Zeichen im Ursprungs-Zeichensatz) entsprechend, damit ihr mindestens so viele Kombinationen aus den Zeichen aus $\Sigma$ habt um eure alten und neuen Symbole damit zu codieren.

Wir brauchen das riesen Arbeitsalphabet mit den Hilfssymbolen damit nicht mehr und bleiben durch die neue Form der Codierung bei geschmeidigen $\{a,b,B\}$. Nur die Länge ist halt ein Stück größer geworden. Eine willkürliche Codierung der $39$ Symbole unseren ursprünglich aufgeblasenen Bandalphabets würde z.B. so aussehen können:

$a\rightarrow aaaaaa$

$b\rightarrow bbbbbb$

$B\rightarrow aaaaab$

$aa\rightarrow aabbbb$

$ab\rightarrow aaabbb$

$aB\rightarrow aaabba$

$a\overline{a}\rightarrow aabaaa$

$a\overline{b}\rightarrow abbaaa$

$...$

$\overline{B}\overline{B}\overline{B}\rightarrow ababab$

Done.

Wir können also beliebige Zeichen mittels nur zwei Symbolen codieren. Genau das besagt das Hilfssymbollemma:

Zu jeder Bandmaschine $M$ mit Ein/Ausgabealphabet $\Sigma$ gibt es eine Bandmaschine $M^{'}$ mit dem Arbeitsalphabet $\Gamma^{'}=\Sigma\cup\{B\}$, so dass $f_M=f_{M^{'}}$ gilt.

Wahrscheinlich ist euch noch nicht ganz klar, warum das so wichtig ist.

Es ist eig. ganz einfach: Wir haben uns hier auf $a$ und $b$ als Ein/Ausgabealphabet versteift. Wir können aber auch $\Sigma=\{1,0\}$ nehmen. Nun können wir mit dem Lemma beliebige Zeichen eines Arbeitsalphabets auch mittels $1$ und $0$ codieren und uns nur noch darauf beschränken. Ab hier übernehmen dann unsere Computer, denn sie kennen nur Strom an ($1$) und Strom aus ($0$).

Fazit: damit haben wir nun alle Lernziele aus der Kurseinheit durch. Wer noch Fragen hat oder grobe Schnitzer findet: ab in die Kommentare!

Update 4: Rechenfehler bei Umkehrfunktion, statt $1218$ ist $1185$ richtig. Danke Marion.

Update 3: Tippfehler, statt $q(500)$ muss das nun $q(39)$ heißen. Danke Christian.

Update 2: meine Güte, wo war ich mit meinen Gedanken? Nach mehreren Hinweisen von Martin und David z. B. scheint die Tupelfunktion nicht ganz richtig definiert gewesen zu sein. Ich weiß ehrlich gesagt auch nicht mehr, wo ich sie her hatte. Nundenn, ist nun wieder aktuell, so definiert wie in der Wikipedia und im Skript und müsste korrekt sein.

Die Cantorsche Tupelfunktion ist eigentlich ein sehr nettes Werkzeug und relativ einfach zu verstehen. Daher wird dieser Beitrag wahrscheinlich eher kurz ausfallen. Martin hat mich auf die Idee gebracht und da mir die Definition der Funktion nicht mehr so geläufig war: warum also nicht?

Die Paarungsfunktion $\pi : \mathbb{N}^2 \rightarrow \mathbb{N}$ macht folgendes: es weist einem Tupel (z.B. (2,6)) einen eindeutigen Wert zu. Aus diesem Wert kann man das Tupel wieder zurückgewinnen. Sie ist somit umkehrbar, d.h. bijektiv und total. Eig. eine ziemlich coole Sache (ja, ich habe eine durchaus fragwürdige Definition von "cool"). Wozu brauche ist das überhaupt? Z.B. für folgendes:

Mächtigkeit von Mengen

Nehmen wir einfach mal zwei Mengen $M_1$ und $M_2$. Zwei Mengen sind gleichmächtig (d.h. es sie beinhalten die gleiche Anzahl an Elementen) wenn es eine bijektive Abbildung $f : M_1 \rightarrow M_2$ gibt. Die Bijektivität der Abbildung ordnet jedem Wert aus der Definitionsmenge $M_1$ genau einen Wert aus der Wertemenge $M_2$ zu. Nicht mehr und nicht weniger. Gibt es diese Abbildung, so gilt jede unendliche Menge als abzählbar wenn die Mächtigkeit von M der Mächtigkeit von $\mathbb{N}$ entspricht ($\left|M\right| =\left|\mathbb{N}\right|$).  Tut sie das nicht ($\left|M\right| \neq\left|\mathbb{N}\right|$), ist sie überabzählbar.

Z.B. sind die Mengen

$M_1 = \{a,z,d\}$ und $M_2 = \{5,1,9\}$ gleichmächtig ($\left|M_1\right| = \left|M_2\right|$).

Wir nummerieren die Elemente einer Menge durch die Elemente der anderen Menge. Wie, ist egal. Hauptsache es gibt eine Nummerierung. Ein schönes Beispiel ist die Nummerierung der ganzen Zahlen $\mathbb{Z}$ (...,-2,-1,0,1,...) durch die natürlichen Zahlen $\mathbb{N} (0,1,2,3,...)$ aus dem Buch von Dirk. W. Hoffmann. Intuitiv scheint die Menge der ganzen Zahlen größer, es sind schließlich auch negative Zahlen dabei. Ist sie aber nicht. Eine Nummerierung könnte z.B. wie folgt aussehen: $f:\mathbb{Z} \rightarrow \mathbb{N}$ mit:

$f(x) = \begin{cases} -2x, & \mbox{ falls } x<0\\ 2x+1, & \mbox{ falls } x\geq 0\end{cases}$

$f(-5) = 10$ und $f(5) = 11$. Da es eine bijektive Abbildung ist, können wir daraus auch eine Umkehrfunktion $f^{-1}:\mathbb{N} \rightarrow \mathbb{Z}$ basteln mit:

$f^{-1}(x) = \begin{cases} -x/2, & \mbox{ wenn x gerade }\\ (x-1)/2, & \mbox{ wenn x ungerade}\end{cases}$

$f^{-1}(10) = -5$ und $f^{-1}(11) = 5$.

Damit haben wir eine eindeutige Nummerierung und Umkehrabbildung gefunden.

Die Tupelfunktion

Aber wir sind nicht nur in der Lage einem Tupel (z.B. (2,3)) eine eindeutige Nummer zu vergeben. Wir können die Zahl sogar einem Tripel (z.B. (5,3,9)) und einem Quadrupel (z.B. (7,4,9,1) und ... ach, Ihr wisst worauf ich hinaus will. Hierbei hilft uns die Cantorsche Paarungsfunktion. Sie ist definiert als:

$\pi_\mathbb{N}(x,y) = \sum_{i=0}^{x+y} i+y={{1}\over{2}}(x+y)(x+y+1)+y$

Um auch Tripel zu erfassen, ist die Funktion definiert als:

$\pi_\mathbb{N}^3(x,y,z)=\pi_\mathbb{N}(\pi_\mathbb{N}(x,y),z)$

Wir können den Gedanken weiterspinnen und landen so bei der allgemeinen Definition:

$\pi^1_\mathbb{N}(x_1) := x_1$

$\pi^{n+1}_\mathbb{N}(x_1,...,x_n,x_{n+1}) := \pi_\mathbb{N}(\pi^{n}_\mathbb{N}(x_1,...,x_n),x_{n+1})$

Beispiel gefällig? Sicher doch!

Beispiel: $\pi^{4}_\mathbb{N}(5,3,9,1)$

Wir lösen zunächst auf und rechnen dann aus. Die exemplarische Nebenrechnungen für das erste Tupel ist unter dem Rechenweg damit es nicht zu unübersichtlich wird:

$\begin{array} {lcl}\pi^{4}_\mathbb{N}(5,3,9,1)&=&\pi_\mathbb{N}(\pi^{3}_\mathbb{N}(5,3,9),1)\\{}&=&\pi_\mathbb{N}(\pi_\mathbb{N}(\pi_\mathbb{N}(5,3),9),1)\\{}&{}&\mbox{(nun }\pi_\mathbb{N}(5,3)\mbox{ ausrechnen: siehe Nebenrechnung)}\\{}&=&\pi_\mathbb{N}(\pi_\mathbb{N}(39,9),1)\\{}&{}&\mbox{(jetzt }\pi_\mathbb{N}(39,9) \mbox{ ausrechnen)}\\{}&=&\pi_\mathbb{N}(1185,1)\\{}&{}&\mbox{(als letztes noch }\pi_\mathbb{N}(1185,1)\mbox{)}\\{}&=&703892\end{array}$

(Korrektur! Danke Marion)

* Nebenrechnung 1:

$\begin{array} {lcl}\pi_\mathbb{N}(5,3) &=&{{1}\over{2}}(5+3)(5+3+1)+3\\&=&{{1}\over{2}}(25+15+5+15+9+3)+3\\&=&{{1}\over{2}}(72)+3\\&=&39\end{array}$

Tada! Ist doch eig. ganz einfach. Es sei denn man macht es wie ich und verrechnet sich dauernd bis man die Formel in Wolfram alpha eingibt

Update: Umkehrfunktion

Da wir in der theoretischen Informatik Teil B auch die Umkehrfunktion brauchen, schreibe ich diese der Vollständigkeit halber mal auf. Martin hat ja einen schönen Link gepostet. Nehmen wir an wir suchen also die Tupel zu $z = 39$, d.h. $\pi(39)$. Das sind zunächst die 4 Formeln, die wir dazu brauchen (frech geklaut aus der Wikipedia):

$q(z) =\lfloor{\frac{\sqrt{8\cdot z+1}-1}{2}} \rfloor$
$f(w) =\frac{w\cdot(w+1)}{2}$
$\pi_2(z) = z - f(q(z))$
$\pi_1(z) = q(z) - \pi_2(z)$

Setzen wir unser $z = 39$ einfach mal ein und rechnen das aus:

$q(39) = \lfloor {\frac{\sqrt{8\cdot 39+1}-1}{2}} \rfloor = 8$
$f(8) = \frac{8\cdot (8+1)}{2} = 36$
$\pi_2(39) = 39 - 36 = 3$
$\pi_1(39) = 8 - 3 = 5$

Und damit $\pi(39) = <5,3>$. That's it (Danke Martin!).

Update: Korrektur des Schleifenfehlers beim Loop-Programm (Danke Dennis).

Mit der primitiven Rekursion haben wir eine echte Teilmenge der berechenbaren Funktionen bereits beschrieben. Und zwar, um genau zu sein, alle totalen Funktionen. D.h. sie sind überall definiert (aber nicht alle totalen Funktionen sind primitiv rekursiv: siehe Ackermann-Funktion) und haben daher für jedes $x$ in $f(x)$ einen Funktionswert und somit endlich viele Rekursionsaufrufe, d.h. eine feste Schachtelungstiefe, was die Ackermann-Funktion z.B. nicht hat. Daher Achtung:

Jede primitiv rekursive Funktion ist total, aber nicht jede totale Funktion ist primitiv rekursiv!

Wir möchten nun aber alle berechenbaren Funktionen haben. Auch die, die nicht überall definiert sind wie z.B. die Wurzelfunktion (diese ist nur auf Quadratzahlen definiert), die partielle Subtraktion oder der Logarithmus zur Basis zwei (nur für 2-er-Potenzen definiert). Was also tun?

Dazu reichen die 3 im vorherigen Beitrag vorgestellten Grundoperationen (konstante Funktion, Projektion und Nachfolgefunktion) im Zusammenspiel mit den Konstruktionsprinzipien der Komposition und primitiver Rekursion aber nicht aus. Wir schaffen es nicht mit den Werkzeugen der primitiven Rekursion (und damit ein LOOP-Programm) zu beschreiben, welches eine noch unbekannte Anzahl an Schleifendurchläufen vorzuweisen hat. Beispiel folgt gleich.

Um die Klasse der berechenbaren Funktionen nun zu erweitern müssen wir unseren Werkzeugkasten entweder mit neuen Grundoperationen aufstocken oder ein neues Konstruktionsprinzip einführen, welches die Möglichkeit mit einschließt, dass eine Berechnung nicht terminiert, d.h. irgendwo nicht definiert ist (im Gegensatz zur primitiven Rekursion), da wir die Anzahl der Schleifendurchgänge nicht kennen. Wir entscheiden uns für letzteres, da es ausreicht und führen den $\mu$-Operator ein. Es gibt den beschränkten und den unbeschränkten $\mu$-Operator. Beide tun das selbe, ersterer jedoch auf einem abgeschlossenen Intervall. D.h. wir haben eine vorher definierte Anzahl an Schleifendurchläufen, damit ein LOOP-Programm und somit letztendlich eine primitive Rekursion. Haben wir keine vorher festgelegte Anzahl an Durchläufen und kann deswegen das komplette Programm auch garnicht anhalten, so sprechen wir vom unbeschränkten $\mu$-Operator.

Wenn man aus der programmiertechnischen Brille schaut, hätte man folgende Fälle:

• 1. beschränkter $\mu$-Operator (unser h im Code):

m:=0;

WHILE f(x1,..,xk,m) NOT 0 AND m <= y DO

  m:=m+1;

  h:=m;

END;

Beschränkung ist rot markiert.

• 2. unbeschränkter $\mu$-Operator (unser h im Code):

m:=0;

WHILE f(x1,..,xk,m) NOT 0 DO

  m:=m+1;

  h:=m;

END;

Hier fehlt die Beschränkung gänzlich. Die Suche ist im schlimmsten Fall endlos. Das Ändert jedoch nichts an der Berechenbarkeit der Funktion und ist uns somit egal.

Wir definieren hier den unbeschränkten $\mu$-Operator zunächst formal und erklären es dann:

$\mu f(x_1,...,x_n):=min\begin{cases} {} & f(m,x_1,...,x_n) = 0\\m\vert & \mbox{und } \forall k < m \mbox{ ist} \\{} & f(k,x_1,...,x_n) \neq \bot \end{cases}$

Was macht das kleine Zeichen denn nun letztendlich? Es hilft uns dabei die vorab fehlende Anzahl an notwendigen Schleifendurchläufen im Programm zu kompensieren. Wir haben dann kein "tue etwas, und zwar x Mal" (LOOP), sondern ein "tue etwas bestimmtes solange etwas der Fall ist" (WHILE). $m$ wird hier bei jedem Schleifendurchlauf hochgezählt und geprüft ob $f(m,x_1,...,x_n) = 0$ ist. Es sucht also die erste "Nullstelle" der Funktion. Wenn das der Fall ist, haben wir das erste $m$, d.h. die Anzahl der Schleifendurchläufe bis zur ersten Nullstelle. Falls die Bedingung nicht erreicht wird, $f(k,x_1,...,x_n)$ wird nie 0, terminiert die Schleife nicht. Das ist der Unterschied zu primitiv rekursiven (LOOP-berechenbaren) Funktionen. Dort steht bereits vor der Ausführung fest wieviele Schleifendurchläufe es gibt, sie haben also eine begrenzte Schachtelungstiefe.

Wichtig ist hierbei, dass die Funktion bis zum auftreten unseres gesuchten $m$ für alle Werte kleiner als $m$ einen Funktionswert liefert, d.h. tatsächlich überall (bis dahin zumindest) definiert ist. Jetzt könntet Ihr euch fragen: "Warum zur Hölle interessiert uns die Nullstelle der Funktion?!". Tut sie selbst eig. zunächst nicht. Wir formen unsere Funktion nur so um, dass sie bei einer erfolgreichen Berechnung am Ende der Durchläufe = 0 ist. Wenn sie erreicht ist, haben wir die Berechnung beendet und unser Ergebnis ist die Anzahl der Schleifendurchläufe. Ansonsten terminiert die Maschine nicht und rechnet endlos weiter.

Aber vielleicht wird das aus den Beispielen etwas deutlicher.

Beispiel: $add(m,n)$ (primitiv rekursiv, LOOP)

Update: danke für die Korrektur des Schleifenfehlers, Dennis.

Wir wissen aus der primitiven Rekursion, dass diese Funktion primitiv rekursiv ist. Auch wissen wir schon vorab Bescheid wieviele Schleifendurchläufe wir brauchen werden. Nämlich genau $m$ (oder $n$, je nachdem über welche Variable wir hochzählen). Geben wir doch mal so ein Loop-Programm für die Addition an (x ist die Ergebnisvariable) welches nur die Grundoperationen nutzt:

x := n;
LOOP m DO
 x := x + 1;
END

Oder der ganze Spaß mit der Grundoperation Nachfolger: $succ()$:

x := n;
LOOP m DO
 x := succ(x);
END

Wir wissen in beiden Fällen schon vorab wieviele Schleifendurchläufe wir haben werden: genau $m$ Stück.

Beispiel: partielle Subtraktion ($\mu$-rekursiv, WHILE)

Während die totale Subtraktion (also die arithmetische Differenz) primitiv rekursiv sind, ist es die partielle Subtraktion nicht. Tun wir mal so als wissen wir das nicht und versuchen unser Glück. Die partielle Subtraktion ist definiert als:

$psub(a,b):=\begin{cases} {a-b,} & \mbox{ falls } a \geq b\\{undef.,} & \mbox{ sonst }\end{cases}$

Sollte also a größer oder gleich b sein, so erfolgt die Subtraktion. Andernfalls ist der Funktionswert undefiniert, d.h. unsere Funktion terminiert nicht. Wie formulieren wir diese Funktion denn nun primitiv rekursiv? Wir müssen also ein LOOP-Programm angeben, welches den Funktionswert berechnet und aus den Grundoperationen besteht. Der beste Versuch scheitert bei dem Versuch eine 1 zu substrahieren:

x := a + 0;
LOOP b DO
 x := x ??? 1
END

Und fehlt hier die Subtraktion selbst. Setzen wir mal die arithmetische Differenz ein, von der wir wissen, dass sie primitiv rekursiv ist. Sie ist wie folgt definiert:

$sub(a,b):=\begin{cases} {a-b,} & \mbox{ falls } a \geq b\\{0,} & \mbox{ sonst }\end{cases}$

x := a + 0;
LOOP b DO
 x := sub(x,1)
END

Setzen wir die Werte a = 5 und b = 3, so haben wir 3 Schleifendurchläufe mit folgenden Aufrufen:

sub(5,1) = 4

sub(4,1) = 3

sub(3,1) = 2

Sieht gut aus, oder? Und nun wollen wir mal der Definition unserer partiellen Subtraktion $psub$ nach bei Werten $b > a$ einen undefinierten Wert rausbekommen. Wir starten also mit a = 3 und b = 5 bei 5 Schleifendurchläufen (wir loopen ja über b = 5).

sub (3,1) = 2

sub (2,1) = 1

sub (1,1) = 0

sub (0,1) = 0

sub (0,1) = 0

Was ist denn hier passiert?! Wir haben eine 0, was offensichtlich falsch ist. Jetzt könnte man meinen: "Ist doch kein Problem! Ist das eben unser undefinierter Wert falls $b > a$!". Und wie unterscheiden wir diesen vom Ergebnis wenn $a = b$ ist? Tja... da müssen wir also mal eine Lösung für finden. Holen wir mal den $\mu$-Operator zur Hilfe und basteln uns mit ihm eine WHILE-Schleife.

Die Frage ist zunächst: wie bekommen wir die feste Anzahl an Schleifendurchgängen weg? Wir müssen ein Kriterium angeben, welches uns eine Abbruchbedingung und somit eine dynamische Anzahl an Schleifendurchgängen erlaubt. Und uns am besten auch noch den Wert für die Anzahl der dazu benötigten Schleifendurchgänge liefert. Wir einigen uns zunächst darauf, dass die Berechnung abgebrochen werden soll wenn der Wert 0 erreicht wird und bemühen unsere $\mu$-Definition von oben:

$\mu f(x_1,...,x_n):=min\begin{cases} {} & f(m,x_1,...,x_n) = 0\\m\vert & \mbox{und } \forall k < m \mbox{ ist} \\{} & f(k,x_1,...,x_n) \neq \bot \end{cases}$

Wir müssen unsere Funktion also so schreiben damit es der $\mu$-Rekursion entspricht:

$\mu f(a,b):=min\begin{cases} {} & f(m,a,b) = 0\\m\vert & \mbox{und } \forall k < m \mbox{ ist} \\{} & f(k,a,b) \neq \bot \end{cases}$

Wir setzen die neue Funktion mit einem Parameter mehr (nämlich m) = 0 für unsere Abbruchbedingung alleine nur mit den Grundoperationen Wir setzen unsere Funktion = 0: $f(m,a,b) = sub(b+m,a) + sub(a,b+m)$ und betrachten folgende Fälle in dem entstandenen WHILE-Programm:

m:=0;

WHILE f(m,a,b) NOT 0 DO
  h:=m;

  m:=m+1;

END;

• 1. Fall $a > b$: Ergebnis kann berechnet werden

Am Ende der Schleifendurchgänge muss der Funktionswert = 0 berechnet und die Anzahl der Schleifendurchgänge in der Variable $m$ abgespeichert werden. Testweise probieren wir das mit $a = 5, b = 2$ aus:

$\begin{array}{lcl}f(0,5,2)&=& sub(2+0,5) + sub(5,2+0) & = 0 + 3 & m = 0\\ {} &=& sub(2+1,5) + sub(5,2+1) & = 0 + 2 & m=1& \\ {} &=& sub(2+2,5) + sub(5,2+2) & = 0 + 1 & m=2&\\ {} &=& sub(2+3,5) + sub(5,2+3) & = 0 + 0 & m=3&\end{array}$

Ab $m=3$ ist unsere Funktion = 0 geworden, die Berechnung wird abgebrochen und wir haben in $m$ die Anzahl der Schleifendurchläufe als Ergebnis stehen. Passt also. $\mu f(5,2) = 3$.

• 2. Fall $a = b$: Ergebnis kann berechnet werden

Am Ende der Schleifendurchgänge muss der Funktionswert = 0 berechnet und die Anzahl der Schleifendurchgänge in der Variable $m$ abgespeichert werden.

$\begin{array}{lcl}f(0,5,5)&=& sub(5+0,5) + sub(5,5+0) & = 0 + 0 & m = 0\end{array}$

Und hier sind wir auch schon fertig. Passt auch. $\mu f(5,5) = 0$.

• 3. Fall $a < b$: Ergebnis ist undefiniert, Berechnung hält nie

Ergebnis ist undefiniert, die Schleife ist endlos.

$\begin{array}{lcl}f(0,2,5)&=& sub(5+0,2) + sub(2,5+0) & = 3 + 0 & m = 0\\ {} &=& sub(5+1,2) + sub(2,5+1) & = 4 + 0 & m=1& \\ {} &=& sub(5+2,2) + sub(2,5+2) & = 5 + 0 & m=2&\\ {} &=& ... & ... & ... &\end{array}$

Hier bricht die Schleife nicht ab, da der Erste Teil der Substraktion mit jeder Schleife immer weiter hochgezählt wird. Das Ergebnis ist für $a < b$ also undefiniert. $\mu f(2,5)=\bot$. Genau das, was wir wollten.

Und nun versuchen wir es mal etwas abstrakter und werden probieren die Goldbach-Vermutung als LOOP-Programm (und somit primitiv rekursiv) abzubilden:

Beispiel: Goldbach-Vermutung

Die Goldbach-Vermutung besagt, dass jede gerade Zahl > 2 als die Summe zweier Primzahlen geschrieben werden kann. Und wir wissen ja, wie wir das testen können: durchprobieren! Nehmen wir z.B. die 4: diese können wir als 4 = 2+2 schreiben. Nun nehmen wir die 6: 6 = 3 + 3. Geht auch. Das können wir so fortführen. Und nun? Wir definieren die Goldbach-Vermutungs-Funktion, die wir auf LOOP (primitiv Rekursiv) oder WHILE ($\mu$)-Berechenbarkeit prüfen wollen durch ein Prädikat $Goldbach$. Das liefert uns eine 1 wenn die Bedingung erfüllt ist und ansonsten eine 0.

$Goldbach(n):=\begin{cases} {1,} & \mbox{ wenn aus zwei Primzahlen darstellbar}\\{0,} & \mbox{ sonst }\end{cases}$

Wie würde unser LOOP-Programm denn für die Goldbach-Vermutung aussehen? Etwa so?

x := 0;
LOOP m DO
 x := Goldbach(m)
END

Hierbei gibt $Goldbach(m)$, wie erwähnt, eine 1 aus wenn die Zahl $m$ mit zwei Primzahlen geschrieben werden kann und 0 sonst. Wir wollen alle $m$ testen, die Schleifendurchgänge sind also dynamisch. Wir kommen hier mit dem LOOP also nicht sonderlich weit und das Programm ist wertlos. Es hört eben genau nach $m$ Schleifendurchgängen mit der Berechnung auf. Wir versuchen es nun mit einem WHILE-Programm:

x := 0;

m:=0;

WHILE x NOT 0 DO
  x := Goldbach(m);
  succ(m);
  h:=m;
  succ(m);

END

Ui, schau an. Sieht doch gut aus! Am Ende der Berechnung (wenn es denn eine gibt) bekommen wir im $x$ eine 0 wenn das Programm auf das erste (und somit auch das kleinste $m$ für das es der Fall ist) $m$ stößt, welches nicht mit zwei Primzahlen geschrieben werden kann, denn unsere Goldbach-Funktion gibt uns ja nach unserer oberen Definition eine 0 aus wenn die Zahl nicht als Summe zweier Primzahlen darstellbar ist (wie wir das genau berechnen ist uns derzeit - für das Verständnis des $\mu$-Operators selbst - ziemlich egal). Streng genommen wird das $m$ am Ende ja nochmal um eins erhöht und wir bekommen das gesuchte $m$ um eins erhöht und müssten es um 1 dekrementieren, aber wir wollen mal nicht so kleinlich sein Mike hat in den Kommentaren mal kurz die WHILE-Schleife umgestellt, das geht natürlich auch und ist eine gute Idee. Damit ist die Änderung auch drin

Wie man sieht haben wir also eine freche Abkürzung genommen: wir haben einfach $Goldbach(m)$ ohne Berechnungs-Definition verwendet und es auch nicht = 0 gesetzt. Für das Verständnis sollte das reichen. Ansonsten müsste man genauso vorgehen wie bei der partiellen Subtraktion.

Im Endeffekt minimalisieren wir hier also eine Funktion und suchen ihre kleinste Nullstelle. Lassen wir z.B. den $\mu$-Operator auf die konstante Funktion $f(x) = 1$ los, so werden wir nie eine Nullstelle finden (es gibt ja keine, der Funktionswert ist immer = 1) und enden in einer Endlosschleife. Damit ist die Funktion $f$ überall undefiniert. Auch wenn ich eine Funktion $f$ habe, die eine Nullstelle hat, aber irgendwo davor undefiniert ist, so ist unsere $\mu f$ auch undefiniert. Das kann man sich beim Aufstellen einer Wertetabelle sehr gut vor Augen führen.

Update

Den Merksatz habe ich bereits einen Betrag zuvor bei der primitiven Rekursion verwendet und halte ihn für so wichtig, ihn noch einmal hier zu verwenden. Bitte vollzieht in euren Gedanken den Merksatz nach damit die Beiden wichtigen Konstrukte auch wirklich hängen bleiben

Merksatz: jedes LOOP-Programm lässt sich durch primitive Rekursion ausdrücken un jede primitiv rekursive Funktion durch ein LOOP-Programm. Ebenso lässt sich ein LOOP-Programm durch ein WHILE-Programm ersetzen. Damit ist auch jede primitiv rekursive Funktion WHILE-Berechenbar. Jedoch gilt das nicht umgekehrt: WHILE-Schleifen lassen sich nicht durch LOOP-Schleifen ersetzen (es ist z.B. im Voraus nicht bekannt wie häufig die Schleife durchlaufen wird), siehe Ackermann-Funktion. Erst durch die $\mu-Rekursion$ können wir das WHILE-Konstrukt mathemathisch greifbar machen.

Wie immer gilt: wer grobe Schnitzer findet, ab in die Kommentare

Wichtig: lasst euch von der mathematischen Definition nicht einschüchtern. Ich versuche in jedem Satz immer die Definition noch zu erklären. Ansonsten: wer grobe Schnitzer findet: bitte melden!

Zwei wichtige Themen aus der 2. Kurseinheit behandeln die primitive und die $\mu$-Rekursion. Aus der Definition im Kurstext erschließt sich mir ihre (und von vielem anderen auch) Bedeutung jedoch nicht sofort. Aber vielleicht stehe ich auch einfach auf dem Schlauch bei diesen Themen. Beide Rekursionen dienen dazu das Repertoire der berechenbaren Funktionen zu vergrößern.

In Kurseinheit 1 gab es ja bereits eine Liste an berechenbaren Funktionen. All' diese konnten mit einer einfachen Registermaschine, welche nur die Grundoperationen (Arithmetische Differenz zu 1, Addition von 1 und Test auf 0) abgebildet werden. Das ist zwar alles schön und gut, aber reicht uns natürlich nicht. Also erweitern wir das Feld der berechenbaren Funktionen mit der Rekursion, denn der Definition nach sind alle primitiv- und $\mu$-rekursiven Funktionen berechenbar.

Grundoperationen, Komposition, Rekursion

Was ist also die primitive Rekursion? Die primitiv rekursiven Funktionen entstehen aus den Grundoperationen (die stelle ich gleich vor) und werden mittels Komposition (Hintereinanderausführung) und/oder der primitiven Rekursion gebildet. Als Grundoperationen haben wir:

Die konstante Funktion: $C^k : \mathbb{N}^k \rightarrow \mathbb{N}$ mit $(n_1, ..., n_k) \mapsto c$ und $c \in \mathbb{N}$.

Oder manchmal auch die Nullfunktion $0^k : \mathbb{N}^k \rightarrow \mathbb{N}$ mit $(n_1, ..., n_k) \mapsto 0$

Erklärung: $\mathbb{N}^k \rightarrow \mathbb{N}$ bedeutet nichts weiter als dass der Definitionsbereich (und damit die Argumente der Funktion) der Bereich der natürlichen Zahlen (eben $\mathbb{N}^k$) ist. $k$ bedeutet Stelligkeit (also die Anzahl der Argumente der Funktion, die Argumente selbst sind mit $(n_1, ..., n_k)$ angegeben). Das Ergebnis der Funktion ist jedoch nur einstellig. Z.B. wäre $f^3 : \mathbb{N}^3 \rightarrow \mathbb{N}$ mit $f(x,y,z) = x + y - z$ so eine Funktion (nicht für eine konstante Funktion), die  drei Argumente entgegen nimmt, aber nur einen Funktionswert (sogenannter Wertebereich) ausgibt.

Die konstante Funktion $C^k$ macht noch viel weniger. Egal wieviel Argumente Du ihr gibst, sie gibt immer nur einen Wert zurück. Die Konstante c, welche auch aus dem Bereich $\mathbb{N}$ kommt. Also z.B. $f^4 : \mathbb{N}^4 \rightarrow \mathbb{N}$ mit $f(a,b,c,d) = 5$. Egal, was die Funktion an Argumenten bekommt, es kommt immer 5 heraus.

Die konstante Nullfunktion, welche häufig in den Definitionen für die primitive Rekursion verwendet wird ist auch nur eine konstante Funktion. Nur ist hier $c$ immer einfach nur 0. Mehr nicht. Also nicht verwirren lassen.

Die Projektion auf ein Argument: $\pi^k_i : \mathbb{N}^k \rightarrow \mathbb{N}$ mit $(n_1,...,n_k) = n_i$

Hier ist die Erklärung offensichtlich. Also überspringen wir sie mal. Nein, Scherz. Das muss ich oft genug im Skript lesen und denke mir nur: "Bitte?!". Manche Dinge sind derart einfach, dass man nicht glaubt sie verstanden zu haben weil man von den ganzen griechischen Buchstaben erschlagen wurde.

Diese Funktion tut nur eines: sie gibt das $i-te$ Argument aus ihrer $k$-stelligen Argumentliste zurück. Das wars. Wirklich. Aber eine Kleinigkeit ist noch hilfreich: Es gibt die einstellige Projektion mit $\pi^1_1(n_1) = n_1$. Diese nennt man die Identitätsfunktion $id(x) = x$. Konkretes Beispiel für beide? Bitte sehr. Projektion: $\pi^4_2(a,b,c,d) = b$. Identitätsfunktion: $\pi^1_1(a) = id(a) = a$.

Die Nachfolgefunktion: $Suc : \mathbb{N} \rightarrow \mathbb{N}$ mit $n \mapsto suc(n) := n+1$

Geht kaum einfacher. Was macht die Funktion? Sie gibt zu dem ihr gegebenen Argument einfach nur den Nachfolger zurück. Beispiel: $f(2) = 3$. Das war's.

Was haben die Basis-Funktionen nun mit primitiver Rekursion zu tun? Alle Funktionen, die aus diesen Basisoperationen mittels Komposition (oder Substitution) und Rekursion gebildet werden können, werden rekursive Funktionen genannt und sind berechenbar. Diese liegen in $\mathcal{P}$, dem Bereich der total-rekursiven Funktionen, denn sie decken den vollständigen Definitionsbereich ab (jedem Wert aus dem Definitionsbereich wird ein Funktionswert zugeordnet, kein Argument bleibt ohne Funktionswert). Zu den partiell-rekursiven Funktionen kommen wir noch.

Beispiel: Wollen wir mal einen Versuch wagen und eine Komposition der Grundoperationen aufstellen und ausrechnen?

Konstante Funktion: $c : \mathbb{N}^2 \rightarrow \mathbb{N}$ mit $c(x,y) \mapsto 4$.

Projektion $\pi^2_1 : \mathbb{N}^2 \rightarrow \mathbb{N}$ mit $\pi^2_1 (x,y) \mapsto x$

Nachfolgefunktion: $suc : \mathbb{N} \rightarrow \mathbb{N}$ mit $suc(x) \mapsto x+1$

Wir bilden nun aus diesen drei Funktionen eine Komposition: $\pi^2_1(x,y)\circ (c(x,y) \circ suc(x))$. D.h. eine Hintereinanderausführung der Funktionen. Es gilt (bitte beim Wikipedia-Link nachschauen) bei der Komposition: $g \circ (f \circ h) = g(f(h(x)))$. Für unsere Funktionen bedeutet es also: $\pi^2_1(c(suc(x),y),z)$. Wir setzen unsere Variablen willkürlich: $x=5$, $y=6$ und $z=7$. Damit haben wir dann auch gleich etwas, womit wir rechnen können: $\pi^2_1(c(suc(5),6),7)$. Wir beginnen also von Innen nach Außen:

$suc(5) = 6$ (unsere Nachfolgefunktion)

$c(6,6) = 4$ (unsere konstante Funktion)

$\pi^2_1(4,7) = 4$ (unsere Projektion)

Damit ist $\pi^2_1(c(suc(5),6),7) = 4$.

Nun ist jede Funktion, die wir mit den drei Basisoperationen von oben mittels Komposition (Substitution) und Rekursion abbilden können ebenfalls primitiv-rekursiv und damit berechenbar.

Rekursionsschema

Bitte nicht drüber hinwegweg lesen. Diese Ausführung wird bei jeder Definition der primitiven Rekursion verwendet (manchmal in umgekehrter Reihenfolge, aber der Sinn und Zweck sind gleich). Erst wenn man die Funktion in das Rekursionsschema hat überführen können, ist sie wirklich primitiv rekursiv. Wir werden also mit folgenden Dingen gequält:

1. Komposition/Einsetzung/Substitution formal: haben wir hier z.B. eine Funktion $h$ (k-stellig mit $\mathbb{N^k}$) und mehrere Funktionen $g_1,...,g_k$ (alle n-stellig mit $\mathbb{N^n}$) und sind diese primitiv-rekursiv, so ist auch $h(g_1(x_1,...,x_n), ..., g_k(x_1,...,x_n))$ primitiv-rekursiv.

Das bedeutet: nichts weiter als eine Einsetzung. Zunächst haben wir in der Funktion $h$ genau $k$ Parameter (Stelligkeit, siehe oben) aus dem Bereich der natürlichen Zahlen $\mathbb{N}$. Und dann noch  $k$ Funktionen $g$ (es können auch mehr sein, aber wir brauchen nur $k$), die selbst $n$ Parameter verwenden, welche oben mit $(x_1,...,x_n)$ beschrieben sind. Nun möchten wir die (nicht beschriebenen) Parameter der Funktion $h$ einfach durch ausgerechnete Funktionswerte der Funktionen $g$ ersetzen. Das ist alles, was die Substitution macht.

Beispiel:

Funktion: $h : \mathbb{N}^2 \rightarrow \mathbb{N}$ mit $h(x,y) \mapsto x*y$
Funktion: $g : \mathbb{N}^3 \rightarrow \mathbb{N}$ mit $g(a,b,x) \mapsto a+b+c$

Wir führen nun die Substitution der Parameter von $h$ mit den Funktionswerten von $g$ durch: $h(x,y) = h(g(a,b,c),g(a,b,c))$. Wir setzen willkürlich $a = b = c = 2$ und haben somit: $h(g(2,2,2),g(2,2,2))$. Ausrechnen von Innen nach Außen: $h(6,6) = 36$. That's it!

2. Rekursionsschema formal: dieser Teil wird dazu verwendet um zu garantieren, dass auch die neue Funktion, welche durch primitive Rekursion gebildet wurde bzgl. primitiver Rekursion abgeschlossen und ist nicht aus dem Rahmen fällt. Es besagt, dass eine Funktion $f$ nach dem Schema der primitiven Rekursion aufgebaut ist, wen sie folgende Form besitzt:

$f(m,n)=\begin{cases} g(n), & \mbox{falls }m = 0 \\ h(f(m-1,n),m-1,n), & \mbox{falls }m > 0 \\\end{cases}$

Was bedeutet das nun für uns? Wir haben hier zwei Fallunterscheidungen: einmal wenn ein Parameter = 0 (m=0) ist, so bedarf es keiner Rekursion und wird durch eine Funktion $g(n)$ abgehandelt. Ist jedoch $m > 0$, müssen wir einen zweiten Fall betrachten. Hier erfolgt die Rekursion, welche die Funktion $f$ einfach nur mit dem nächst-kleineren Parameter $m-1$ aufruft. Am Ende wird  $m=0$ und wir können unser $g(n)$ für diesen Fall verwenden und schließen die Rekursion damit ab.

Häufig wird auch folgende Definition verwendet:

(R1) $f(0,x_1,...,x_n) = g(x_1,...,x_n)$

Bedeutet nichts anderes, als unser $g$ von oben. Nur dass das etwas allgemeiner formuliert und die Parameterbeschränkung abgehoben wurde.

(R2) $f(m+1,x_1,...,x_n) = h(f(m,x_1,...,x_n),m,x_1,...x_n)$

Auch das ist nicht weit weg von unserer Fallunterscheidung. Unsere Funktion beginnt mit dem Parameter $m+1$, das ist das was eig. unsere Schleifenvariable ist. Diese wird dann im nächsten Durchlauf dekrementiert und die Funktion ruft sich mit diesem dekrementierten Wert so lange selbst auf, bis $m=0$ ist und wir unser oben definiertes $g$ verwenden können. In manchen Definitionen wird einfach nur $m$ in $f$ verwendet und in $h$ steht dann $m-1$.

Hier wäre ein Beispiel nicht schlecht, oder? Versuchen wir es doch mal mit der Addition und schauen ob sie aus der Klasse der primitiv-rekursiven Funktionen ist. Also los geht's:

Ist die Addidtion primitiv rekursiv?

Um zu beweisen, dass eine Funktion primitiv rekursiv ist muss man diese mit den obigen Grundoperationen definieren und in das Rekursionsschema pressen können. Und zwar für alle Fälle aus den natürlichen Zahlen. Hier sei die 0 vor allem zu beachten, denn die wird gerne mal vergessen. Im Endeffekt ist die Addition ja nur $add(m,n) = m+n$. Um zu zeigen, dass sie primitiv rekursiv ist müssen wir sie nun mit den oben definierten Grundoperationen abbilden und sie ins Rekursionsschema pressen. Probieren wir es einfach.

1. Fall: Addition von 0 + n. Bedeutet: $add(0,n)=0+n = n$. Das bilden wir ab mit der Projektion: $\pi^2_2 : \mathbb{N}^2 \rightarrow \mathbb{N}$ mit $\pi^2_2 (0,n) \mapsto n$.  Aufgeschrieben bedeutet dies: $add(0,n)=\pi^2_2 (0,n)=n$. Damit wir unser $g(n)$ aus dem Rekursionsschema von oben schon erschlagen:

$add(m,n)=\begin{cases} g(n) = \pi^2_2 (0,n), & \mbox{falls }m = 0 \\ ..., & \mbox{falls }m > 0 \\\end{cases}$

Allgemein ausgedrückt (wir wollen uns ja an die Definitionen aus dem Skript halten) pressen wir das nun in unsere Definition von $g$ aus (R1):

$f(0,x_1,...,x_n) = add(0,n)$

$g(x_1,...,x_n)=g(n)=\pi^2_2 (0,n)=n$

Und somit

(R1) $add(0,n)=g(n)=\pi^2_2 (0,n)=n$

Passt also in den ersten Teil des Schemas.

2. Fall: Addition von m + n: Bedeutet: $add(m,n) )= m+n$. Das ist etwas schwieriger. Hier bedienen wir uns der primitiven Rekursion und der Nachfolgefunktion $suc$: $add(m+1,n) = suc(add(m,n))$ (Achtung: die Funktion ist noch nicht in der geforderten Form für den 2. Fall um die Übersicht zu wahren). Noch nicht so ganz einleuchtend, oder? Vor allem nicht, wie wir drauf gekommen sind. Nehmen wir einen ganz einfachen Fall mit echten Zahlen.

Wollen wir z.B. 1 + 5 addieren, so fällt uns schnell ein, dass wir uns doch einfach einmal der Nachfolgefunktion bedienen können: $add(1,5) = suc(add(0,5))$ (nun haben wir Innen den 1. Fall von oben, wo die 0 addiert wird und wir verwenden die dort für diesen Fall definierte Projektion, unser $g(n)$ auf das zweite Argument) $=suc(\pi^2_2(0,5)) = suc(5) = 6$. Schnell sollte einleuchten, dass wir uns einfach beliebig oft der Nachfolgefunktion bedienen dürfen, abhängig davon was wir addieren. Wir können hier aber zunächst nur die 1 addieren. Um auch mehr als die 1 addieren zu können, müssen wir die Funktion so definieren, dass sie am Ende auf unser $g(n)$ Innen zurückgeführt, welches dann mit $suc(x)$ ausgerechnet werden kann. Wie würde unser $add(2,5)$ denn aussehen? So: $suc(suc(\pi^2_2(0,5))) = suc(suc(5))$. Lösen wir das auf: $suc(suc(5)) = suc(6) = 7$. Und $add(3,5)$? Genau! $suc(suc(suc(\pi^2_2(0,5)))) = suc(suc(suc(5))) = 8$.

Das ist aber noch nicht die Rekursion, denn eine Rekursion ist der Aufruf einer Funktion durch sich selbst. Und vor allem ist das ja auch noch nicht in der streng geforderten Form! Wir können ja nicht für jeden $n$ aus $\mathbb{N}$ tausende von $suc$ angeben. Also muss unser $add$ rekursiv durch sich selbst definiert werden (was ja am Ende sowieso auf ein einzelnes $suc$ zurückführt). Probieren wir also das Beispiel mit den Zahlen $(3,5)$ von oben und arbeiten mit Rekursion statt nur mit tausenden von $suc$:

$\begin{array} {lcl} add(3,5)&=& suc(add(2,5))\\&=& suc(suc(add(1,5)))\\&=&suc(suc(suc(add(0,5))))\\&=&suc(suc(suc(\pi^2_2(0,5))))\\&=&suc(suc(suc(5)))\\&=&suc(suc(6))\\&=&suc(7)\\&=&8\end{array}$

Damit entspricht das genau dem, was wir mit $add(m+1,n) = suc(add(m,n))$ bereits rekursiv definiert haben. Für die einfache Fallunterscheidung nehmen wir dann $add(m,n) = suc(add(m-1,n))$, was ja das Selbe ist. Für die allgemeinere Definition aus (R2) ist unsere Definition jedoch goldrichtig.

Ab damit in die Fallunterscheidung und wir haben unser $h$ gefunden:

$add(m,n)=\begin{cases} g(n)=\pi^2_2 (0,n), & \mbox{falls }m=0 \\ suc(\pi^3_1 (add(m-1,n),m-1,n)) & \mbox{falls }m > 0 \\\end{cases}$

Wie versprochen werden wir auch hier allgemeiner und pressen das in unsere Definition der Rekursion für (R2):

(R2) $f(m+1,x_1,...,x_n)=add(m+1,n)$

$h(f(m,x_1,...,x_n),m,x_1,...x_n) = suc(\pi^3_1(add(m,n),m,n))$

Und somit

(R2) $add(m+1,n) = suc(\pi^3_1(add(m,n),m,n))$

Und das passt auch in den zweiten Teil des Schemas.

Nehmen wir Papier und Stift und rechnen damit ein konkretes Beispiel durch:

Beispiel: $add(3,4)$

Mit unserer Definition der Addition von oben  $add(m+1,n)=suc(\pi^3_1 (add(m,n),m,n))$ können wir das nun rekursiv auflösen:

$\begin{array} {lcl} add(3,4)&=& suc(\pi^3_1 (add(2,4),2,4))\\&{}&\text{(aufloesen von add(2,4))}\\&=& suc(\pi^3_1 (suc(\pi^3_1(add(1,4),1,4),2,4)))\\&{}&\text{(aufloesen von add(1,4))}\\&=&suc(\pi^3_1 (suc(\pi^3_1(suc(\pi^3_1(add(0,4),0,4),1,4),2,4))))\\&{}&\text{(aufloesen von add(0,4))}\\&=&suc(\pi^3_1 (suc(\pi^3_1(suc(\pi^3_1(\pi^2_2(0,4),0,4),1,4),2,4))))\\&{}&\text{(aufloesen von }\pi^2_2(0,4))\\&=&suc(\pi^3_1 (suc(\pi^3_1(suc(\pi^3_1(4,0,4),1,4),2,4)))\\&{}&\text{(aufloesen von }\pi^3_1(4,0,4))\\&=&suc(\pi^3_1 (suc(\pi^3_1(suc(4),1,4),2,4)))\\&{}&\text{(ausrechnen von } suc(4))\\&=&suc(\pi^3_1 (suc(\pi^3_1(5,1,4),2,4)))\\&{}&\text{(aufloesen von }\pi^3_1(5,1,4))\\&=&suc(\pi^3_1 (suc(5),2,4)))\\&{}&\text{(ausrechnen von } suc(5))\\&=&suc(\pi^3_1 (6,2,4))\\&{}&\text{(aufloesen von }\pi^3_1 (6,2,4))\\&=&suc(6)\\&{}&\text{(ausrechnen von } suc (6))\\&=&7\end{array}$

Damit haben wir die Addition primitiv rekursiv definiert, die Addition ist also ein Teil der primitiv-rekursiven Funktionen und damit berechenbar. Sicher wollt ihr den ganzen Spaß auch mit der Multiplikation machen. Probiert es mal. Ihr werden sehen, dass es schnell unübersichtlich wird wenn ihr nur die 3 Grundoperationen von oben benutzt. Irgendwas stimmt hier aber noch nicht ganz, oder? Euch schwirrt bestimmt noch etwas aus der 1. Kurseinheit im Kopf rum, was wir gemacht haben. Genau! Erinnert ihr euch zufällig noch an die normalen und verallgemeinerten Registermaschinen aus der 1. Kurseinheit?

Alle Operationen, die wir mit normalen Registermaschinen abbilden und damit ihre Berechenbarkeit beweisen konnten, konnten wir fortan in unseren verallgemeinerten Registermaschinen ohne Beweis benutzen! Das Gleiche können wir hier auch tun. Wir können jetzt die Multiplikation primitiv-rekursiv definieren und hierfür die Addition verwenden, deren Berechenbarkeit wir soeben nachgewiesen haben. Weil wir dann damit nach dem Rekursionsschema die Multiplikation mittels der Addition definieren konnten, die Addition durch die 3 Grundoperationen definiert wurde folgt daraus, dass die Multiplikation auch berechenbar ist.

Gerne kann ich den Lösungsweg für die Multiplikation dann auch posten wenn gewünscht. Versucht es aber erstmal selbst.

Ackermann-Funktion

Aber auch die primitive Rekursion hat ihre Grenzen. Genau für diese wurde die Ackermann-Funktion erfunden. Man vermutete vor einiger Zeit, dass man mit der Klasse der primitiv Rekursiven Funktionen alle berechenbaren Funktionen erschlagen hätte. Das wurde jedoch von der Ackermann-Funktion, die eigens dafür entwickelt wurde, widerlegt. Das Repertoire an Grundoperationen war schlicht und ergreifend nicht mächtig genug um diese berechenbare, aber nicht primitiv rekursive Funktion abzubilden.

Erst mit der Einführung des $\mu$-Operators und der sogenannten $\mu$-Rekursion hat man diese Klasse so erweitern können, dass die Ackermann-Funktion da hinein fällt. Man geht in der Church'schen These davon aus, dass sich mit der $\mu$-Rekursion nun alle berechenbaren Funktionen abbilden lassen, die (Turing-)berechenbar sind. Aber da kümmern wir uns dann im nächsten Beitrag im Rahmen der $\mu$-Rekursion drum.

Loop Berechenbarkeit

Eine wichtige Eigenschaft der rekursiven Funktionen ist derer Zusammenhang mit der LOOP-Berechenbarkeit. Jedes LOOP-Programm lässt sich primitiv rekursiv darstellen und umgekehrt. Im Gegensatz zu GOTO (Registermaschinen) und WHILE (unsere $\mu$-Rekursion) terminieren LOOP-Programme immer. Und ja, Ihr habt es euch vielleicht gedacht: die Ackermann-Funktion ist nicht primitiv rekursiv und damit auch nicht LOOP-berechenbar.

Aber hier steht schon zu viel Text. Vielleicht sind WHILE und LOOP-Berechenbarkeit ja einen eigenen Beitrag wert

Update

Gesagt, getan: der neue Beitrag behandelt die $\mu$-Rekursion und die WHILE-berechenbarkeit. Auch wenn ich das bereits etwas vorweg nehme, ein wichtiger Merksatz um es auf den Punkt zu bringen:

Merksatz: jedes LOOP-Programm lässt sich durch primitive Rekursion ausdrücken un jede primitiv rekursive Funktion durch ein LOOP-Programm. Ebenso lässt sich ein LOOP-Programm durch ein WHILE-Programm ersetzen. Damit ist auch jede primitiv rekursive Funktion WHILE-Berechenbar. Jedoch gilt das nicht umgekehrt: WHILE-Schleifen lassen sich nicht durch LOOP-Schleifen ersetzen (es ist z.B. im Voraus nicht bekannt wie häufig die Schleife durchlaufen wird), siehe Ackermann-Funktion. Erst durch die $\mu-Rekursion$ können wir das WHILE-Konstrukt mathemathisch greifbar machen.

Um zu zeigen, dass eine Zahlenfunktion berechenbar ist muss man nachweisen, dass man die Funktion mit der allgemeinen Maschine berechnen und die komplexen Funktionen und Tests der allgemeine Registermaschine dann durch eine normale Registermaschine  ausdrücken kann (die korrekte Funktion dieser vorausgesetzt bzw. bewiesen). Auch müssen die im Flussdiagramm vorkommenden Tests rekursiv, d.h. entscheidbar sein. Wir kümmern uns hier um Ersteres. Der Umweg über die allgemeine Registermaschine wird gegangen um sich die Schreibarbeit der komplexen Funktionen nur einmal machen zu müssen. Hat man z.B. die Multiplikation als komplexe Operation mit einer normalen Registermaschine (nur mit den Operationen Addition/Subtraktion, arithmetische Differenz und Test auf 0) bewiesen, kann man diese ab sofort in seiner allgemeinen Registermaschine nutzen.

Formal definiert bedeutet es, dass eine Funktion $f : \subseteq \mathbb{N}^k \rightarrow \mathbb{N}$ dann berechenbar ist, genau dann wenn es eine k-stellige Registermaschine gibt mit $f = f_M$.Bei  $f_M(Eingabe) = x$ ist x hierbei das Ergebnis welches nach einem Durchlauf (man ist bei HALT gelandet oder wenn es kein Ende gibt bei $div$) der Registermaschine (das als Flussdiagramm dargestellt ist) in Register $R_0$ steht. Informal ausgedrückt bedeutet es, dass die Funktion $f$ durch Maschine $M$ berechnet werden kann und die Ergebnisse für jede Eingabe für $f$ und $f_M$ gleich sind: eben $f = f_M$.

Nehmen wir als Beispiel die Addition von zwei Registern $R_1$ und $R_2$ durch eine allgemeine Registermachine. Sie berechnet das Ergebnis und legt es dann im Ergebnisregister $R_0$ ab. Hier das zugehörige und unglaublich komplexe Flussdiagramm dazu.

Da es eine komplexe Funktion ist müssen wir sie jedoch mit einer normalen Registermaschine und den drei erlaubten Operationen (Addition und Subtraktion von$1$, sowie Test auf $0$) abbilden und zeichnen uns hierzu ein passendes Flussdiagramm. Dieses ist nur unwesentlich komplexer.

Umgangssprachlich macht die normale Registermaschine folgendes: die inkrementiert das Register $R_0$ zunächst genau $R_1$ mal und dekrementiert $R_1$ bei jedem Durchlauf der ersten Schleife ($p \rightarrow q \rightarrow e$). Anschließend wird es in Block $p$ wieder auf 0 geprüft. Sollte das Register $R_1$ tatsächlich 0 sein, bewegen wir uns dann zum Block $s$ um in der zweiten Schleife ($s \rightarrow t \rightarrow u$) das Selbe nochmal mit Register $R_2$ zu veranstalten und $R_0$ weitere $R_2$ Mal zu inkrementieren. Damit wird $R_0$ genau $R_1 + R_2$ Mal inkrementiert und so die Addition von Register $R_1$ und $R_2$ bewerkstelligt. Einfach, nicht? Jetzt stellt sich nur die Frage, wie wollen wir die korrekte Funktionalität unserer normalen Registermaschine beweisen. Alle $\mathbb{N}$ durchtesten? Ne, lieber nicht.

Der Beweis

Der Beweis, dass die Funktion $f(x,y) = f_M(x,y) = x+y$ berechenbar ist gliedert sich selbst in folgende Schritte:

1. allgemeine Registermaschine als Flussdiagramm zeichnen, die die Funktion berechnet. Ggf. die korrekte Funktion auch mit vollständiger Induktion beweisen. Hier verzichten wir darauf, da es für das kleine Flussdiagramm oben offensichtlich ist. Ebenso ist hier darauf zu achten, dass jeder vorkommende Test entscheidbar ist.
2. alle komplexen Operationen der allgemeinen Registermaschine durch eine normale Registermaschine als Flussdiagramm ausdrücken, wo man nur die aus der Definition für normale Registermaschinen erlaubten Funktionen Addition und Subtraktion von $1$, sowie Test auf $0$ durchführen darf. Auch hier bitte auf entscheidbare Tests achten.
3. nun hat man für jede komplexe Operation ein Flussdiagramm, deren korrekte Funktion man mit vollständiger Induktion beweisen muss.

Das Flussdiagramm aus Schritt 2 ist oben dargestellt. Da wir nur eine komplexe Operation (die Addition) haben, haben wir nur ein Flussdiagramm für eine normale Registermaschine. Man überzeuge sich, dass nur die erlaubten 3 Operationen benutzt werden. Überzeugt? Gut! Fangen wir mit dem Induktionsbeweis an.

Wir prüfen zunächst de Fälle, die wir als Eingabe haben und leiten hieraus die Induktionsbehauptungen ab:

Wir möchten jede natürliche Zahl ($\mathbb{N}$) addieren können. Im Endeffekt sind diese dann fest und wir haben nur eine unterschiedliche Anzahl an Einzelschritten, die wir durch das Programm gehen müssen bis das Ergebnis im Register $R_0$ steht. Abhängig von den Eingabewerten. Da wir zwei Schleifen haben, können wir für diese auch zwei Induktionsbehauptungen aufstellen.

Man sieht leicht, dass wir die erste Schleife genau $R_1$ Mal durchlaufen und wieder in Block $p$ landen. Ist z.B. $R_1 := 1$, so sind 3 Einzelschritte notwendig bis wir $R_1 = x$ erneut auf 0 testen und die Schleife verlassen. Das als Registerbelegung erwartete Gesamtergebnis ist also $(p,(i,x-i,y,0,...)$, wobei $i$ die Anzahl der Schleifendurchläufe und somit auch die Anzahl der Inkrementierungen von $R_0$ (eben $i$ im Ergebnis) und Dekrementierungen von $R_1$ (eben $x-i$ im Ergebnis) ist. Der Rest bleibt unangetastet ($y$ und $0$) Damit ergibt sich schon die erste Induktionsannahme in Abhängigkeit von x:

$ES^{3i}(p,(0,x,y,0,...) = (p,(i,x-i,y,0,...)$

Das Ergebnis ist so wie wir gewollt haben: ist $x := 1$, so haben wir nur einen Schleifendurchlauf, genau 3 Einzelschritte und am Ende die Registerbelegung $(i,x-i,y,0,...)$ und wir landen wieder im Block $p$. Ist $i = 2$, so haben wir zwei Schleifendurchläfe, somit 6 Einzelschritte und landen wieder bei $p$. Die Behauptung scheint also korrekt. Fehlt nur noch der Induktionsbeweis für den Dominoeffekt damit wir nicht unendlich viele Fälle durchtesten müssten.

Wir führen für die oben aufgestellte

Annahme: $ES^{3i}(p,(0,x,y,0,...)$ = $(p,(i,x-i,y,0,...))$

einen Induktionsbeweis über $i$ durch. Zu beweisen ist:

Behauptung: $ES^{3(i+1)}(p,(0,x,y,0,...) = (p,((i+1),x-(i+1),y,0,...)$

der Einfachheit halber ausrechnen:

$ES^{3i+3}(p,(0,x,y,0,...) = (p,(i+1,x-i-1,y,0,...)$

D.h. am Ende unseres Beweises muss $(p,(i+1,x-i-1,y,0,...))$ rauskommen. Wir fangen also an:

$ES^{3i+3}(p,(0,x,y,0,...) = ES^{3}$$(p,(i,x-i,y,0,...)$ (wir setzen hier den rechten Teil der Annahme von oben als "Induktionsschritt" ein, mit $ES^3$ haben wir unser "+1" um es mal nicht unbedingt formal korrekt auszudrücken und spielen jetzt das Flussdiagramm durch)

= $ES^2(q,(i,x-i,y,0,...))$ (nun sind wir in Block q)

= $ES(r,(i+1,x-i,y,0,...))$ (nun sind wir in Block r)

= $(p,(i+1,x-i-1,y,0,...))$ (am Ende sind wir in Block p)

Und siehe da: das Ergebnis entspricht dem rechten Teil der Behauptung. Damit haben wir die Schleife bewiesen.

Fehlt uns noch die Annahme für die andere Schleife. Diese ist analog zur ersten Schleife herauszufinden. Wir starten bei Block $s$ und haben die Eingabe $(x,0,y,0,...)$, da wir x bereits aus der vorhergehenden Schleife wissen, $R_1$ aufgrund der Dekrementierung auf $0$ ist und somit nur noch $R_2 = y$ verbleibt, was wir in dieser Schleife genau $R_1 = y$ Mal dekrementieren und $R_0 = x$ somit um die gleiche Anzahl inkrementieren. Wir haben hier ebenfalls drei Schritte bis wir wieder in Block $s$ angekommen sind. Als Ergebnis erwarten wir somit wieder in Block $s$ zu sein und folgende Registerbelegung zu haben: $(x+i, 0, y-i, 0, ...)$, da $i$ genau die Anzahl ist, die wir die Schleife durchlaufen und $y$ dekrementiert und $x$ inkrementiert haben. Hier ist dann auch schon die Annahme: $ES^{3i}(s,(x,0,y,0,...) = (s,(x+i,0,y-i,0,...))$. Für diese führen wir nun den Induktionsbeweis über $i$ durch:

Annahme: $ES^{3i}(s,(x,0,y,0,...) =$ $(s,(x+i,0,y-i,0,...))$

Zu beweisen ist die Behauptung:

$ES^{3(i+1)}(s,(x,0,y,0,...) = (s,(x+(i+1),0,y-(i+1),0,...))$

Auch hier einfach ausrechnen:

$ES^{3i+3}(s,(x,0,y,0,...) = (s,(x+i+1,0,y-i-1,0,...))$

D.h. am Ende unseres Beweises muss $(s,(x+i+1,0,y-i-1,0,...))$ rauskommen.

Wir fangen an:

$ES^{3i+3}(s,(x,0,y,0,...) = ES^{3}$$(s,(x+i,0,y-i,0,...))$ (wieder den rechten Teil der Annahme einsetzen und ab jetzt das Diagramm durchspielen)

= $ES^{2}(t,(x+i,0,y-i,0,...))$ (nun sind wir in Block t)

= $ES(t,(x+i+1,0,y-i,0,...))$ (nun sind wir in Block u)

= $(s,(x+i+1,0,y-i-1,0,...))$ (nun sind wir an Ende wieder in Block s)

Und auch hier: das Ergebnis entspricht dem rechten Teil der Behauptung. Damit haben wir auch die zweite die Schleife bewiesen.

Die Fälle für $i = 0$ (d.h. man springt im Flussdiagramm direkt durch bis zum $HALT$) habe ich ausgelassen, da sie durch einfaches Ausrechnen offensichtlich sind. Durch die drei Schritte (Flussdiagramm einer allgemeinen Maschine erstellen, Flussdiagramm einer normale Maschine für jede in der allgemeinen Maschine verwendete komplexe Funktion erstellen, Beweis der Korrektheit der normalen Maschinen durch vollständige Induktion) haben wir bewiesen, dass unsere allgemeine Maschine $M$ die Funktion $f(x,y) = x+y$ berechnet. Damit gilt $f_M = f$.

Wie immer: bei Fehlern bitte Bescheid geben.

Buchempfehlung