Update: Formulierungen etwas verständlicher gemacht. Wenn euch das smn-Theorem noch nicht ganz klar, war bitte den Beitrag nochmal lesen.

Update: aus zwei macht drei. Das ist nun hoffentlich der letzte Teil zu KE5 mit einem riesen Beispiel zum smn-Theorem.

Noch einmal die Wiederholung der zwei Anforderungen an vernünftige Programmiersprachen:

• (U) Es soll einen Computer geben, der zu jedem Programm $P$ und jedem möglichen Eingabewert $x$ das Resultat $\sigma(P)(x)$ berechnet und nicht hält wenn $\sigma(P)(x)$ nicht existiert.
• (S) Zu je zwei Programmen $P$ und $Q$ möchte man ein Programm für die Komposition konstruieren können, d.h. es soll eine berechenbare Funktion $h$ geben, so dass $\sigma(h(P,Q)=\sigma(Q) \circ\sigma(P)$.

Während wir (U) mit dem utm-Theorem gut behandeln konnten, schauen wir uns jetzt (S) an:

Lernziel 5

Erklärung und Anwendung des smn-Theorems

Kommen wir nun zum smn-Theorem, unserem Übersetzungslemma. Formal ausgedrückt:

$f \in P^{(2)}$, dann gibt es eine total-rekursive Funktion $r \in R^{(1)}$ mit:

$f(i,j) = \varphi_{r(i)}(j)$ für alle $i,j \in \mathbb{N}$.

Ehm, ja. Was macht das Ding nun?

Im wesentlichen geht es darum, dass sich berechenbare Funktionen kombinieren lassen. Durch die Hintereinanderausführung lassen sich neue Funktionen und somit auch neue Programme (und damit selbstverständlich auch neue Maschinen) mit eigenen Gödelnummern $i$ erschaffen.

Dazu werden die Funktionen einfach hintereinander ausgeführt und die Variable $x$ als Eingabe immer wieder von Maschine zu Maschine "mitgenommen". Da bei diesem Vorgang, abhängig von der konkreten Belegung der Variable $x$ eine neue Maschine erschaffen wird, gibt uns unsere Funktion $r$ diese neue Gödelnummer preis. In dieser Maschine ist die Variable $x$ konkret belegt und fixiert. Variable $j$ nimmt sie jedoch ganz normal an.

Dadurch ist es möglich aus Funktionen mit mehreren Argumenten Funktionen mit nur einem Argument zu erstellen, die jedoch das selbe berechnen (Currying genannt). Wir "fixieren" sozusagen Argumente und codieren sie in unsere neuen Maschinen ein. Am Beispiel unten wird es etwas deutlicher.

Zunächst: $R^{(1)}$ sind die berechenbaren, totalen, einstelligen Funktionen (sie sind überall in $\mathbb{N}$ definiert). Die Funktionen in $P^{(1)}$ müssen nicht überall definiert sein. Im Skript ist das in menschlicher Sprache beschrieben:

"Jedes Programm der Programmiersprache $\psi$ für Zahlenfunktionen mit berechenbarer, universeller Funktion kann mit der Funktion $r$ in die Programmiersprache $\varphi$ übersetzt werden"

Das trifft es eig. ganz gut. Das ist jedoch nicht direkt die Formalisierung unseres $(S)$, der Zusammenhang kommt aber gleich noch.

In der Wikipedia steht zum smn-Theorem auch noch folgender Satz (den ich leicht modifiziert habe damit er besser zu uns passt):

"Die smn - Eigenschaft besagt, dass es zu einem Code $f_M$, der mit den Parametern $i$ und $x$ ausgeführt wird (bzw. ausgeführt werden kann), ein Transformationsprogramm $r$ gibt, das aus $f_M$, $i$ und $x$ ein Programm $f_{M_i}$ berechnet, welches bei der Eingabe von $x$ das gleiche berechnet, wie $f_M$ bei der Eingabe von $i$ und $x$"

Ja, macht Sinn. Formal ausgedrückt:

$f_M(i,x)=r(f_M,i,x)=f_{M_i}(x)$

(Hier sind $i$ und $x$ Argumente, und $f_M$ die Gödelnummer der Ursprungsmaschine, $f_{M_i}$ ist dann die Gödelnummer der Maschine mit dem festgesetzten $i$).

Auch ist es nicht das eig. smn-Theorem, welches sonst überall verwendet wird und die Stelligkeit $m + n$ nutzt, sondern eine abgewandelte Form davon (wie vieles andere im Skript auch), damit es für den Leser nicht zu einfach wird und er Zusatzliteratur heranziehen kann. Wo kämen wir denn hin?!

Als Beweis im Skript wird folgende Idee angebracht:

Zunächst machen wir uns klar, was wir suchen. Wir brauchen eine Maschine für unsere Funktion $r$ aus der Definition.

Wir wir oben sehen, bekommt $f_M$ (also im Endeffekt die Maschine $M$) zwei Parameter übergeben: $i$ und $x$. Dabei geht $f_M$ hin und berechnet die Funktion (welche auch immer) mit ihren zwei Argumenten $i$ und $x$. Was passiert, wenn wir im ersten Schritt nun $i$ in unserer neuen Maschine $M_i$ festsetzen?

Beispiel: $f(i,x)=i+x$

Um diese Funktion zu berechnen brauchen wir eine Maschine $M$, die wir wie folgt definieren:

$M=\{F,{\{1\}}^*\times {\{1\}}^*,{\{1\}}^*,EC^{(2)},AC\}$

Die Eingabecodierung $EC$ ist:

$EC^{(2)}(1^i,^x)=(\epsilon,B,1^{i}B1^{x}B)$

Konkretes Beispiel für $f(2,3)$: $EC^{(2)}(11,111)=(\epsilon,B,11B111B)$. Auf dem Eingabeband stehen also die Eingabeparameter $i$ und $x$ getrennt nebeneinander rechts vom Lesekopf.

Das dazugehörige Flussdiagramm $F$ wäre:

Ausgeschrieben sieht das Flussdiagramm also so aus, nennen wir es mal $\omega\in\Omega^{*}$:

$(0:1:1?,1,4)$

$(1:1:R,2)$

$(2:0:1,3)$

$(3:0:R,0)$

$(4:1:R,4)$

$(5:1:1?,1,6)$

$(6:HALT)$

(Bitte nagelt mich nicht auf das Alphabet $\Omega$ und den korrekten Aufbau der Befehle fest, mir geht es hier nur um das Verständnis)

Was tut es? Es geht Band $1$ von Anfang bis Ende durch: findet es eine $1$, so schreibt es auch eine $1$ auf das Ausgabeband $0$. Findet es ein erstes $B$ (unser Trennzeichen zwischen dem Parameter $1^i$ und $1^x$) auf dem Eingabeband $1$, geht es auf dem Band nach rechts und schaut ob da der zweite Parameter steht. Bis zum nächsten $B$, d.h. dem Ende des zweiten Parameters $1 ^x$ wird nun in jedem Schritt eine weitere $1$ auf das Ausgabeband $0$ geschrieben.

PS: Ihr erinnert euch an das utm-Theorem und unsere $h$-Funktion? Wir können das ausgeschriebene Programm$\omega$ (bzw. seine Gödelnummer ${\nu_{\Omega}}^{-1}(\omega)$) und seine Eingaben auf Bänder unserer universellen Turingmaschine schreiben und es einfach simulieren. Behaltet das mal im Hinterkopf.

Am Ende haben wir also die Ausgabe $f_M(1^i,1^x)=1^{f(i,x)}$

Konkretes Beispiel: $f_M(11,111)=1^5=11111$

Und jetzt kommen wir zum Problem, das wir lösen wollen: wie schaffen wir es eine Maschine anzugeben, die nur einen Parameter $1^x$ hat und dennoch das gleiche Resultat berechnet?

$EC(1^x)=(\epsilon,B,1^i 1^xB)$

Wie können wir denn $1^i 1^x$ berechnen wenn wir gar kein $1^i$ als Eingabeparameter haben?!

Ganz einfach: wir schreiben den Parameter $1^i$ auf das Eingabeband, links neben $1^x$ und rechnen dann wie $M$ weiter. Nehmen wir wieder als konkrete Belegung $i=1^2$ und lassen unser $x$ variabel, was uns zu einer neuen Maschine $M_2$ mit dem Flussdiagramm $F_2$ führt:

Der grüne Teil ist der zusätzliche Part, ich nenne ihn mal $\gamma_2$ (abhängig von $i=2$). Schreiben wir dieses komplette Flussdiagramm $F_2$ aus, so haben wir $\omega_2$ (Achtung, die Marken habe ich aus Faulheit nicht umbenannt. In Wirklichkeit müsste man sie umbenennen, so dass das neue Flussdiagramm $F_2$ auch mit Marke $0$ beginnt. Ich habe für die Marken vor Marke $0$ einfach Buchstaben genommen) als Bandprogramm:

$(A:1:L,B)$

$(B:1:1,C)$

$(C:1:L,D)$

$(D:1:1,E)$

$(E:1:L,0)$

$(0:1:1?,1,4)$

$(1:1:R,2)$

$(2:0:1,3)$

$(3:0:R,0)$

$(4:1:R,4)$

$(5:1:1?,1,6)$

$(6:HALT)$

Nachdem der grüne Teil des Flussdiagramms $\gamma_2$ ausgeführt wurde haben wir auf dem Eingabeband folgende Belegung:

$(\epsilon,B,1^{2}B1^{x}B)$.

Und, oh Wunder, das sieht ja genauso aus wir unsere Eingabecodierung für $1^2,1^x$. Und schwupp, können wir ganz normal wie die ursprüngliche Maschine $M$ (der weiße Teil im Flussdiagramm) weiterrechnen.

Wir Ihr euch leicht vorstellen könnt, können wir auch das für jedes beliebige $i$ machen, indem wir den grünen Part $\gamma$ einfach abhängig von $i$ zu $\gamma_i$ verlängern. Am Ende haben wir damit eine "Quasi-Eingangsbelegung" von:

$(\epsilon,B,1^{i}B1^{x}B)$

Abhängig von $i$ haben wir somit immer eine neues Programm $\omega_i$ mit der Maschine $M_i$ inkl. - selbstverständlich - auch immer einer neuen Gödelnummer $k={\nu_{\Omega}}^{-1}(\omega_i)$.

(Wiederholung: zur Funktion $\nu_{\Omega}(k)$, welche uns zu einer Gödelnummer $k$ das Bandprogramm $\omega$ gibt, ist die Umkehrfunktion ${\nu_{\Omega}}^{-1}(\omega)$. Diese gibt uns zu einem Bandprogramm $\omega$ die zugehörige Gödelnummer $k$).

Wir haben mit unserem Verfahren also das $i$ innerhalb einer Maschine quasi "fixiert". Mit der neuen Gödelnummer $k$ können wir eine universelle Turingmaschine zu füttern und sie mit nur einem Parameter $x$ simulieren, so dass gilt:

$f(i,x) = \varphi_{r(i)}(x)$ für alle $i,x \in \mathbb{N}$ bzw.

$f_M(i,x)=r(f_M,i,x)=f_{M_i}(x)$

Und das Problem? Tja... wir brauchen ein Verfahren, dass uns dieses Flussdiagramm $F_i$ und damit auch das Bandprogramm $\omega_i$ automatisch erzeugt und somit die Gödelnummer $k={\nu_{\Omega}}^{-1}(\omega_i)$ abhängig von einem $i$ berechnet. Dazu gehen wir wie folgt vor:

• Wir basteln uns eine Maschine $N$, welche auf Band $1$ den Parameter $i$ hat
• $N$ schreibt das komplette, initiale Programm $\omega$ auf Band $2$
• Nun schreibt $N$ den grünen Part, also das Teilprogramm (nennen wir es mal $\gamma_i$, abhängig vom $i$ auf Band $3$
• Nun kopiert $N$ das initiale Programm $\omega$ von Band $2$ neben das Teilprogramm $\gamma$ auf Band $3$ und benennt die Marken so um, dass die erste Marke des Teilprogramms $\gamma$ zuerst ausgeführt wird und anschließend in die erste Marke vom initialen Programm $\omega$ mündet.
  Also praktisch genau das, was wir mit $A-E$ gemacht haben, nur eben nicht so faul wie ich, sondern tatsächlich mit natürlichen Zahlen. Da das initiale Programm $\omega$ auch mit der Marke $0$ anfängt, müssen diese beim Kopiervorgang selbstverständlich auch umbenannt werden.
• Am Ende steht auf Band $3$ also ein komplett neues Programm $\omega_i$, dass wir interpretieren können.
• Der Vollständigkeit halber: da wir nicht den Code, sondern die Gödelnummer interpretieren, müssen wir $\omega_i$ noch in die Gödelnummer umwandeln: $k={\nu_{\Omega}}^{-1}(\omega_i)$

Damit gilt $f_N(1^i)=1^k$ und wir haben unser $r$ gefunden:

$r=\iota^{-1}(f_N(\iota(i)))$

PS: $\iota(i)=1^i$ und $\iota^{-1}(1^i)=i$

Schon wieder diese Iotas! Wollen wir das an dem obigen Beispiel mal durchspielen? Klar doch.

Beispiel: $N$ für $f(i,x)=i+x$

Wir nutzen wieder unser $M$ inkl. Flussdiagramm $F$ von oben für die Berechnung der zweistelligen Funktion $f$, sowie auch das ausgeschriebene Programm $\omega$ davon.

• Mit der Maschine $N$ und dem Programm $\omega$ der initialen, zweistelligen Maschine $M$ bekommen wir für $f_N(1^i)=1^k$ die Gödelnummer von $M_i$.
• $r$ wäre dann:$\begin{array}{ll}r(i)&={\iota}^{-1}(f_N({\iota}(i)))\\&={\iota}^{-1}(f_N(1^i))\\&={\iota}^{-1}(1^k)\\&=k\end{array}$
• Damit haben wir zu einem $i$ die Gödelnummer $k$ einer Maschine, die uns zu jedem $x$ die korrekte Funktion $\varphi_k(x)=f(i,x)$ berechnet.

Konkretes Beispiel? Aber sicher!

Konkretes Beispiel: $N$ für $f(2,3)=2+3=5$

Die Gödelnummern halte ich willkürlich, da die konkrete Berechnung ja nicht unbedingt wichtig ist. Tun wir also einfach so, als wäre die von $N$ errechnete Gödelnummer von $M_2$ einfach $k=1^44$

• $N$ startet also mit $i=2$ auf Band $1$, schreibt das initiale Programm $omega$ auf Band $2$ und das Teilprogramm $\gamma_2$ (grün) auf Band $3$. Die Bänder von $N$ sehen nun so aus (ich habe der Übersichtlichkeit halber (okay, ich gebe es zu, ich war wieder zu faul) nicht die ganzen Programme $\omega$ und $\gamma$ auf die Bänder gepackt):
• Jetzt geht $N$ hin und kopiert das initiale Programm $\omega$ von Band $2$ links neben $\omega$ auf Band $2$ und benennt die Marken um (in unserem Beispiel sind die schon umbenannt - statt in Zahlen in Buchstaben, aber dennoch umbenannt -; normal würde das Teilprogramm auch mit $0$ statt $A$ starten usw.). Band $3$ sieht dann so aus:

Leider ist die Grafik etwas klein geraten, Sorry. Am Ende steht also unser komplettes Programm $\omega_2=\gamma_2\cdot\omega$ auf Band $3$ mit umbenannten Marken, bereit zur Ausführung. Naja, fast bereit. Denn das Programm $\omega_2$ selbst ist ja nicht ausführbar, sondern nur seine Gödelnummer.

• Und die bekommen wir, indem wir zum Programm $\omega_2$ nun seine Gödelnummer ${\nu_{\Omega}}^{-1}(\omega_2)=1^44$ (nicht vergessen, $1^44$ ist die willkürliche Gödelnummer für $\omega_2$, die wir uns ausgedacht haben) berechnen. Wir wissen ja, dass wir durch die Ordnungsfunktion auf dem Alphabet unserer Bandprogramme auch eine Standardnummerierung haben.
  Die Funktion ${\nu_{\Omega}}^{-1}$ ist, wie wir im Beitrag zur Standardnummerierung gezeigt haben, berechenbar. Ich gebe hier also nicht extra ein Flussdiagramm einer Maschine an, dass uns zu den Zeichen des Programms $\omega_2$ auf Band $3$ anhand der Ordnungsfunktion die Gödelnummer berechnet. Wir könnten es aber problemlos.

Damit gilt letztendlich: $f_N(11)=1^44$. Nur noch die $1^44$ mit unseren Iotas ($\iota$) in Dezimaldarstellung umwandeln und wir sind fertig:

$\begin{array}{ll}r(2)&=\iota^{-1}(f_N(\iota(2)))\\&=\iota^{-1}(f_N(1^2))\\&=\iota^{-1}(1^44))\\&=44\end{array}$

Füttern wir die Maschine mit der Gödelnummer $44$ $M_2=\nu_M(\omega_2)$ nun mit unserem $x=5$, so bekommen wir  $f_{M_2}(2)=5$, was genau das gleiche ist wie $f_M(2,3)=5$, das Ergebnis unserer Ursprungsmaschine $M$ mit zwei Parametern.

Fertig.

Münzen wir das beispiel konkret auf das smn-Theorem, so bedeutet es:

$f(2,3) = \varphi_{r(2)}(3)=\varphi_{144}(3)=5$ für $i=2$ und $x=3$ bzw.

$f_M(2,3)=r(f_M,2,3)=f_{M_2}(3)=5$

PS: nicht vergessen: $f_M$ ist dabei unser Ursprungsprogramm $\omega$, dass für $N$ natürlich fest vorgegeben ist. Es ändert sich nicht, egal welches $i$ oder $x$ wir haben, daher können wir es für alle Eingaben fest vorgeben.

Und wenn Ihr nach oben, in die Definition vom smn-Theorem schaut, ist es genau die Definition, nur mit unseren Werten für $i$ und $x$ gefüllt.

Rekapitulieren wir: alles, was unser Programm $r$ bzw. die Maschine $N$ macht, ist uns ein festes Argument zusammen mit dem Quellcode des Urspungsprogramms in eine neue Maschine zu codieren und uns dazu die zugehörige Gödelnummer anzugeben. Mit unserer universellen Turingmaschine $u_\varphi$ (utm-Theorem) können wir diese neue Maschine mit den verbliebenen, nicht fixierten Argumenten interpretieren. Nur der Zusammenhang zu $(S)$ ist euch wahrscheinlich noch nicht klar. Aber darum kümmern wir uns jetzt.

Die Eigenschaft $(S)$ (d.h. die effektive Komposition) gefordert wird. Wenn man also zwei Programme einer Sprache komponieren kann, ist das smn-Theorem erfüllt und umgekehrt. Das liegt an einer Kleinigkeit, unserer Funktion $r$ aus dem smn-Theorem.

Zusammenhang zwischen effektiver Komposition und dem smn-Theorem

Wir schauen uns nochmal die Forderung (S) an, welche an Programmiersprachen gestellt wird:

• (S) Zu je zwei Programmen $P$ und $Q$ möchte man ein Programm für die Komposition konstruieren können, d.h. es soll eine berechenbare Funktion $h$ geben, so dass $\sigma(h(P,Q)=\sigma(Q) \circ\sigma(P)$.

Während die Funktion $r$ in ihrer ursprünglichen Form, $r: \mathbb{N} \rightarrow\mathbb{N}$ mit $r(i) = k$ einen Index/Gödelnummer für eine neue Maschine ausgibt, damit $f(i,x) = \varphi_k(x)$ gilt, gibt uns die gleiche Funktion, jedoch mit dem Definitionsbereich $\mathbb{N}^2$, d.h.  $r: \mathbb{N^2} \rightarrow\mathbb{N}$ (die Funktion $r$ bekommt also zwei Parameter aus $\mathbb{N}$ übergeben) auch nur einen Index einer Maschine. Dieses Mal jedoch den Index/Gödelnummer einer Maschine, die zwei Ursprungsmaschinen mit den Indizes $i$ und $j$ zusammenschaltet, so dass gilt:  $f(<i,j>,x) = \varphi_i(\varphi_j(x))$. That's it.

Funktionieren tut das genauso wie beim Beispiel zum smn-Theorem:

(Danke an Herbert für seinen Beitrag zum Thema in der NG)

• Dazu werden die Marken aus dem Flussdiagramm der Maschine $i$ erhöht/umbenannt. Und zwar um den Wert der größten Marke aus dem Flussdiagramm der Maschine $j$ damit es in der neuen Maschine keine gleichen Marken gibt, denn es könnte aus beiden Maschinen Marken mit der gleichen Nummer geben.
• Dann wird aus der $HALT$-Marke von Maschine $i$ in die Startmarke der Maschine $j$ und wir haben eine Zusammenschaltung und nur eine einzige Maschine aus zwei gebaut.
• Das können wir natürlich beliebig kombinieren, so dass unser $r$ wie folgt definiert wird: $r: \mathbb{N}^m \rightarrow\mathbb{N}$. Die "Übersetzungsleistung" besteht hier nicht von einer Sprache in die andere, sondern in einer Zusammenschaltung von zwei Maschinen in eine durch Umbenennung der Marken und Verknüpfen der Flussdiagramme, so dass wir am Ende aus zwei Flussdiagrammen nur noch eines haben.

Wir können im Endeffekt also eine beliebige Anzahl ($m$) von Maschinen zusammenschalten, so dass wir am Ende nur eine Maschine haben. Jetzt können wir uns auch die übliche Definition der Funktion $r$ herleiten, die normal $s$ heißt:

$s_n^{m}:\mathbb{N}^{m+1} \rightarrow \mathbb{N}$ mit $\varphi_{s_n^{m}(i,y_1,...,y_m)}(z_1,...,z_n) = \varphi_i(y_1,...,y_m,z_1,...,z_n)$

Und hier verstehen wir auch warum sich das Theorem eben smn-Theorem nennt. Die Funktion besagt nichts anderes, als dass wir $m$ Maschinen zusammenschalten und somit in eine überführen/transformieren können, die mit $n$ Argumenten gefüttert werden kann und das selbe Ergebnis hat wie die ursprüngliche Maschine. Und das ist ja genau unser Wunsch nach einer Komposition aus Forderung $(S)$.

Klar geworden? Damit haben wir nun auch unser $(S)$ abgehakt.

Antwort zum Lernziel: mit dem smn-Theorem ist es uns nicht nur möglich Eingabeparameter einer Maschine fest zu codieren und zur neu erzeugten Maschine eine Gödelnummer anzugeben, die um einen Eingabeparameter (den fest codierten) weniger benötigt und dennoch das gleiche Ergebnis berechnet (um Currying zu unterstützen), sondern wir können mit dem smn-Theorem auch Funktionen, d.h. Maschinen zusammenschalten um eine Forderung an gute Programmiersprachen zu erfüllen: (S) die Forderung nach einer effektiven Komposition.

Das funktioniert durch ein Zusammenfügen der Flussdiagramme, bzw. Befehle der Maschinen bei gleichzeitiger Umbenennung der Marken, so dass z.B. die $HALT$-Marke einer Maschine statt zu halten nun auf die Anfangsmarke der anderen Maschine verweist.

Zusammen mit dem utm-Theorem bilden sie das Grundgerüst für gute Programmiersprachen: (S) und (U).

Lernziel 6

Erläuterung des Äquivalenzsatzes für Nummerierungen (Rogers)

Wir machen uns zunächst klar, dass wir mit $\varphi$ eine eigene Programmiersprache entwickelt haben. Wir konnten mit dieser alle Funktionen aus $P^{(1)}$ nummerieren und diese auf unseren universellen Turingmaschinen ausführen.

Zwar haben wir die Syntax und die Notation dieser Bandbefehle willkürlich gewählt. Das ist aber gar nicht tragisch, denn die Nummerierung im Skript ist genauso gut wie jede andere. Vorausgesetzt sie erfüllt das utm- (universelle Turingmaschine) und das smn- (Übersetzungslemma) Theorem. Dann sind die Nummerierungen nämlich äquivalent zueinander, da sie ineinander überführbar sind.

Der Äquivalenzsatz von Rogers besagt formal:

Sei $\psi$ eine Nummerierung von $P^{(1)}$, dann sind folgende Eigenschaften äquivalent:

1. $\psi \equiv \varphi$

2. $\psi$ erfüllt das utm- (universelle Funktion von $\psi$ ist berechenbar) und das smn- (Berechnung der Nummer eines Programms und damit z.B. die Übersetzung in eine andere Programmiersprache) Theorem.

Damit lassen sich alle Programme, die beide Theoreme erfüllen durch "Übersetzer" $g,h\in R^{(1)}$ ineinander übersetzen. D.h. soviel wie:

$\varphi=g(\psi)$ und

$\psi=h(\varphi)$.

Wir können uns daher auf eine Nummerierung beschränken wenn sie die beiden Theoreme erfüllt. Unser $\varphi$ ist somit genauso gut wie jede andere Nummerierung (die natürlich auch das utm- und das smn-Theorem erfüllen muss).

Antwort zum Lernziel: nach dem Äquivalenzsatz von Rogers sind alle Programmiersprachen/Nummerierungen äquivalent wenn sie das utm- und das smn-Theorem erfüllen.

Hat man also eine andere Programmiersprache/Nummerierung $\psi:\mathbb{N}\rightarrow P^{(1)}$, die beide Theoreme erfüllt, so sind diese äquivalent, d.h. $\varphi\equiv\psi$ und können mit "Übersetzern" ineinander überführt werden.

Lernziel 7

Formulieren des Rekursionssatzes

Dieser Satz wird auch Fixpunktsatz von Kleene genannt. Ich fand es persönlich einfacher von der anderen Seite an diesen Satz heranzugehen, die Skripte der HU Berlin gehen einen ähnlichen weg. Aber fangen wir mal an: ein schönes Beispiel für den Rekursionssatz ist die Selbstreproduktion. Wir wollen also ein Programm, dass bei einer beliebigen Eingabe sich selbst ausgibt. Dazu ist der Rekursionssatz hilfreich.

Formal ausgedrückt:

Zu jeder Funktion $f \in R^{(1)}$ gibt es eine Zahl $n$ mit $\varphi_n = \varphi_{f(n)}$.

Was bedeutet das nun genau und was ist $n$? $n$ ist die Gödelnummer einer Maschine, also quasi unser in natürliche Zahlen codierter Programmcode (kennt Ihr schon, Thema Standardnummerierung). Unsere Programmtransformationsfunktion $f$ bekommt als Eingabe diese Gödelnummer $n$, rechnet darauf rum und gibt uns als Ausgabe eine Gödelnummer $f(n)=k$ aus.

Wenn wir nun die Maschine mit der Gödelnummer $k$ und dem Parameter $x$ starten ($\varphi_k(x)$), so bekommen wie die gleiche Ausgabe, die unser Programm mit der Gödelnummer $n$ und dem Parameter $x$ gehabt hätte ($\varphi_n(x)$), d.h.

$\varphi_n(x) = \varphi_{f(n)}(x)$

Umgangssprachlich gesprochen: Wir können $f$ als eine "Programmumschreibefunktion" betrachten. Nach diesem Satz gibt es Programme, die in ihrer Funktion von unserer Programmtransformationsfunktion $f$ nicht verändert werden. Aber Achtung: nur in der Funktion, d.h. es könnten Programmteile abgeändert oder hinzugefügt werden, die nicht zur Ausführung kommen. Die korrekte und gleiche Funktion/Ausgabe des Programms ist damit dennoch gegeben.

$n$ wird deswegen auch der semantische Fixpunkt der Modifikationsfunktion $f$ genannt.

Damit ist es uns z.B. erlaubt Maschinen zu erstellen, welche eine Beschreibung von sich selbst berechnen und benutzen können. Das ist keineswegs selbstverständlich! Denn lange Zeit galt diese sog. Selbstreproduktion, d.h. Maschinen, die sich selbst nachbauen ohne sich selbst zu enthalten als unmöglich.

Alle Erfindungen, die andere Dinge herstellten wie z.B. eine Autofabrik oder Werkzeughersteller sind komplexer als das erzeugte Produkt und brauchen eine Beschreibung des herzustellenden Produktes. Damit wäre die Selbstreproduktion aber unmöglich, denn um einfache Produkte zu bauen, braucht man komplexe.

Und genau das ist der Trugschluss, den von Neumann 1966 aufgezeigt hat, indem er theoretisch eine einfache Maschine konstruierte, die sich selbst reproduzieren kann:

Diese Maschine besteht aus drei Teilen:

• dem Konstrukteur $K$
  Der Konstrukteur bekommt die Beschreibung einer Maschine (mathematisch gesehen also z.B. unsere Gödelnummer $i$) und setzt diese dann mit den Bauteilen zusammen, so dass wir eine Maschine mit $\varphi_i$ bekommen.
• dem Kopierer $C$
  Der Kopierer kann den Bandinhalt von einem Band auf ein anderes kopieren, so dass am Ende zwei Bänder mit dem selben Inhalt als Ausgabe ausgegeben werden.
• der Steuerung $S$
  Die Steuerung kümmert such um Konstrukteur und Kopierer und versorgt beide mit Eingaben.

Was wir also brauchen ist, eine Maschine $M$, die bei der Eingabe von sich selbst, sich selbst reproduziert. Und so sieht dann die Maschine aus:

Wir geben den Bauplan $i$ in die Steuerung, diese gibt sie an den Kopierer, welcher den Bauplan verdoppelt. Eine Kopie wird an den Konstrukteur übergeben, der daraus eine neue Maschine $M_i$ baut. Und eben diese neue Maschine (der "Sohn") bekommt dann von seinem "Vater" den Bauplan ausgehändigt und baut dann den "Enkel", eine exakte Kopie von sich selbst usw.

Und nun wieder zurück zur theoretischen Informatik:

Wir haben damit eine Möglichkeit zur Selbstreproduktion und können Maschinen angeben, die sich selbst ausgeben können. Mit dem Rekursionssatz ist es also sichergestellt, dass es ein Programm gibt, welches bei allen möglichen Eingaben sich selbst ausgibt. Eine Anwendung sind z.B. die Quines, denn sie geben bei jeder Ausgabe sich selbst aus, damit gilt der Satz über Selbstreproduktion:

Es gibt eine Zahl $n$, so dass $\varphi_n(x) = n$ für alle $x$.

Wer könnte denn an sowas interessiert sein? Außer Skynet. Viren zu Beispiel.

Just als ich den Beitrag getippt habe, fliegt mir ein Satz Folien um die Ohren, die ich euch nicht vorenthalten will: Folien zur Selbstreproduktion der Uni Potsdam.

Antwort zum Lernziel: Der Rekursionssatz von Kleene besagt, dass man zu einem gegebenen Modifikationsprogramm $f$ immer einen Quelltext finden kann, der trotz Modifikation seine Aufgabe weiterhin erfüllt. Da sich die Semantik des Programms somit nicht ändert wird dieser Quelltext (das $n$) auch semantischer Fixpunkt von $f$ genannt.

Ein Anwendungsbereich dieses Satzes ist die Selbstreproduktion, so dass die Ausgabe von sich selbst der Fixpunkt ist (das Programm gibt sich selbst aus) und es gelten muss: $\varphi_n(x)=n$, egal was man als $x$ eingibt.

Puh, das war ein Haufen arbeit. Wie immer gilt: sollten sich Fehler eingeschlichen haben: bitte wieder Bescheid geben. Danke auch an die Kollegen aus der NG, die so manche einleuchtende Erklärung eingeworfen und zu diesem Text beigetragen haben. Schade, dass die NG jedes Semester gelöscht wird. So verwindet manch eine schöne Erläuterung im digitalen Papierkorb. Vielleicht trägt der Blog ja etwas dazu bei, dass einige Erläuterungen über das Haltbarkeitsdatum der NG bestehen bleiben.

Update 2: Fehler korrigiert. Danke Max.

Update 2: Merksatz zum Lernziel hinzugefügt.

Update: aus zwei Beiträgen habe ich mittlerweile drei gemacht. Die Ladezeiten vom smn-Theorem waren ja nicht zu ertragen.

Nun Teil 2 der Kurseinheit 5. Nachdem wir in Teil 1 die Standardnummerierung $\varphi$ und die Standardkomplexität $\Phi$ und das $\Phi$-Theorem behandelt haben, folgen in diesem und dem nächsten Teil die zwei weiteren Theoreme. Der letzte Beitrag war mit acht Seiten schon relativ lang, hoffentlich wird dieser was kürzer.

Zu früh gefreut, das Beispiel im nächsten Beitrag zum smn-Theorem hat mich ebenfalls 8 Seiten gekostet, daher die Beitragstrennung und der letzte Beitrag der Serie zu KE5 von TIA ist:

• TIA: smn-Theorem (Lernziele KE5, 3/3)

Starten wir zunächst mit einigen Anforderungen an vernünftige Programmiersprachen:

Es gibt zwei Anforderungen an vernünftige Programmiersprachen, die im Skript zu Anfang behandelt wurden. Das sind

• (U) Es soll einen Computer geben, der zu jedem Programm $P$ und jedem möglichen Eingabewert $x$ das Resultat $\sigma(P)(x)$ berechnet und nicht hält wenn $\sigma(P)(x)$ nicht existiert.
• (S) Zu je zwei Programmen $P$ und $Q$ möchte man ein Programm für die Komposition konstruieren können, d.h. es soll eine berechenbare Funktion $h$ geben, so dass $\sigma(h(P,Q)=\sigma(Q) \circ\sigma(P)$.

Auch wenn die Programmiersprache RPG wahrscheinlich beide Voraussetzungen erfüllt, vernünftig wird sie dadurch trotzdem nicht. Aber bevor IBM-Fans mir die Fensterscheiben einwerfen machen wir lieber weiter im Text

Lernziel 4

Anwendung und Erläuterung des utm-Theorems

Für die Formalisierung des utm-Theorems brauchen wir zunächst eine hilfreiche Funktion, die wir im letzten Beitrag bereits definiert und als berechenbar bewiesen hatten:

$h:\mathbb{N}^3 \rightarrow \mathbb{N}$  mit

$h(i,n,t) = \begin{cases} 1+\varphi_i(n), & \mbox{ falls } \Phi_i(n) \mbox{ existiert und } \Phi_i(n) \leq t\\ 0, & \mbox{ sonst }\end{cases}$

Ich werde das jetzt nicht groß ausführen, steht ja alles im ersten Teil der Lernziele zu KE5, sondern sage euch nur schnell noch einmal, was sie macht: Wir bekommen eine $1+$ das Ergebnis der Maschine mit der Nummer $i$ bei der Eingabe von $n$ wenn die Standardkomplexität $\Phi_i$ existiert und kleiner/gleich $t$ ist (die Berechnung von $i$ bei der Eingabe von $x$ ist noch vor $t$ Schritten abgeschlossen). Ansonsten gibt es nur eine Null zurück. Fair.

Wie hilft diese Funktion uns nun beim utm-Theorem?

Das utm-Theorem ist definiert als

$u_\varphi :\subseteq \mathbb{N}^2 \rightarrow \mathbb{N}$ mit

$u_\varphi(i,x) := \varphi_i(x)$ für alle $i,x \in \mathbb{N}$.

$u_\varphi$ ist dann berechenbar und wird die universelle Funktion von $\varphi$ genannt

Aber wahrscheinlich fügen sich bei euch noch nicht alle Puzzle-Teile zu einem Bild zusammen. Vielleicht holen wir daher zunächst etwas weiter aus: eine universelle Turing-Maschine ist eine Maschine, die beliebige andere Maschinen simulieren kann.

Wie wir im vorherigen Beispiel gesehen haben, können wir einer Turing-Maschine eine andere Maschine und das Eingabewort als Parameter mitgeben und so diese Maschine simulieren. Am Ende kopiert unsere universelle Maschine die Ausgabe auf Band $0$ und wir sind fertig (nur, dass wir im vorherigen Beitrag noch eine $1$ zum Ergebnis addiert haben). Die Maschine agiert also als eine Art Interpreter und ist nicht auf die Berechnung einer einzigen Funktion beschränkt.

Was haben wir dazu nun gemacht? Die Turing-Maschinen sprechen nur unär, d.h. Zeichen aus unserem Bandprogramm $\omega\in BP$ mit $\omega=(1^2:1,,1)$, mit unseren Klammern, Kommas und Doppelpunkten können wir eigentlich gar nicht interpretieren.

Doch, das können wir! Und zwar mittels der Nummerierung $\varphi$. Im obigen Beispiel stehen diese zwar im Klartext auf dem Band, aber nur der Übersichtlichkeit halber. Wenn Ihr euch statt einer öffnenden Klammer $($ nun ihren Nummerierungswert der Ordnungsfunktion $a\rightarrow\nu_\Omega$ ($a("(")=3$)auf dem Band denkt, dann ist das Jacke wie Hose. Im ersten Teil haben wir gezeigt, dass das durch die Ordnungsfunktion wunderbar funktioniert.

Nachdem wir nun diese Maschine in Zahlen überführt haben, haben wir eine sog. Gödelisierung durchgeführt. Die Codierung, die am Ende für die Maschine herauskommt ist die sogenannte Gödelnummer. Das formale utm-Theorem ist die formale und etwas abstrakte Version dieser universellen Turing Maschine, denn sie erfüllt die am Anfang gestellte Forderung $(U)$ (siehe oben).

Wir können nämlich mit diesem Computer $U$ (unsere universelle Turing-Maschine) zu jedem Programm $P$ (welches wir vorher entsprechend codiert haben), das mit einem Eingabewert $x$ gefüttert werden würde, durch die Simulation/Interpretation von ihm, sein Ergebnis berechnen, also genau unser gesuchtes $\sigma(P)(x)$.

Das utm-Theorem bedeutet also nichts anderes, als dass eine Funktion $u_\varphi(i,x)$ (sie nimmt also die Nr. der zu simulierenden Maschine und die Eingabe für sie als Parameter auf) berechenbar ist wenn sie als Ausgabe $\varphi_i(x)$ (also genau das Ergebnis der simulierten Maschine $i$) hat. Genau das bedeutet die obige formale Definition des utm-Theorems.

$u_\varphi(i,x) := \varphi_i(x)$ für alle $i,x \in \mathbb{N}$.

Jetzt müssen wir also nur noch eine Maschine angeben, die $u_\varphi$ berechnet. Unsere Funktion $h$ von oben leistet uns hier große Dienste: während wir bei $h(i,n,t)$ im Parameter $t$ genau angeben mussten, wie lange die simulierende Maschine rechnen darf, wollen wir bei $u_\varphi$ eig. nur das Ergebnis haben und nicht angeben, wie lange unsere Maschine zu rechnen hat. Das $t$ ist uns also egal. Und das geht ganz einfach.

Beispiel: wir simulieren das Programm $h$, welches unser Programm $(1^2:1,,1)(:1,1,1^2)(:B,,)$ mit der Gödelnummer $n_1$ simuliert, in einer Schleife und zählen unser $t$ ab $1$ einfach hoch. Eingabe bleibt $n = 3$.

1. Führe $h(n_1,3,1)$ aus und speichere es in $R_0$
2. Wenn $R_0 = 0$ (wir haben die $HALT$-Marke im Programm mit unserem $t=1$ noch nicht erreicht und bekommen daher eine $0$ als Ausgabe), erhöhe $t$ um eins und führe dann $h(2,3,2)$ aus, usw.
3. Wenn $R_0$ eine Ausgabe ungleich $0$ hat, dann subtrahiere eine $1$ vom Ergebnis (in $h$ haben wir es ja immer um Eins erhöht) und beende dich.

Dam Ende steht in $R_0$ das Ergebnis ($3$) und wir haben unser kleinstes $t = 8$ auch. Es wird im Skript im Register $R_3$ zwischengespeichert. Damit ist auch $u_\varphi$ berechenbar.

Im Skript wird eine weitere universelle Funktion für die Standardkomplexität, nämlich $u_\Phi$ definiert:

$u_\Phi :\subseteq \mathbb{N}^2 \rightarrow \mathbb{N}$ mit

$u_\Phi(i,x) := \Phi_i(x)$ für alle $i,x \in \mathbb{N}$.

Sie macht nicht viel anders als $u_\varphi$. Wir bekommen hier jedoch nicht das Ergebnis $\varphi_i(x)$ als Ausgabe, sondern das kleinste $t$ (die Anzahl der Rechenschritte, Schrittzahlfunktion, wir erinnern uns?) bei der Eingabe von $x$, also genau $\Phi_i(x)$. Das Ergebnis schreiben wir ins $R_0$, dem Ergebnisregister der berechnenden Maschine und sind fertig.

Zusammenhang zu $R^{(1)}$

Nachdem ich gemerkt habe, dass ich einige Details von $P^{(1)}$ und $R^{(1)}$ durcheinander brachte und freundlich von Harald und Carsten aus der NG darauf hingewiesen wurde, habe ich mich entschlossen das hier auch nieder zu schreiben. Obwohl ich der Meinung bin, dass die meisten von euch die Unterschiede zwischen den beiden Mengen gut bewusst sind und sie keine Auffrischung brauchen, bin ich mir sicher, dass ich das in spätestens einigen Monaten vor der Prüfungsvorbereitung wieder verdrängt habe. Also tue ich etwas für mein "Zukunfts-ich" (How i met your mother lässt grüßen) und schreibe in aller Deutlichkeit nochmal:

$P^{(1)}$: partielle (nicht überall definierte), berechenbare Funktionen. Nummerierung $\varphi$ von $P^{(1)}$ erfüllt das utm-Theorem, d.h. es gibt eine universelle Turingmaschine, die die Funktion interpretiert und die entsprechende Ausgabe berechnet.

$R^{(1)}$: totale (überall definierte), berechenbare Funktionen. Keine Nummerierung von $R^{(1)}$ erfüllt das utm-Theorem (es gibt also keine universelle Funktion $u$ zum interpretieren des Programms).

Die letzte Feststellung ist wichtig: warum erfüllt keine Nummerierung von $R^{(1)}$ das utm-Theorem? Denn es wäre doch - wie im Skript angemerkt - praktisch wenn man sich nur auf überall definierte Funktionen beschränken könnte. Was nützt einem ein Programm, dass bei einer Eingabe ggf. nicht hält? Leider geht das nicht. Die Beweisidee ist wie folgt:

Zunächst: was ist eine Nummerierung? Einfach nur die Nummer einer Funktion. Während wir also $P^{(1)}$, die einstelligen, berechenbaren, ggf. partiellen Funktionen mit $\varphi$ nummeriert haben und diese Funktion (bzw. die Maschinen, die die Funktionen berechnen) durch eine universelle Turingmaschine mit $u_\varphi(i,x)=\varphi_i(x)$ simulieren, können, bekommen wir bei $R^{(1)}$ ein Problem.

Warum? Während $\varphi_i(x)$ nicht für jedex $x$ definiert sein muss, d.h. es auch eine Ausgabe $\varphi_i(x)=div$ geben kann, haben wir bei dem gleichen Spiel mit $\psi$, der Nummerierung von $R^{(1)}$ immer eine Ausgabe. Ist ja auch klar, die Funktionen aus $R^{(1)}$ sind total und damit eben für jedes $x$ definiert.

In was für ein Problem laufen wir hier?

Wir nehmen eine Nummerierung $\psi$ von  $R^{(1)}$. Lt. utm-Theorem gibt es dazu eine universelle Funktion $u_\psi(i,x)=\psi_i(x)$, d.h. eine universelle Turing-Maschine, welche als Eingabe die Gödelnummer/den Index der Maschine und ein $x$ bekommt und diese so simuliert (siehe das 2. Beispiel für $h$ von oben), dass auf Band $0$ anschließend die Ausgabe $\psi_i(x)$ steht.

Nun basteln wir uns eine Funktion $h(i)=u_\psi(i,i)+1$. Diese ist auch total und berechenbar, da $\psi(i,i)$ ja selbst total und berechenbar war. D.h. die universelle Funktion $u$ simuliert uns die Maschine $i$ mit der Eingabe $i$ und addiert eine $1$ dazu. Sie ist damit definitiv von $\psi(i,i)$ verschieden und somit eine neue Maschine.

Da es eine komplett neue Maschine ist, hat sie natürlich auch eine neue Gödelnummer/einen neuen Index $k$. Da wir aber alle totalen Funktionen bereits durchnummeriert haben, ist $h(k) = \psi_k(k) = \psi_k(k)+1$, was aber nicht funktioniert. Denn $\psi_k(k)$ existiert ja bereits in unserer Auflistung und kann ja gar nicht eine neue Maschine sein.

Das ist wieder ein Beweis durch Diagonalisierung: wir sind von der Vollständigkeit unserer Auflistung ausgegangen und haben offensichtlich trotzdem noch eine neue Maschine erstellen können, was uns zu einem Widerspruch führt. Damit erfüllt keine Nummerierung nur der totalen, berechenbaren Funktionen $R^{(1)}$ das utm-Theorem.

Und was ist mit $P^{(1)}$? Damit klappt es:

Wir gehen zunächst genauso vor, wie bei $R^{(1)}$: holen uns eine Nummerierung mit $\varphi$ und eine universelle Funktion $u_\varphi(i,x)=\varphi_i(x)$.

Nun erstellen wir die neue Funktion: $h(i)=u_\varphi(i,i)+1$. Da $\varphi(i,i)$ nicht total sein muss (für ein $x$ kann $\varphi(i,x)=div$ sein), könnte $h(i)=u_\varphi(i,i)+1$ ebenfalls nicht total sein und die Aussage $h(k)=\varphi_k(k)=\varphi_k(k)+1$ hätte durchaus Bestand: $h(k)=\varphi_k(k)=div=\varphi_k(k)+1=div+1=div$.

Ist tatsächlich etwas abstrakt, aber hoffentlich trotzdem nachvollziehbar.

(Hier geht ein großer Dank an Barbara, Harald, Oliver und Herbert aus der NG für ein paar - wenn auch hinkende - Vergleiche Wenn jemand in "einfacheren Worten" eine Erklärung hat, warum eine Nummerierung für $P^{(1)}$ das utm- Theorem erfüllen kann, aber keine Nummerierung für $R^{(1)}$ das zu leisten vermag, der möge mir bitte eine Nachricht schicken. Ich würde das dann gerne hier aufnehmen)

Antwort zum Lernziel: bei dem utm-Theorem geht es im Grunde um die Frage ob es einen Computer gibt, der jeden anderen Computer simulieren kann. In der theoretischen Informatik wäre es zwar unproblematisch für jede Aufgabe eine eigene Maschine anzugeben, ist aus praktischer sicherlich kein gangbarer Weg.

Diese Fragestellung hat große Bedeutung bei den Programmiersprachen, denn nur durch die Bejahung dieser Frage können Programmiersprachen durch Computer interpretiert und so Anwendungen auf ihnen ausgeführt werden.

Daher betrachten wir den Computer als universelles Gerät, dass Programme (andere Computer sozusagen, die nur eine Funktion berechnen) und Daten entgegen nimmt und die Funktion des Programms auf den entgegen genommenen Daten simuliert.

Frage ist hierbei: gibt es denn so eine Funktion, die auf einer Turingmaschine ausgeführt, eine andere Funktion simulieren kann? Und genau diese Funktion wird universelle Funktion $u$ genannt, die als Eingabe eine Gödelnummer $i$ des zu simulierenden Programms $\omega$ und die Eingabedaten $x$ entgegen nimmt und auf diesen die Befehle des Programms Schritt für Schritt durchführt um am Ende die gleiche Ausgabe zu haben wie das Programm selbst: $u_\varphi(i,x)=\varphi_i(x)$.

In unserem Beweis im letzten Betrag hat es unsere Funktion $h$ für uns erledigt (wobei sie noch die maximale Anzahl der zu rechnenden Schritte verwendet hatte).

Merksatz:

Das formale utm-Theorem ist die formale und etwas abstrakte Version dieser universellen Turing Maschine. Es besagt, dass eine universelle Funktion existiert, die jede andere berechenbare Funktion berechnen kann.

Im nächsten Beitrag geht es dann um das smn-Theorem und Rekursionssätze.

Update: Tippfehler, Danke Marcel.

Update: Ungenauigkeit beseitigt. Danke Steve.

Update: Fehler beseitigt. Danke Max.

Update: Pfui, da sind mir doch tatsächlich ein paar Funktionen abhanden gekommen. Sind alle wieder im Text. Auch habe ich einen weiteren Betrag verfasst um den Zusammenhang zwischen einer Programmiersprache und $\varphi$ sowie dem utm- und smn-Theorem noch etwas zu verdeutlichen.

Update: Fehler beseitigt.

Update: ein paar Details zur Standardnummerierung $P^{(1)}$ habe ich noch hinzugefügt. Denn die ist nicht bijektiv, sondern nur surjektiv. Das wollte ich unbedingt noch einmal hervorheben, da es im letzten Beitrag so ausgesehen hat, als wären alle Standardnummerierungen bijektiv, was für $P^{(1)}$ nicht stimmt.

Update: beim erneuten Lesen sind mir einige Fehler aufgefallen, die ich nun (hoffentlich) ausgemerzt habe. Auch habe ich die Lernziele etwas umgestellt, so dass sie zwischen den zwei Beiträgen besser passen. Wenn also noch irgendwo Verweise sein sollten, wo sie nicht hingehören: bitte Bescheid geben.

Die Antworten zu den Lernzielen habe ich noch nicht ausformuliert, kommt aber gleich noch.

Weil's so schön war: nochmal entlang der Lernziele, diesmal aus KE5. Die Lernziele zu KE5 bestehen aus zwei drei Beiträgen: diesem hier, dem zweiten und dritten Teil mit:

• TIA: utm-Theorem (Lernziele KE5, 2/3)
• TIA: smn-Theorem (Lernziele KE5, 3/3)

Wir starten im ersten Teil direkt mit dem ersten Lernziel: der Standardnummerierung für $P^{(1)}$

Lernziel 1

Erläuterung der Definition der Standardnummerierung $\varphi$ von $P^{(1)}$

Was eine Standardnummerierung ist, wissen wir bereits aus dem Beitrag zu KE4. Sie ist (im Kontext von KE4) eine bijektive Abbildung zwischen den natürlichen Zahlen $\mathbb{N}$ und einer anderen Menge. Im letzten Beitrag haben wir alle Worte über dem Alphabet $\Sigma$, nämlich $\Sigma^{*}$ standard-nummeriert. In diesem Beitrag kümmern wir uns um die einstelligen, berechenbaren Zahlenfunktionen $P^{(1)}$.

Nur hier gibt es ein kleines Problemchen:

Ihr wisst doch noch, was dort der Unterschied zwischen einer Nummerierung und einer Standardnummerierung ist? Nein? Schämt euch! Wurde alles im letzten Beitrag durchgekauft. Aber trotzdem:

• Eine Nummerierung muss nicht bijektiv sein, Surjektivität reicht.
• Eine Standardnummerierung jedoch ist eine bijektive Abbildung zwischen zwei Mengen.

Durch eine bijektive Abbildung zwischen zwei Mengen zeigen wir unter anderem, dass diese gleichmächtig sind. Wo liegt nun das Problem? Kommt gleich, versprochen! Behaltet einfach erst einmal im Hinterkopf, dass die Bijektion für eine Standardnummerierung unserer $P^{(1)}$ keinen Bestand hat.

Im Skript ist $BM$ die Menge der normierten Bandmaschinen mit dem Alphabet $\{1,B\}$. Im Gegensatz zu den Bandmaschinen mit beliebigen Hilfsalphabeten sind diese jedoch nummerierbar.

Zunächst sollte man sich nochmal ins Gedächtnis rufen, dass wir jede (Register-berechenbaren) Zahlenfunktion mittels Standardnummerierung in (Turing-berechenbare) Wortfunktionen und umgekehrt überführen können. Was hier am Ende passieren soll ist, dass wir von einer natürlichen Zahl über die Funktion $\nu_P$ zu einem Bandprogramm kommen. Von diesem ausgehend kommen wir mit $\nu_M$ auf eine normierte Bandmaschine (bzw. das Flussdiagramm aus diesem). Anschließend können wir diese mit $\xi$ in eine einstellige, berechenbare Funktion aus $P^{(1)}$ abbilden und haben zum Schluss über mehrere Wege also eine Nummerierung der einstelligen, berechenbaren Funktion $P^{(1)}$ erreicht. Aber mal langsam.

Die Nummerierung $\varphi$ besteht im Skript aus vier Komponenten:

• Ordnungsfunktion $a$ für das Alphabet $\Omega$, so dass wir mit $\nu_\Omega$ die Standardnummerierung aller Worte aus $\Omega$, d.h. von $\omega\in\Omega^{*}$ haben. Also nicht nur Programme, sondern auch Kauderwelsch wie z.B. $"1B(:"$.
• $\nu_P : \mathbb{N} \rightarrow BP$, z.B. $\nu_P(i)$ als die Nummerierung des Bandprogramms $i$. Es ist definiert durch:
• $\nu_P(i)=\begin{cases}\nu_\Omega(i)&\text{ wenn }\nu_\Omega(i)\in{BP}\\"(:B,,)"&\text {sonst}\end{cases}$
  Wir bekommen damit zur Nummer $i$ das zugehörige Bandprogramm wenn es tatsächlich ein Bandprogramm ist. Oder einfach nur eine Endlosschleife wenn die Nummer $i$ zu irgendwelchem Kauderwelsch gehört, denn mit $\nu_\Omega$ haben wir (siehe oben) alle Worte über $\Omega$, d.h. auch Unsinn, nummeriert.
• $\nu_M : \subseteq \Omega^* \rightarrow BM$, damit bekommen wir zum Wort $\omega$ aus $\Omega^{*}$ die zugehörige Bandmaschine $M$ (dazu gleich mehr)
• Funktion $\xi:BM \rightarrow P^{(1)}$ mit  $\xi(M) := \iota^{-1}{f{_M}}\iota$. $\xi(M)$ ist also die Funktion aus $P^{(1)}$, welche die Funktion der Bandmaschine $M$ berechnet.

Damit kann die Standardnummerierung $\varphi$ als eine Komposition zwischen $\xi\circ\nu_M\circ\nu_P$ definiert werden.

Das Problem ist nun, dass diese Standardnummerierung $\varphi$ nicht bijektiv ist, wie die Standardnummerierung $\nu_\Sigma$! Das liegt an der Surjektivität der verwendeten Funktionen, u.a. $\xi :BM \rightarrow P^{(1)}$. Denn zu einer Funktion aus $P^{(1)}$ kann es durchaus mehrere Bandmaschinen aus $BM$ geben, die die Funktion berechnen: wir fügen der Berechnungsroutine einfach ein paar sinnlose Schleifen hinzu und haben so eine neue Maschine, aber immer noch die alte, berechnete Funktion.

Jedoch ist sie trotzdem total, denn die Nummerierung aller Bandprogramme $\nu_P : \mathbb{N} \rightarrow BP$ ist ja total: wir erwischen durch die Definition von $\nu_P$ tatsächlich nur richtige Bandprogramme. Und zwar alle.

Und zu einem Bandprogramm bekommen wir die zugehörige Bandmaschine mit $\nu_M$. Der Definitionsberech der Funktion $\nu_M$ ist durch die Totalität von $\nu_P$ die komplette Menge $BP$.

Die Komposition aus $\nu_M(\nu_P)$ ist damit auch total. Und weil $\xi : BM\rightarrow{P^{(1)}}$ auch total ist (wir haben zu allen Funktionen aus $P^{(1)}$ min. eine Bandmaschine, die sie berechnet), ist die Komposition $\xi\circ\nu_M\circ\nu_P=\xi(\nu_M(\nu_P))$ ebenfalls total.

Um es etwas deutlicher zu machen, holen wir uns Beispiele und bauen auf diesen dann die Definition auf:

Zunächst haben wir ein Alphabet $\Omega$, welches unsere Zeichen

$\Omega:=(1\mid{B}\mid{(}\mid{)}\mid{,}\mid{:}\mid{R}\mid{L})$

beinhaltet. Achtung $\mid$ ist unser Trennzeichen, da das Komma zum Alphabet $\Omega$ gehört.

Aus diesen Zeichen kann ein Bandbefehl $BB$ unseres Programms bestehen, welches die Form

$(1^m:\beta,1^n)$ mit $\beta\in\{B,1,R,L\}$ oder

$(1^m:\beta,1^k,1^n)$ mit $\beta\in\{B,1\}$

hat. Das kennt Ihr alles schon von den Turingmaschinen. Der erste Befehl der Marke $1^m$ schreibt entweder ein $B$, eine $1$ auf das Band oder geht nach $L$inks oder $R$echts und springt anschließend in die Marke $1^n$.

Der zweite Befehl ist eine Verzweigung: in der Marke $1^m$ wird geprüft ob unter dem Lesekopf aktuell ein $B$ oder eine $1$ steht. Ist das der Fall, wird in die Marke $1^k$ verzweigt und ansonsten in die Marke $1^n$ gesprungen.

An den Beispiel weiter unten wird es gleich deutlicher.

Ein Bandbefehl aus der Menge $BB$ ist damit ein Wort über $\Omega$, d.h. $BB\subseteq\Omega^{*}$. Ein Bandprogramm aus der Menge $BP$ ist eine Folge von Bandbefehlen (es kann auch nur eines seit) und ist damit auch nur eine Kombination aus Worten über $\Omega$: $BP\subseteq\Omega^{*}$

Kommen wir nun zu unserer Funktion, die uns zu einem Bandprogramm aus $BP$ eine Bandmaschine aus $BM$ gibt, die die gleiche Funktion berechnet:

$\nu_M:BP\rightarrow BM$

Die Maschine $M\in{BM}$, die das Bandprogramm $\omega\in{BP}$, welches aus einer Folge von Bandbefehlen aus der Menge $BB$ besteht, berechnet, wird durch ein Flussdiagramm $F$ beschrieben. Damit gilt:

$M=\nu_M(\omega)\in{BM}$

D.h. mit der Funktion $\nu_M(\omega)$ bekommen wir zum Bandprogramm $\omega$ die passende Maschine $M$

Wir haben noch die Definition von $F$ im Kopf? Nein? Macht nichts: $F := \{Q,D_{\{1,B\}},\sigma, q_0\}$.

$Q$: ist die Menge unserer Marken, d.h. die Beschriftung der Befehle und Verzweigungen (Rechtecke und Rauten) im Flussdiagramm.

$D$: ist unser Arbeitsalphabet. Wir beschränken uns im Skript auf $\{1,B\}$, da sie die einzigen Zeichen sind, die wir benötigen (Satz über Hilfssymbole!)

$\sigma$: die auszuführenden Aktionen für die Marken. Ist z.B. $n$ eine Marke, so ist $\sigma(n)$ der auszuführende Befehl.

$q_0$: unsere Startmarke. Diese ist der Definition nach das erste Element aus $\omega$, d.h. der erste Befehl.

Wir überführen also die Folge von Bandbefehlen im Endeffekt einfach in ein Flussdiagramm. Das geschieht nachfolgendem Schema:

Für $(1^n:\beta,1^k)$ bekommen wir

und für $(1^n:\beta,1^m,1^k)$ gibt es ein

Was mich zunächst aus dem Konzept gebracht hat, sind Befehle und Übertragung dieser in ein Flussdiagramm in folgender Form: $(:1,1,1^2)$, doppelte Zuweisungen zu einer Marke und $HALT$-Befehle. Die folgenden Sätze liefern hierzu den Schlüssel (Harald aus der NG hat mich hier drauf gestoßen. Danke nochmal):

1. Falls es für eine Zahl/Marke $k$ mehrere Befehle gibt, so zählt nur der erste von links.

2. Kommt irgendwo eine Zahl/Marke $k$ vor und beginnt kein Befehl mit $1^k$, so ist es der HALT-Befehl.

Beispiel: aus dem Skript $\omega = (1^2:1,,1)(:1,1,1^2)(:B,,)$

Was müssen wir hier also zunächst tun? Wir schreiben uns alle Marken raus, die wir finden: 2 (aus $(1^2:...)$), 0 (aus $(:...)$) und 1 (aus $(...,1)$). Nun schauen wir uns die Definitionen unserer Marken 0,1 und 2 an.

• Marke 0: $(:1,1,1^2)$. Bedeutet: wenn $1$, gehe zu Marke $1$, ansonsten zu Marke $2$. $(:B,,)$ wird ignoriert, da doppelte Zuweisung.
• Marke 1: $HALT$. Es wird auf die Marke $1$ in Marke $0$ und $2$ verwiesen, aber es gibt keinen Befehl dafür. Also ist es unsere $HALT$-Marke.
• Marke 2: $(1^2:1,,1)$. Bedeutet: wenn $1$, gehe zu Marke $0$, ansonsten zu Marke $1$. Ist unsere erste Marke und daher auch unser Einstiegspunkt im Flussdiagramm.

Mit diesen Informationen könnt Ihr euch nun das dazugehörige Flussdiagramm eurer Maschine $M$ aufmalen (versucht es mal selbst und prüft eure Lösung mit dem Spoiler-Ausklapp-Text unten) und habt damit euer $\nu_M(\omega)$.

Lösung zeigen

Und nun tun wir das wozu wir hier sind: wir definieren wir die Standardnummerierung $\varphi$ dem Skript nach.

1. Ordnungsfunktion $a$, welche die Zeichen (siehe oben) unserer Programmiersprache nummeriert. $a_1 = 1$, $a_2 = B, ... a_8 = L$, usw. Mit $\nu_\Omega$ wird dann die Standardnummerierung von $\Omega^*$ bezeichnet, denn $\Omega^*$ beinhaltet (wir denken wieder an den Beitrag über die Standardnummerierung) ja alle Worte über diesem Alphabet.D.h. wir können diese Kombinationen aus diesen Zeichen durchnummerieren.
2. Mit $\nu_P : \mathbb{N} \rightarrow BP$ haben wir eine Funktion, die uns zu einer Zahl $i$ das zugehörige Bandprogramm aus $BP$ (bzw. eine Kombination aus den oben definierten Zeichen) zurückgibt: nämlich $\nu_\Omega (i)$ (aber nur wenn es ein echtes Bandprogramm ist, welche wiederum aus Bandbefehlen der Menge $BB$ besteht. Es könnte aber auch irgendwelches Kauderwelsch sein, was nicht ausführbar ist).
   Wenn es also Kauderwelsch ist, wird ein $((:B,,)$. zurückgegeben, d.h. eine Endlosschleife. Damit ist $\nu_P$ nur surjektiv, da man einige Nummern $i$ mit $\nu_P(i)$ durchaus mehrfach auf $((:B,,)$ abbildet wenn sie nicht Nummern von legitimen Bandprogrammen sind.
3. $\nu_M : \subseteq \Omega^* \rightarrow BM$, damit bekommen wir zum Wort $\omega$ aus $\Omega^{*}$ (von wem wir durch $\nu_P$ sicher wissen, dass es sich um ein Bandprogramm handelt), die zugehörige Bandmaschine $M$
4. Durch $\xi:BM\rightarrow P^{(1)}$ mit  $\xi(M):=\iota^{-1}{f{_M}}\iota$ haben wir die von der Bandmaschine $M$ berechnete Funktion aus $P^{(1)}$. Zudem: $\iota(i) = 1^i$. Bei den beispiel gleich wird es deutlicher.
5. Als letztes definieren wir $\varphi:\mathbb{N}\rightarrow P^{(1)}$ durch: $\varphi_i=\varphi(i)=\xi\nu_M\nu_P (i)$. Auch hier hilft zum besseren Verständnis das Ausklammern: $\varphi_i=\varphi(i) = \xi(\nu_M (\nu_P (i)))$.

Punkt 4 baut auf der ganzen Vorarbeit auf und standard-nummeriert uns schlussendlich unsere einstelligen, berechenbaren Funktionen aus $P^{(1)}$. Und nicht vergessen: die Standardnummerierung von $P^{(1)}$ ist surjektiv und total!

Ein Beispiel wäre hilfreich, oder? Ich nehme gleich das Beispiel aus dem Skript und rechne es Schritt für Schritt durch.

Beispiel: $\omega_1 = (: R,1)(1:B,11,)$

Die Nummer des Bandprogramms ist in der Aufgabenstellung $n_1$. Das ist relativ willkürlich gewählt uns ist uns auch ziemlich egal. Wir könnten durch die ordnungsfunktion $a$ auch eine echte Gödelnummer angeben, aber wozu? Spielt hier keine große Rolle.

Wir haken nun die komplette Definition der Standardnummerierung ab:

1. Als Ordnungsfunktion $a$ nutzen wir die Funktion aus der Definition und haben so auch unsere Nummerierung von allen Worten über dem Alphabet $\Omega$, nämlich $\nu_\Omega$.

2. Nun brauchen wir $\nu_P(n_1)$. Da unser Wort $\omega_1 = (: R,1)(1:B,11,)$ korrekt ist und aus $BP$ kommt, bekommen wir das zurück (siehe Definition):

$\nu_P(n_1)=\nu_\Omega(n_1)=\omega_1=(: R,1)(1:B,11,)$.

Wäre $(: R,1)(1:B,11,)$ nicht in $BP$, so hätten wir nur ein $(:B,,)$ bekommen. Daraus basteln wir uns nun ein wunderschönes Flussdiagramm. Auch hier: alleine versuchen, dann Lösung öffnen.

Lösung zeigen

Was macht das schöne Stück? Nehmen wir an wir geben in die Maschine $11$ und starten bei Marke $0$. Der Lesekopf ist anfangs ja auf dem letzten $B$ (Blank) vor dem Eingabewort. Wir gehen nun nach rechts (Marke $0$) auf die erste $1$ auf dem Band. Dann sind wir bei Marke $2$ und prüfen ob unter dem Lesekopf ein $B$ (Blank) steht. Tut er das, gehen wir zu Marke $2$ und halten. Befindet sich jedoch eine $1$ unter dem Lesekopf, gehen wir wieder zu Marke $0$ und tun das so lange bis wir auf ein Blank treffen und unser Eingabewort damit zu Ende ist.

Soweit so unspektakulär.

Die so berechnete Funktion $f$ unserer Maschine $M$ ist somit: $f_{M}(1^m) = 1^m$. Zur Auffrischung. Das $m$ ist einfach nur die Anzahl der Einsen. Wir geben also $m$ Einsen auf das Band und am Ende steht der Lesekopf auf Position $m+1$ und wir haben als Ausgabe links vom Lesekopf also $m$ Einsen auf dem Band. Sprechen wir von "normalen" Funktionen, die dezimal ($x$) und nicht unär ($1^{x}$) definiert sind, wäre das $f(x) = x$.

Nun brauchen wir noch unser $\varphi$ (ich erkläre die Berechnung weiter unten um die Übersichtlichkeit nicht zu killen):

$\begin{array}{lcl}\varphi_{n_1}(m)&=& \varphi(n_1)(m)& {*1} \\ {} &=& \xi(\nu_M(\nu_P(n_1)))(m) & {*2} \\ {} &=& \xi(\nu_M((: R,1)(1:B,11,)))(m) &\mbox{*3}\\{} &=& \xi(M)(m)&\mbox{*4}\\{}&=&\iota^{-1}(f_M(\iota(m)))&\mbox{*5}\\{}&=&\iota^{-1}(f_M(1^m))&\mbox{*6}\\{}&=&\iota^{-1}(1^m)&\mbox{*7}\\{}&=&m&\mbox{*8}\end{array}$

Fertig!

Wir haben es also geschafft mit $\varphi$ die Funktionen aus $P1 {(1)}$ zu nummerieren. Geben wir $\varphi$ also die dezimale Nummer der Maschine und einen dezimalen Parameter aus $\mathbb{N}$ mit, bekommen wir als Ausgabe auch einen dezimalen Ausgabewert zurück, obwohl die Maschine, die diesen Wert berechnet nur mit der unären Darstellung $1^m$ arbeitet. Wir verkürzen das in den Merksatz:

$\varphi(i)$ ist die von der $i-ten$ Bandmaschine berechnete Funktion aus $P^{(1)}$, der Menge der einstelligen partiell-rekursiven Funktionen.

Hier die Erklärung der Berechnung von oben (Danke an Carsten für den letzten Hinweis).

$*1$: nur schöner umgeschrieben, einfach der Definition nach

$*2$: der Definition nach ist $\varphi(i)=\xi\nu_M\nu_P(i)$. Ich habe hier nur ausgeklammert. Und da wir $\varphi(i)$ mit einem Parameter $m$ füttern, hängt er eben mit hinten dran.

$*3$: $n_1$ war ja die willkürliche Nummer unserer Maschine. $\nu_P(n_1)$ ist demnach unser Wort $\omega_1 = (: R,1)(1:B,11,)$ für die Maschine (siehe Definition von $\nu_P$).

$*4$: $\nu_M((: R,1)(1:B,11,))$ ist also unsere Maschine $M$ mit dem Flussdiagramm, welche unsere Funktion berechnet. Die von der Maschine $M$ berechnete Funktion nennen wir ja immer $f_M$.

$*5$: $\xi(M)$ ist unserer Definition nach ja eben $\iota^{-1}(f_M(\iota))$. Da wir ja immernoch den Parameter $m$ mitschleppen, hängt er weiterhin einfach nur mit.

$*6$: Jetzt wird es lustig. In der Definition steht, dass $\iota(m) = 1^m$ ist. D.h. einfach die Anzahl von Einsen. $\iota(4)$ wäre z.B. ${} = 1^4 = 1111$. Das dient uns als Eingabe für unsere Funktion $f_M$. Die Bandmaschinen werden ja mit der unären Darstellung von Dezimalzahlen gefüttert. Daher brauchen wir hierfür $\iota$ um eine Dezimalzahl in ihre unäre Darstellung umzuwandeln damit wir unsere Maschine damit bedienen können.

$*7$: Was macht unsere Funktion $f_M$ wenn man sie mit der Eingabe $1^m$ startet? Genau: sie gibt uns als Ausgabe auch wieder $1^m$ zurück.

$*8$: Und $\iota^{-1}$ ist die Inverse zu $\iota$ und macht genau das umgekehrte. Es bekommt als Parameter die unäre Darstellung $1^m$ der Zahl $m$ als Parameter und gibt uns die dezimale Darstellung $m$ zurück.

Damit haben wir auch die Standardnummerierung $\varphi$ der einstelligen, berechenbaren Funktionen $P^{(1)}$ abgehakt.

Ich gehe in diesem Abschnitt jetzt nicht strikt den Lernzielen, da zu dieser Aufgabe auch noch die Standardkomplexität $\Phi$ gehört. Im anderen Beitrag wäre sie nicht wirklich gut aufgehoben. Aus diesem Grund nehme ich das noch hier auf. Aber zunächst die Antwort zum Lernziel.

Antwort zum Lernziel: Die Standardnummerierung $\varphi$ der einstelligen, berechenbaren Funktionen $P^{(1)}$ besteht aus den Komponenten:

• Ordnungsfunktion $a$ mit $a:\{1,...,8\}\subseteq\Omega$ für die geordnete Nummerierung des Alphabets $\Omega$
• $\nu_\Omega$. Durch die Ordnungsfunktion induzierte Standardnummerierung von von $\Omega^{*}$.
• $\nu_P(i):\mathbb{N}\rightarrow BP$. Funktion um zu einer Nummer $i$ das zugehörige Bandprogramm zu bekommen wenn $\nu_\Omega(i)$ tatsächlich ein Bandprogramm ist
• $\nu_M(i):BP\rightarrow BM$. Funktion um zur einem Bandprogramm die zugehörige Bandmaschine zu bekommen.
• $\xi:BM\rightarrow P^{(1)}$. Funktion um zu einer Maschine die zugehörige Funktion zu erhalten.

Dadurch ist es möglich, ausgehend von einer Zahl $i\in\mathbb{N}$ eine Funktion aus $\varphi(i)\in{P^{(1)}}$ zu erhalten:

$\varphi: \mathbb{N}\rightarrow BP\rightarrow BM\rightarrow P^{(1)}$

Lernziel 2

Erläuterung des $\Phi$-Theorems

Wir starten zunächst mit der Definition der Standardkomplexität selbst:

$\Phi$ heißt Standardkomplexität zu $\varphi$ und ist definiert durch:

$\Phi(i)(x):=\Phi_i(x) := SZ_i(q_{0i}, (\varepsilon, B, 1^x))$

$q_{oi}$ ist die Anfangsmarke, $SZ_i$ die Schrittzahlfunktion der Bandmaschine $\nu_M(\nu_P(i))$.

Was haben wir hier?

Im Endeffekt bekommen wir mit $\Phi$ also einfach nur die Anzahl der Schritte, die die Maschine $\nu_M(\nu_P(i))$ braucht um für eine Eingabe $x$, ausgehend von Marke $q_{oi}$ und der Bandbelegung $(\varepsilon, B, 1^x)$ (unter dem Lesekopf steht das Blank $B$ vor der Eingabe, einer unären Darstellung von $x$) die Berechnung durchzuführen und schließlich auf $HALT$ stehen zu bleiben (oder eben nicht). Dafür brauchen wir die Schrittzahlfunktion $SZ$, die wir bereits kennen.

$\nu_M(\nu_P(i))$ schreckt euch doch nach dem Abschnitt zur Standardnummerierung $\varphi$ von $P^{(1)}$ doch auch nicht mehr, so dass ich es nicht an einem Beispiel auflösen muss, oder? Nein? Gut. Dann machen wir weiter.

Die Standardkomplexität $\Phi$ zu $\varphi$ hat zudem drei schöne Eigenschaften:

1. Die Funktion zur Standardkomplexität $\Phi$ einer Maschine $i$ gehört zu den einstelligen, berechenbaren Funktionen $P^{(1)}$.

Ist auch klar, denn es ist die Rechenzeitfunktion der $i$-ten Bandmaschine.

2. Der Definitionsbereich von $\Phi_i$ ist gleich dem Definitionsbereich von $\varphi_i$. Beide Funktionen verwenden den selben Parameter $x$ aus $\mathbb{N}$ für ihre Eingabe.

Während $\varphi_i(x)$ uns das Ergebnis $y$ aus seinem Bildbereich liefert, bekommen wir mit $\Phi_i(x)$ die zur Berechnung von $y$ notwendige Schrittanzahl $z$.

Dass $y \neq z$ sein kann (mit etwas Zufall ist die Anzahl der Schritte gleich dem Ergebnis, aber das ist dann auch nur Zufall), für das gleiche $x$, ist auch klar. Aber es bleibt das gleiche $x$, daher ist

$Def(\Phi_i) = Def(\varphi_i)$.

3. Die Menge $\{(i,x,t) \in \mathbb{N}^3\mid \Phi_i(x) \leq t\}$ ist rekursiv/entscheidbar.

Während Punkt Eins und Zwei wahrscheinlich klar sind, wiederholen wir für Punkt 3 noch einmal die Definition einer rekursiven/entscheidbaren Menge aus einem alten Beitrag. Wann ist eine Menge also rekursiv/entscheidbar? Genau dann wenn die charakteristische Funktion berechenbar ist. Die charakteristische Funktion für $\Phi$ ist:

$g_\Phi(i,x,t)=\begin{cases} 1, & \mbox{ falls } \Phi_i(x) \leq t \\ 0, & \mbox{ sonst}\end{cases}$

Was bedeutet das?

Ganz einfach: wir bekommen mit der Funktion $g_\Phi(i,x,t)$ eine $1$ zurück wenn die Maschine $\nu_M(\nu_P(i))$ bei der Eingabe von $x$ nicht mehr als $t$ Rechenschritte bis zur $HALT$-Marke braucht. Braucht sie mehr, so bekommen wir eine $0$ zurück.

Als Beweis benutzen wir wieder eine Funktion, die unserem $h(i,n,t)$ (Erläuterung von $h$ ist im nächsten Lernziel) sehr ähnlich ist.

$h(i,n,t) = \begin{cases} 1+\varphi_i(n), & \mbox{ falls } \Phi_i(n) \mbox{ existiert und } \Phi_i(n) \leq t\\ 0, & \mbox{ sonst }\end{cases}$

Der Beweis, dass diese Funktion berechenbar ist, gehört auch zu den Lernzielen. Wir schieben die Funktion dennoch hier dazwischen und holen den Beweis gleich nach.

Was passiert also bei $g_\Phi(i,x,t)$?

1. $\Phi_i(x)$ ist ja die kleinste Zahl $t$, bei der $h(i,n,t) \neq 0$ gilt, da $\Phi_i(x)$ uns ja die Anzahl der Schritte liefert, die die Maschine $\nu_M(\nu_P(i))$ braucht um bei der Eingabe  $x$ zum Ende der Berechnung zu kommen.

2. $\Phi_i(x)$ gibt es nur wenn es die Schrittzahlfunktion $SZ(q_{oi},(\varepsilon,B,1^xB))$ und auch die Ausgabe $\varphi_i(x)$ gibt. Ansonsten wäre sie nicht vorhanden: keine Ausgabe, keine Schritte, keine Standardkomplexität $\Phi$.

3. Da $h$ berechenbar ist (weisen wir gleich nach), auch Kompositionen aus den Funktionen berechenbar sind, so ist auch unsere charakteristische Funktion $g_\Phi(i,x,t) = min(1,h(i,x,t))$ berechenbar.

Was $min(1,h(i,x,t))$ sollte klar sein, ich schreibe es trotzdem mal auf:

Wir bekommen mit der Funktion $min$ den kleinsten Wert aus der Auswahl von zwei Werten. Und wir haben die Auswahl zwischen $1$ und dem Funktionswert von $h(i,x,t)$.

Unser $h$ gibt aber nur den Funktionswert zurück wenn die Maschine die Berechnung mit maximal $t$ Rechenschritten abschließt, denn $t$ ist die Anzahl der Schritte, die wir maximal rechnen dürfen. Ansonsten gibt es nur den Zonk, ähm, ich meine die $0$. In diesem Fall hat die Maschine bereits $t$ Schritte gerechnet und ist noch nicht bei der $HALT$-Marke angekommen, d.h. die Berechnung ist nach $t$ Schritten noch nicht zu Ende.

Wir haben daher immer $min(1,0) = 0$ wenn $\Phi_i(x) > t$ oder $min(1,Funktionwert)=1$ wenn $\Phi_i(x)\leq t$. Passt.

Damit ist gewiesen, dass die Menge $\{(i,x,t) \in \mathbb{N}^3\mid \Phi_i(x) \leq t\}$ tatsächlich rekursiv/entscheidbar ist, denn wir können entscheiden ob Maschine $i$ bei der Eingabe von $x$ nach $t$ Schritten hält oder nicht.

Naja, streng genommen müssen wir dazu noch $h$ als berechenbar nachweisen, aber das tun wir ja gleich im 3. Lernziel.

Und was ist mit der

Beispielaufgabe zu $\omega_1 = (: R,1)(1:B,11,)$ von Oben?

Die holen wir mit dem Wissen, das wir haben nun nach. Hier noch einmal das Flussdiagramm damit Ihr nicht scrollen müsst:

Wie viele Schritte braucht unser Flussdiagramm denn bei der Eingabe von z.B. $1^3$, d.h. drei Einsen um bis zur $HALT$-Marke zu gelangen und wie sieht die Ausgabe dann aus? Spielt das Flussdiagramm einfach mal damit durch und Ihr werden feststellen, dass Ihr genau $8$ Schritte braucht.

Bei der Eingabekonfiguration von $(0,(\varepsilon,B,1^3))$ kommen wir nach $8$ Schritten dann bei der Endkonfiguration $(2,(1^3,B,\varepsilon))$ an. Wenn man das Flussdiagramm nun genauer betrachtet kommt man drauf, dass man bis zur Endkonfiguration genau $2*3+2$ Schritte passiert hat. Bei der Eingabe von $m$ Einsen muss man die Schleife $m$ Mal passieren und führt so am Ende $2m+2$ Schritte durch, was uns zu unserer Übergangsrelation führt:

$(0,(\varepsilon,B,1^m) \vdash^{2m+2} (2,(1^m,B,\varepsilon))$

Und da $\Phi_{n_1}(m)$ nun genau die Anzahl der Schritte ist bis die Maschine bei der Eingabe von $m$ $HALT$ erreicht, ist

$\Phi_{n_1}(m) = 2m+2$

Damit ist die Standardkomplexität $\Phi_{n_1}$ zu $\varphi(n_1)$ bei der Eingabe von $m$ genau $2m+2$. Würde die Maschine nicht halten, so wäre $\Phi_{n_1} = div$.

Hiermit ist die Standardnummerierung für $P^{(1)}$ abgehakt und wir kümmern uns jetzt um den Beweis von $h$.

Antwort zum Lernziel: das $\Phi$-Theorem besagt drei Dinge:

• dass die Schrittzahlfunktion $\Phi_i=SZ_i$ der Maschine $i$ zu den einstelligen, berechenbaren Funktionen $P^{(1)}$ gehört
• der Definitionsbereich von $\Phi_i$ ist gleich dem Definitionsbereich von $\varphi_i$, da beide Funktionen den selben Eingabeparameter $x$ benötigen
• und die Menge $\{(i,x,t)\in\mathbb{N}^3\mid \Phi_i(x) \leq t\}$ rekursiv/entscheidbar ist, da die charakteristische Funktion berechenbar ist.

Mit dieser Standardkomplexität können wir bestimmen wie viele Berechnungsschritte die Maschine $i$ bei der Eingabe von $x$ benötigt ($\Phi_i(x)$) oder feststellen ob die Maschine $i$ bei der Eingabe von $x$ nach $t$ Berechnungsschritten hält oder nicht ($g_\Phi(i,x,t)$) um die Menge $(i,x,t)\in\mathbb{N}^3$ zu entscheiden.

Lernziel 3

Beweis der Berechenbarkeit von $h:\mathbb{N}^3\rightarrow\mathbb{N}$

Für die Formalisierung des utm-Theorems brauchen wir diese hilfreiche Funktion auch, also aufpassen! Definieren wir $h$ zunäüchst:

$h:\mathbb{N}^3 \rightarrow \mathbb{N}$  mit

$h(i,n,t) = \begin{cases} 1+\varphi_i(n), & \mbox{ falls } \Phi_i(n) \mbox{ existiert und } \Phi_i(n) \leq t\\ 0, & \mbox{ sonst }\end{cases}$

Okay, dreistellige Funktion auf den natürlichen Zahlen, die ein einstelliges Ergebnis ausgibt. Wir bekommen eine $1$ und das Ergebnis der Maschine $\nu_M(\nu_P(i))$ bei der Eingabe von $n$ wenn die Standardkomplexität $\Phi_i$ existiert und kleiner/gleich $t$ ist, d.h. wir kommen zum Ergebnis ($HALT$-Marke noch bevor wir $t$ Rechenschritte absolviert haben). Ansonsten gibt es nur eine Null zurück. Fair.

Um zu beweisen, dass die Funktion $h$ berechenbar ist wird wie folgt vorgegangen:

Wir zeigen, dass die Wortfunktion zu $h$ berechenbar ist. Anhand der Standardnummerierung können wir ja Worte in Zahlen und Zahlen in Worte codieren. Unsere Wortfunktion wäre damit: $\nu_\Sigma h\bar{\nu_\Sigma}^-1$.

Schaut euch die Standardnummerierung noch einmal an, falls euch das nicht mehr viel sagt. Anschließend basteln wir uns eine Turing-Maschine mit $f_M=\nu_\Sigma h\bar{\nu_\Sigma}^-1$. Diese Funktion sieht dann so aus:

$f_M(1^i,1^n,1^t) = 1^{h(i,n,t)}$

$1^{h(i,n,t)}=\begin{cases} 1^{1+\varphi_i(n)}, & \mbox{ falls } \Phi_i(n) \mbox{ existiert und } \Phi_i(n) \leq t\\ \varepsilon, & \mbox{ sonst }\end{cases}$

Führen wir uns einfach mal vor Augen, dass die Turing-Maschine nur Eingaben in Form von $1^x$, also $x$ Mal die $1$ entgegen nimmt und auch wieder ausgibt. Für die Funktion $h$ wandeln wir unsere $i, n$ und $t$ daher einfach in die entsprechende Anzahl ein Einsen um (unäre Darstellung einer Dezimalzahl).

Während wir bei der Funktion $h$ als Ergebnis dann $1+$ den dezimalen Ausgabewert, also $\varphi_i(n)$ bekommen hätten, bekommen wir hier einfach die dazu entsprechende Anzahl von Einsen ($1^{1+\varphi_i(n)}$); die unäre Darstellung des Ergebnisses. Das der Ausgabewert $0$ jedoch nicht in unserem vorher definierten Alphabet für die Maschine ist, nutzen wir das leere Wort $\varepsilon$ zur Codierung von $0$.

Bevor ich hier den Beweis praktisch abschreibe, wäre es wahrscheinlich sinnig ihn direkt anhand eines Beispiels durchzuspielen. Wir nehmen wieder die Aufgabe aus dem ersten Teil:

Beispiel:  $(1^2:1,,1)(:1,1,1^2)(:B,,)$

mit der zugehörigen Nummer $n_1$, der willkürlichen Eingabe $n=3$ und den maximal durchzuführenden Rechenschritten $t=9$.

Ein Ergebnis sollten wir auch herausbekommen, da wir aus dem letzten Beitrag ja wissen, dass die Standardkomplexität $\Phi_{n_1}(3)$ der Funktion ja $8$ und bekanntlich ist $8<9$ ist. Unser $f_M$ sieht mit der willkürlichen Wahl der Eingangsparameter nun so aus:

$f_M(1^{n_1},1^3,1^9) = 1^{h(n_1,3,9)}$

$1^{h(n_1,3,9)}=\begin{cases} 1^{1+\varphi_{n_1}(3)}, & \mbox{ falls } \Phi_{n_1}(3) \mbox{ existiert und } \Phi_{n_1}(3) \leq 9\\ \varepsilon, & \mbox{ sonst }\end{cases}$

Wir haben folgende Teil-Flussdiagramme mit den entsprechenden Aufgaben:

• $F_1$: Transformiert die Eingabe auf die einzelnen Bänder (siehe unten).
• $F_2$: Kopiert die Anfangsmarke auf Band $4$.
• $F_3$: Sucht auf Band $1$ nach dem Befehl mit der Marke von Band $4$. Wird keine passende Marke auf Band $1$ gefunden, so muss es eine $HALT$-Marke sein.
• $F_4$: Simuliert den gefundenen Befehl von Band $1$ auf dem Band $2$, wo unser Eingabewort steht.
• $F_5$: Testet ob weitergerechnet werden darf, d.h. ob noch Einsen auf Band $3$ stehen.
• $F_6$: Subtrahiert eine Eins von Band $3$ bei jedem simulierten Rechenschritt von $F_4$.
• $F_7$: Kopiert vom Arbeits- und Eingabeband $2$ am Ende alle Einsen auf Band $0$ und erzeugt uns so auf dem gewünschten Band $0$ eine Ausgabe.

Wir transformieren die Eingabecodierung $EC(1^{n_1},1^3,1^9 )$ und setzen jeden der drei Parameter als ein Eingabewort aus Einsen auf ein eigenes Band. Was jedoch mit $1^{n_1}$ gemacht wird, ist etwas spannender: Aus $1^{n_1}$ wird $\nu_P(n_1)$, unser Bandprogramm aus $BP$ (zur Auffrischung: siehe Lernziel 1), welches nun auf Band $1$ unserer Maschine steht.

Auf Band $2$ (Eingabeband) steht die Eingabe $1^{3}$ ($n=3$). Auf diesem Band werden die einzelnen Berechnungsschritte von Band $1$ (dem Programmband) simuliert. Band $3$ (Schrittzahlband) ist der Schrittzähler mit $1^9$, wo bei jedem Schritt von $\nu_P(n_1)$ eine $1$ gelöscht wird. Auf Band $4$ (Markenband) wird die aktuelle Marke gespeichert. Unsere Bänder sehen nun so aus:

Das hat unser Teil-Flussdiagramm $F_1$ gemacht. Nun kommt $F_2$ und kopiert die Anfangsmarke nach Band 4:

Nun sucht Teil-Flussdiagramm $F_3$ auf Band $1$, wo unser Programm gespeichert ist das erste Teilwort, wo die gespeicherte Marke von Band $4$ vorkommt. Wenn es einen passenden Befehl findet, führt Teil-Flussdiagramm $F_4$ den Befehl auf Band $2$ aus. Wenn nicht, so ist es eine Endmarke (wir erinnern uns an den ersten Abschnitt: wenn im Programm auf eine Marke referenziert wird, es jedoch keine Beschreibung für diese gibt, so ist es eine $HALT$-Marke).

Da die Marke $1^2$ von $F_3$ gefunden wird, wird der Befehl auf Band $2$ von Teil-Flussdiagramm $F_4$ ausgeführt. Wenn er die Form $(1^k:\beta,1^n)$ hat, wird die Bandoperation $\beta$ auf Band $2$ ausgeführt und die gespeicherte Marke auf Band $4$ mit der Folgemarke $1^n$ ersetzt. Hat der Befehl die Form $(1^k:\beta,1^j,1^m)$, so testet $F_4$ ob unter dem Kopf $\beta$ steht und ersetzt die Marke auf Band $4$ entsprechend dem Ergebnis durch $1^j$ (nein, $\beta$ steht nicht unter dem Lesekopf) oder $1^m$ (ja, $\beta$ steht unter dem Lesekopf). Das Teil-Flussdiagramm $F_5$ prüft ob auf dem Zählerband $3$ noch Einsen stehen, d.h. ob weitergerechnet werden kann.

In unserem Fall sehen unsere Bänder anschließend so aus, da der Befehl $(1^2:1,,1)$ auf Band $1$ gefunden und ausgeführt wurde. Auch ist eine $1$ auf Band $2$ unter dem Lesekopf, so dass wir nicht in die Marke $1$, sondern in die "leere" Folgemarke springen werden und diese Folgemarke auf unser Folgemarkenband $3$ schreiben. Auch haben wir eine $1$ von unserem Zählerband, Band $4$ mit dem Teil-Flussdiagramm $F_6$ gelöscht.

Da noch Einsen auf dem Zählerband stehen ($F_5$ hat das geprüft), dürfen wir weiterrechnen. Nun wird nach der "leeren" Marke auf Band $1$ gesucht, diese auf Band $2$ durch $F_4$ ausgeführt, wieder eine $1$ vom Zählerband $3$ durch $F_6$ gelöscht, die Folgemarke auf Band $4$ durch $F_4$ geschrieben, diese wieder auf Band $1$ durch $F_3$ gesucht, usw.

Wir wiederholen den Spaß nun die ganze Zeit bis die Maschine letztendlich alle ihre Befehle abgearbeitet (es in einem befehl auf eine Marke referenziert, diese auf das Folgemarkenband geschrieben und gesucht. Sie steht aber nicht auf Band $1$ - es ist also eine Endmarke) hat. Dann geht es von $F_3$ zu $F_7$, welches die Ausgabe von Band $2$ auf Band $0$ kopiert. Wäre es keine Endmarke, würde von $F_5$ noch einmal geprüft werden ob noch Einsen auf dem Zählerband stehen. Wenn das nicht der Fall wäre, so würde die Maschine halten. In unserem Fall sind noch Einsen auf Zählerband, eine Endmarke ist aber erreicht worden, alles ist gut.

Um noch wie gewünscht die $1$ zur Ausgabe $1^{\varphi_{n_1}(1^3)}$ zu addieren und den Lesekopf rechts von der Ausgabe zu positionieren werden am Ende noch die Befehle $0:1$ und $0:R$ ausgeführt.  Am Ende sehen unsere Bänder wie folgt aus:

Die gesuchte Ausgabe steht auf dem Ausgabeband $0$.

Damit haben wir die Berechenbarkeit der Funktion $h$ bewiesen. Und damit wir die ganze Arbeit nicht umsonst gemacht haben, nutzen wir $h$ gleich für das smn- un das utm-Theorem.

Antwort zum Lernziel: Um die charakteristische Funktion $g_\Phi$ für das $\Phi$-Theorem zu berechnen, ist es notwendig die Maschine mit der Nummer $i$ auf einer (sog. universellen) Turingmaschine zu simulieren.

Dazu wird das zu simulierende Bandprogramm $\nu_P(i)$, die Eingabe $x$, die maximale Anzahl der Schritte $t$ auf jeweils ein Band der neuen Maschine geschrieben und die einzelnen Befehle des Bandprogramms $\nu_P(i)$ auf dem Eingabeband, wo $x$ steht simuliert. Bei jedem Berechnungsschritt wird $t$ auf dem Schrittzahlband um Eins dekrementiert, während auf dem Markenband sich die Marke des aktuell zu simulierenden Befehls befindet damit die simulierende Maschine immer weiß, wo sie gerade ist.

Endet die Berechnung noch bevor $t$ auf dem Schrittzahlband zu $0$ geworden ist, war die Berechnung erfolgreich und es ist $h\neq 0$. Ist auf dem Schrittzahlband jedoch bereits $t=0$, so wird die Berechnung abgebrochen und es gilt $h=0$. Damit braucht die Maschine $i$ bei der Eingabe von $x$ mehr Berechnungsschritte als $t$ um zur Endmarke $HALT$ zu gelangen.

Diese Funktion ist nicht nur für das $\Phi$-Theorem wichtig, sondern bildet auch die Basis einer universellen Turingmaschine.

Weil der Beitrag zu den letzten drei Lernzielen so lang geworden ist, geht der Rest im nächsten Beitrag weiter.

Update: ich modelliere auch diesen Beitrag auf die Lernziele um. Evtl. kann es sein, dass der Beitrag nicht ganz fertig wird, so dass ein paar Antworten (noch) leer sind. Da ich ihn aber nicht speichern kann ohne ihn zu aktualisieren oder ihn offline nehmen müsste, habe ich keine andere Wahl als das zunächst so zu handhaben.

Update 6: Nachdem ich nun schon zwei Mails zum Thema $\mu$-Rekursion bekommen habe, möchte ich das hier noch einmal ausführen. Für die Details zum Thema Nullstellen möchte ich mich hier auch bei Oliver bedanken. Lernziel 5 also.

Update 5: mir ist was zur Standardnummerierung von $\Sigma^{*}$ und $P^{(1)}$ aufgefallen, dass ich hier passend unbedingt noch erwähnen musste.

Riesen Update: alle Lernziele habe ich nun überarbeitet und einige Ungenauigkeiten korrigiert. Der Beweis der nicht-berechenbaren Funktionen ist wohl auf das 10-fache des ursprünglichen Texts angewachsen. Irgendwie konnte ich mich mit dem alten Verweis auf das Diagonalrgument von Cantor für die Überabzählbarkeit der reellen Zahlen nicht anfreunden (beim ersten Erstellen hielt ich das noch für ausreichend) und habe den Skriptbeweis nun komplett auseinander genommen. Hoffentlich hilft es euch.

Kurseinheit 4 ist wieder ein Rundumschlag. Einige Dinge, die hier drin sind, hätten sich auch in Kurseinheit 2 wiederfinden müssen (LOOP, WHILE, Churchsche These und Zusammenhang zu $\mu$-rekursiven Funktionen. Taten sie aber nicht. Wäre wahrscheinlich einfach zu einfach gewesen. Ich würde daher vorschlagen, dass wir uns ausnahmsweise nicht thematisch, sondern anhand der Lernziele entlang hangeln.

Rekapitulation: Zahlen, Wörter

Nochmal als Wiederholung bevor wir loslegen.

Zahlenfunktionen: $f:\subseteq \mathbb{N}^k \rightarrow \mathbb{N}$. D.h. Abbildung von ggf. mehrstelligen (unser $k$) Eingabewerten von natürlichen Zahlen auf einen einzigen Ausgabewert, eine einzige natürliche Zahl. Berechenbar mit Registermaschinen, nicht mit Turingmaschinen.

Konkretes Beispiel: $f\subseteq\mathbb{N}^3\rightarrow\mathbb{N}$ mit $f(x,y,z)=x+y-z$,

z.B. $f(431,469,899)=1$

Wortfunktionen: $g:\subseteq \Sigma^{*k} \rightarrow \Sigma^{*}$. D.h. Abbildung von ggf. mehreren (wieder unser $k$) Eingabewerten von beliebig langen (unser $*$) Worten über einem Alphabet (unser $\Sigma$) auf einen einzigen Ausgabewert: ein einziges, beliebig langes Wort. $\Sigma^{*}$ ist hier die Wortmenge über dem Alphabet $\Sigma$. Berechenbar mit Turingmaschinen, nicht mit Registermaschinen.

Konkretes Beispiel: $g:\subseteq \Sigma^{*2}\rightarrow \Sigma^{*}$ mit $g(x,y)=xy$,

z.B. $g(abbb,aaaa)=abbbaaaa$

Wir können Zahlenfunktionen nicht auf Turingmaschinen und Wortfunktionen nicht auf Registermaschinen berechnen. Es gibt jedoch einen Weg: Erst wenn man Wörter in Zahlen codiert und Zahlen in Wörter (bijektive Abbildung zwischen zwei Mengen: Wörtern und Zahlen) kann man diese mit den entsprechend anderen Maschinen berechnen.

Ausgenutzt wird dabei, dass Registermaschinen und Turingmaschinen über Flussdiagramme definiert sind. Aber kümmern wir uns zunächst um die Standardnummerierung selbst.

Das ist die sogenannte Standardnummerierung (bijektive Abbildung zwischen den natürlichen Zahlen und einer Mengen). Definition kommt gleich. Es gibt jedoch einen wesentlichen Unterschied zu einer Nummerierung, der nicht verschwiegen werden darf.

Eine Nummerierung ist nicht bijektiv; Surjektivität reicht. Wir können in der Nummerierung dann jedem Wort mindestens eine Zahl zuordnen, aber wir haben keine eindeutige Umkehrabbildung, d.h. wenn wir dann zu einem Wort die zugehörige Zahl suchen, könnten wir diese mit etwas Pech auf mehrere Zahlen abbilden.

Achtung: während die Standardnummerierung von $\Sigma^{*}$ durch $\nu_\Sigma$ bijektiv ist, ist die Standardnummerierung der berechenbaren, einstelligen Funktionen $P^{(1)}$ aus dem nächsten Beitrag das nicht! Warum, sage ich dann dort. Bitte behaltet das unbedingt im Hinterkopf.

Formal definiert ist eine Nummerierung also:

$\nu:\subseteq\mathbb{N}\rightarrow{M}$

Sie kann partiell sein und ist - wie gesagt - surjektiv. Damit hat zwar jedes Element aus der nummerierten Menge $M$ eine Zahl aus $\mathbb{N}$, aber nicht zu jeder Zahl aus $\mathbb{N}$ gibt ein Element aus der Menge $M$.

Und weil Marco mich in den Kommentaren zu KE5 auf die Idee gebracht hat, noch eine kleine Nebeninfo: Haben wir eine bijektive Abbildung zwischen zwei Mengen, gelten diese als gleichmächtig und die Eigenschaften der einen, gelten auch für die andere Menge. Bilden wir also die natürlichen Zahlen mittels einer bijektiven Funktion auf eine andere Menge ab, wie wir das mit der Standardnummerierung tun, so übernimmt diese Menge eine wunderbare Eigenschaft der natürlichen Zahlen $\mathbb{N}$: sie ist dann ebenfalls abzählbar unendlich.

Lernziel 1

Angabe und Erläuterung der Definition einer Standardnummerierung von $\Sigma^{*}$

Nehmen wir als Beispiel ein Alphabet $\Sigma$  mit $n$ Symbolen, welches eine totale Ordnung hat (d.h. die $n$ Symbole innerhalb des Alphabets sind - wie auch immer - eindeutig sortiert), so beinhaltet $\Sigma^*$ alle Worte über dem Alphabet $\Sigma$.

$\nu_\Sigma(i)$ ist das $i$-te Wort aus dieser sortierten Liste. Die Sortierung nennt man Ordnungsfunktion. Das spannende an dieser Nummerierung ist, dass sie bijektiv ist. Wir haben also eine eindeutige Abbildung von einem Wort in eine Zahl und eine Inverse, die uns zu einer Zahl ein eindeutiges Wort liefert. Lasst uns die Definition mal formalisieren:

$\Sigma$ ist ein Alphabet mit $card(\Sigma) >= 1$.
$a: \{1,...,n\} \rightarrow \Sigma$ die Ordnungsfunktion $a$ mit $a_i := a(i)$ und $\Sigma = \{a_1, ..., a_n\}$.

$\sigma:\Sigma^* \rightarrow \mathbb{N}$ mit $\sigma(\varepsilon):=0$ sowie

$\sigma ({a_{i}}_{k} {a_{i}}_{k-1} ... {a_{i}}_{1} {a_{i}}_{0}) := i_k n^k + i_{k-1} n^{k-1} + ... i_1 n+i_0$ für alle $k \in \mathbb{N}, i_0,...,i_k \in \{1,...,n\}$.

$\nu_\Sigma : \mathbb{N} \rightarrow \Sigma^*$ ist unsere Inverse der Funktion $\sigma$ und damit $\nu_\Sigma := \sigma^{-1}$. Sie gibt uns zu einer gegebenen Zahl das entsprechende, eindeutige Wort zurück und wird Standardnummerierung von $\Sigma^{*}$ genannt.

Keine Sorge, wir gehen das direkt an einem Beispiel durch.

Beispiel:

$\Sigma = \{a,b\}$ mit $card(\Sigma) = 2$ (Kardinalität, Mächtigkeit einer Menge). Ein Alphabet mit den Buchstaben $a$ und $b$, d.h. nur $2$ Elementen und damit der Kardinalität $2$.

Wir haben zwei Elemente $a$ und $b$ im Alphabet, also ist $n = 2$ und wir haben $a_1 = a(1) = a$ und $a_2 = a(2) = b$: innerhalb der Wortmenge werden die Elemente wie im Skript nach Länge und dann lexikographisch geordnet. Die Menge $\Sigma^*$ wäre dann

$\Sigma^*=\{a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,...\}$.

Wir haben nun jedem unserer zwei Elemente eine Ordnungszahl zugewiesen. Das ist unsere Ordnungsfunktion $a$.

Der letzte Teil ist jetzt etwas ekelig, aber halb so wild. Erinnert mich irgendwie an SIMPLEX. Die Funktion $\sigma$ macht nichts anderes, als zu einem bestimmten Wort die eindeutige Zahl anhand der definierten Ordnung zu bestimmen. Wir suchen z.B. die zugewiesene Zahl zu $abb$. $abb$ steht an 10. Stelle in der Reihenfolge und wir erwarten die $10$ auch als Ergebnis.

$n = 2$ (ist klar, die Kardinalität von $\Sigma$, d.h. Anzahl der Elemente)

$k = 2$ (das Wort $abb$ besteht aus drei Elementen, wir zählen von $0$ und haben damit $k=2$)

$i$ ist unsere Ordnungszahl. Da $a$ zuerst kommt, ist $a=1$ und da $b$ an zweiter Stelle in unserer Ordnung kommt, ist $b=2$. Hätten wir noch $c$, so wäre $c=3$ unserer festgelegten Ordnung nach.

$\begin{array} {lcl}\sigma(abb)&=&1\cdot2^2 + 2\cdot2 + 2\\{}&=&4+4+2\\{}&=&10\end{array}$

Und ja, $abb$ steht an 10. Stelle in unserer Ordnung.

Man mache sich einfach klar, dass ein beliebiges Alphabet $\Sigma$ definieren können, solange wir nur eine numerische Ordnung auf den Elementen des Alphabets definieren. Da wir aus den Elementen des Alphabets Worte bauen können, können wir auch aus den Ordnungszahlen, die den Elementen zugeordnet sind Kombinationen herstellen.

Die Ordnung ist ja nichts weiter als die Festlegung der Reihenfolge der verwendeten Elemente in unserem Alphabet. Damit rechnen wir statt mit den Buchstaben, nun mit ihren "Ordnungszahlen". Und da auf den verwendeten, natürlichen Zahlen für unsere Reihenfolge auch eine natürliche Ordnung herrscht ($1<2<3<4<...$), können wir damit wunderbar rechnen.

Unser $a$ im Alphabet repräsentiert unsere "Ordnungszahl" $1$ und $b$ unsere "Ordnungszahl" $2$, welche wir dann oben in der Gleichung für $\sigma(abb)$ verwendet haben und damit auf den Rechenweg $1$ $\cdot2^2 +$ $2$ $\cdot2^1 +$ $2$ $\cdot2^0$ kommen. Die grüne 1 ist daher die Ordnungszahl unseres $a$ und die rote 2 die unseres $b$.

Die Inverse zu $\sigma(a)$ ($a$ ist ein Wort) ist $\sigma^{-1}=\nu_\Sigma(i)$ und gibt uns für eine Zahl $i$ das dazugehörige Wort. Das 10. Wort wäre also $\nu_\Sigma(10) = abb$.

Damit ist $\nu_{\Sigma}$ eine Standardnummerierung von $\Sigma^{*}$, also aller Worte über dem Alphabet $\Sigma$.

Antwort zum Lernziel: die Standardnummerierung $\nu_{\Sigma}$ der Worte über einem Alphabet $\Sigma$ ist eine bijektive Abbildung zwischen den natürlichen Zahlen $\mathbb{N}$ und den Worten aus $\Sigma^{*}$. Die Bijektivität ist wichtig damit wir einer Zahl eindeutig ein Wort und einem Wort eindeutig eine Zahl zuweisen können.

Diese Zuweisung funktioniert aufgrund einer sog. Ordnungsfunktion $a$ auf dem Alphabet $\Sigma$, welches jedem Zeichen aus den Alphabet eine eindeutige Nummer (Ordnungszahl) aus den natürlichen Zahlen zuordnet. Durch die natürliche Ordnung auf den natürlichen Zahlen $\mathbb{N}$ haben wir auch eine natürliche Ordnung auf den Elementen aus unserem Alphabet $\Sigma$, die wir vorher nicht hatten.

Mit $\sigma(a)$ bekommen wir somit zu einem Wort $a$ die zugehörige Ordnungszahl $i$ und mit $\nu_{\Sigma}(i)$ zu einer Zahl $i$ das zugehörige Wort aus den Worten über dem Alphabet $\Sigma$: $\Sigma^{*}$.

Lernziel 2

Formulierung und Erläuterung der Beziehung zwischen Zahlen- und Wortfunktionen

Zunächst noch einmal die Definition wann Wortfunktionen berechenbar sind:

Eine (ggf. partielle) Wortfunktion $g : \subseteq (\Sigma^*)^k \rightarrow \Sigma^*$ ist genau dann berechenbar, wenn es eine Turing-Maschine $T$ gibt, die die Funktion berechnet. Wenn also $g =g_T$ gilt.

Das gleiche Spiel für Zahlenfunktionen.

Eine (ggf. partielle) Zahlenfunktion $f : \subseteq \mathbb{N}^k \rightarrow \mathbb{N}$ ist genau dann berechenbar, wenn es eine Registermaschine $M$ gibt, die die Funktion berechnet. Wenn also $f = f_M$ gilt.

Kennen wir schon aus den alten Beiträgen. Registermaschinen für Zahlen- und Turingmaschinen für Wortfunktionen. Langweilig. But wait, there's more! Im Zusammenhang mit der Standardnummerierung hatten wir das noch nicht. Denn wir können Wortfunktionen durchaus mit Registermaschinen und Zahlenfunktionen mit Turingmaschinen berechnen.

Man macht sich zunächst noch einmal folgenden Zusammenhang klar: Unsere ($k$-steligen) Wortfunktionen, welche die Turingmaschinen (Mehrbandmaschinen mit $k$ Bändern) berechnen können, können auch auf Einbandmaschinen berechnet werden (Ihr erinnert euch: Spuren, Hilfssymbole, etc.?). Wir können uns also auf die Betrachtung der Einbandmaschinen für die Berechnung der Wortfunktionen beschränken.

Und hier kommt die Standardnummerierung ins Spiel: wollen wir eine Wortfunktion auf einer Registermaschine berechnen, geht das zunächst nicht. Die Registermaschine rechnet ja mit Zahlen und nicht mit Worten. Und auch als Ausgabe bekommen wir eine Zahl und kein Wort. Aber hey! Wir können die Worte ja mit unserer Standardnummerierung eindeutig auf Zahlen und Zahlen eindeutig auf Worte abbilden. Damit gelingt es uns die Eingabeworte für unsere Turingmaschine in eine Zahl zu verwandeln, damit die Registermaschine zu füttern und die Ausgabe dieser (die ja auch eine Zahl ist) wieder in ein Wort zu verwandeln. 

Die Standardnummerierung erledigt das. Was uns hier noch fehlt ist die Umwandlung der Flussdiagramm der Turing- in eine passende Registermaschine. Das geschieht wie folgt:

• Aufbereitung der Eingabe: jedes Register bekommt die eindeutige Nummer der Eingabeworte. Nur Register $R_0$, unser Ausgaberegister bleibt leer. Die Worte der $k$ Arbeitsbänder werden so alle in die Register abgebildet. Ein Register bekommt also $\sigma(a)$ zugewiesen, z.B. $R_1=\sigma(abb)=10$.
• Simulation des Flussdiagramms der Turingmaschine (hier lasse ich die Details erstmal weg, evtl. trage ich sie nach)

Nun können wir auch mit der formalen Definition des Zusammenhangs etwas anfangen:

Sei $\Sigma$ ein Alphabet, $\nu_\Sigma : \mathbb{N} \rightarrow \mathbb{N}$ eine Standardnummerierung von $\Sigma^*$, $k \in \mathbb{N}$. Es sei $f : \subseteq \mathbb{N}^k \rightarrow \mathbb{N}$ und $g : \subseteq (\Sigma^*)^k \rightarrow \Sigma^*$. Dann gilt:

$f$ berechenbar $\Longleftrightarrow$ $\nu_\Sigma f\bar{\nu_\Sigma}^-1 : \subseteq (\Sigma^*)^k \rightarrow \Sigma^*$ berechenbar.

$g$ berechenbar $\Longleftrightarrow$ $\nu_\Sigma^-1 g\bar{\nu_\Sigma} : \subseteq \mathbb{N}^k \rightarrow \mathbb{N}$ berechenbar.

Harter Tobak. Der Satz besagt eig. nichts anderes, als dass

Die Wortfunktion $g$ genau dann berechenbar ist, wenn ihre Verschlüsselung $\nu_\Sigma^-1 g\bar{\nu_\Sigma}$ eine berechenbare Zahlenfunktion ist

und

Die Zahlenfunktion $f$ genau dann berechenbar ist, wenn ihre Verschlüsselung $\nu_\Sigma f\bar{\nu_\Sigma}^-1$ eine berechenbare Wortfunktion ist.

Also genau das, was wir oben bereits beschrieben haben. Versuchen wir dass mal anhand eines Beispiels aufzudröseln:

Beispiel: $\Sigma := \{a,b\}$, $\nu_\Sigma : \mathbb{N} \rightarrow \Sigma^*$ mit der Ordnungsfunktion $a: \{1,...,n\} \rightarrow \Sigma$,

d.h. $a$ ist wieder unser $1$. und $b$ unser $2$. Element in der Ordnung.

Wir definieren $f$ und $g$ willkürlich:

$f(x)\begin{cases} {} & 1, \mbox{ wenn } x = 2 \\{} & 2, \mbox{ wenn } x = 1 \end{cases}$

$g(x)\begin{cases} {} & a, \mbox{ wenn } x = b \\{} & b, \mbox{ wenn } x = a \end{cases}$

Wir müssen uns anschauen, was $\nu_\Sigma^-1 g\bar{\nu_\Sigma}$ und $\nu_\Sigma f\bar{\nu_\Sigma}^-1$ aus der Definition von oben denn nun tatsächlich tun.

Fangen wir mit $\nu_\Sigma^-1 g\bar{\nu_\Sigma}$ an, denn es liefert uns zu der Nummer des Definitionswertes (ein Wort) die Nummer des Bildes/Funktionswerts (ja eig. auch ein Wort):

Wir machen uns zunächst einmal klar, dass $\nu_\Sigma(1) = a$ ist, denn $a$ ist das erste Element und $\nu_\Sigma$ gibt uns zu einer Zahl das Wort aus. Die Inverse wäre dann $\nu_\Sigma^-1(a) = 1$, zu einem Wort bekommen wir also seine eindeutige Nummer.

Und lasst euch von $\nu_\Sigma^-1 g\bar{\nu_\Sigma}(i)$ nicht erschrecken. Es ist nur eine Komposition aus den oben genannten Funktionen und sieht geklammert weniger bedrohlich aus: $\nu_\Sigma^-1 (g(i))$. Aber der Reihe nach.

Unserer oben definierten Funktion $g$ nach, ist z.B. $g(a) = b$. Zu dem  Definitionswert $a$ bekommen wir also das Bild/den Funktionswert $b$. Was tun wir nun wenn wir statt auf Worten (was $a$ und $b$ ja selbstredend sind) nun auf den zugehörigen Zahlen rechnen wollen? Die Funktionalität der Ursprungsfunktion soll dabei natürlich erhalten bleiben. Und genau das geht mit unserem $\nu_\Sigma^-1 g\bar{\nu_\Sigma} (i)$, was ja nur - wie gesagt - eine Komposition von Funktionen ist.

Wir tun das, was wir wollten (auf den Zahlen der Worte $a$ und $b$ rechnen statt auf den Worten selbst) und setzen $i = 1$, da der Zahlenwert unseres Arguments $\nu_\Sigma^-1(a)=1$ ist und dröseln auf:

$\begin{array}{lcl}\nu_\Sigma^-1 g\nu_ \Sigma(1)&=&\nu_\Sigma^-1 (g (\nu_ \Sigma(1)))&\mbox{Ausklammern fuer bessere Lesbarkeit}&\\ {}&=&\nu_\Sigma^-1 (g (a))&\mbox{da }\nu_ \Sigma(1) = a \mbox { ist}&\\ {}&=&\nu_\Sigma^-1 (b) &\mbox{da } g (a) = b \mbox { ist}&\\ {}&=&2&\mbox {da }\nu_\Sigma^-1 (b) = 2 \mbox { ist}&\end{array}$

Ergebnis passt? Passt!

Damit haben wir dank unserer Standardnummerierung unsere Wortfunktion $g$ in eine Zahlenfunktion überführt und können ruhigen Gewissens erneut sagen:

Die Wortfunktion $g$ ist berechenbar gdw. ihre Verschlüsselung $\nu_\Sigma^-1 g\bar{\nu_\Sigma}$ eine berechenbare Zahlenfunktion ist.

Damit kann man nun eine Zahlenfunktion angeben, welche statt $a$ auf $b$ abzubilden nun eine $1$ auf eine $2$ abbildet. Ist diese berechenbar, so ist auch eine Wortfunktion berechenbar.

Analog geht der gleiche Spaß mit $\nu_\Sigma f\bar{\nu_\Sigma}^-1$, was unsere Zahlenfunktion $f$ in eine Wortfunktion verschlüsselt. Wir setzen statt $i = 1$ nun einfach $i=a$ und schauen ob wir $b$ herausbekommen.

$\begin{array}{lcl}\nu_\Sigma f\bar{\nu_\Sigma}^-1(a)&=&\nu_\Sigma(f(\bar{\nu_\Sigma}^-1(a)))&\mbox{Ausklammern fuer bessere Lesbarkeit}&\\ {}&=&\nu_\Sigma(f(1))&\mbox{da }\bar{\nu_\Sigma}^-1(a) = 1 \mbox { ist}&\\ {}&=&\nu_\Sigma(2) &\mbox{da } f (1) = 2 \mbox { ist}&\\ {}&=&b&\mbox {da }\nu_\Sigma(2) = b \mbox { ist}&\end{array}$

Wow! Was man mit den natürlichen Zahlen alles anstellen kann! Wir haben unsere Zahlenfunktion $f$ nun in eine Wortfunktion verschlüsselt und schließen unser Beispiel mit folgenden Worten ab:

Die Zahlenfunktion $f$ ist berechenbar gdw. ihre Verschlüsselung $\nu_\Sigma f\bar{\nu_\Sigma}^-1$ eine berechenbare Wortfunktion ist.

That's it.

Antwort zum Lernziel: mittels Standardnummerierung ist es uns möglich Worte in Zahlen und Zahlen in Worte bijektiv zu verschlüsseln. Da Register- und Turingmaschinen über Flussdiagrammen definiert sind, können wir diese ineinander simulieren und durch die Standardnummerierung so mit Registermaschinen auf Worten und mit Turingmaschinen im Endeffekt auf Zahlen arbeiten.

Lernziel 3

Definition der primitiv-rekursiven Funktionen

Im Beitrag über primitiv rekursive Funktionen und LOOP Berechenbarkeit haben wir das Thema bereits behandelt. Daher nur ein kurzer Abriss der Definition:

Eine Funktion $f:\mathbb{N}^k\rightarrow\mathbb{N}$ heißt primitiv-rekursiv wenn sie sich in endlich vielen Schritten aus der menge der Grundfunktionen durch wiederholtes Anwenden der Substitution und primitiver Rekursion erzeugen lässt.

Diese Menge nennen wir $PRK$.

PS: sie sind alle total (wichtig!) und eine echte Teilmenge der $\mu$-rekursiven Funktionen (kommen wir später noch darauf zurück).

Die im Skript genannten Grundfunktionen sind:

• Null- und einstellige Nullfunktion
• Nachfolgefunktion
• Projektion

Alle Funktionen, die wir damit und durch wiederholtes Anwender der primitiven Rekursion und Substitution erstellen können, sind ebenfalls primitiv-rekursiv aufgrund der Abgeschlossenheit. Beispiele zu diesen findet Ihr im oben verlinkten Beitrag.

Wir hatten das bereits im Beitrag zur $LOOP$-Berechenbarkeit ausgearbeitet, es sei dennoch der Vollständigkeit halber darauf hingewiesen:

Eine Funktion $f$ ist $LOOP$-berechenbar genau dann wenn sie primitiv-rekursiv ist.

Nicht vergessen.

Antwort zum Lernziel: die Menge der primitiv-rekursiven Funktionen $PRK$ wird  mittels der oben genannten Grundoperationen und wiederholtes Anwenden der Substitution ($Sub$) und primitiver Rekursion ($Prk$) gebildet. Es sind alles totale Funktionen (d.h. überall definiert) und bilden eine Teilmenge der $\mu$-rekursiven Funktionen.

Lernziel 4

Beweis, dass bestimmte Funktionen primitiv-rekursiv sind

In dem oben verlinkten Beitrag könnt Ihr euch die Details dazu zu Gemüte führen. Wir zeigen dort, dass die Addition primitiv-rekursiv ist.

Antwort zum Lernziel: Für den Beweis, dass eine Funktion primitiv-rekursiv ist wird diese einfach mittels der Grundoperationen (oder der als primitiv-rekursiv bereits bewiesenen anderen Operationen) nachgebildet. Damit gilt die Funktion für ein $n$ als bewiesen. Mittels vollständiger Induktion wird es dann auch für $n+1$ gezeigt.

Ex-Lernziel: Rechenzeitsatz

Ebenfalls wird im Skript jedoch der Rechenzeitsatz erwähnt. Der besagt nichts anderes, als dass eine Maschine $M$, welche eine Funktion $f: \mathbb{N}^k \rightarrow \mathbb{N}$ für eine Eingabe von $x_1,...,x_k$ eine bestimmte Anzahl an Schritten rechnet. Die Anzahl der Schritte wird mit $Zeit_M(x_1,...,x_k)$ bezechnet.

Gibt es diese Anzahl von Schritten, so ist die Funktion $f$ primitiv rekursiv und die Anzahl der Schritte durch eine Funktion $A_n$ ($Zeit_M(x_1,...,x_k) <= c \cdot max(x_1,...,x_k) + c$) beschränkt. Wir haben hier also nichts weiter als die Beschränkung der Rechenschritte einer Registermaschine beim Berechnen einer Funktion abhängig vom Eingabewert der Funktion, einer Konstanten und einer anderen primitiv rekursiven Funktion. Im Skript wird $A_n$ als Funktion verwendet, aber Achtung: das ist nicht die Ackermann-Funktion, denn diese ist nicht primitiv rekursiv und $A_n$ muss primitiv rekursiv sein!

Alle Funktionen, die sich auf einer Registermaschine nicht in $c \cdot 2^x + x$ (Exponentialzeit) berechnen lassen, gelten lt. Skript als "nicht in der Praxis berechenbar". Damit sind alle in der Praxis berechenbaren Funktionen primitiv rekursiv. Die Isomorphie von Graphen ist z.B. in Exponentialzeit berechenbar, aber es ist noch nicht bewiesen ob es nicht einen effizienteren Algorithmus gibt.

Lernziel 5

Definition der $\mu$-rekursiven Funktionen

Auch das haben wir bereits in einem Eintrag für die $\mu$-rekursiven Funktionen bereits behandelt. Wir fassen das nochmal in einem Merksatz zusammen:

Die ggf. partielle Funktionen (d.h. sie sind ggf. nicht überall definiert: Beispiel Wurzelfunktion) $f$ ist $\mu$-rekursiv wenn sie mittels der Grundoperationen: Nachfolge-, null- und einstellige Funktion sowie durch wiederholtes Anwenden der Substitution, primitiver Rekursion und des $\tilde{\mu}$-Operators abbilden lässt.

Gemerkt? Die Totalität unserer Funktion $f$ ist für die $\mu$-Rekursion nun nicht mehr notwendig. Auch haben wir zusätzlich zu den Grundoperationen, der Substitution und der primitiven Rekursion nun mit dem $\mu$-Operator das Nullsetzen der Funktion mit drin.

Aber Achtung: der $\mu$-Operator ist im Skript nur auf totalen Funktionen definiert. Bei partiellen Funktionen können wir in Endlosschleifen geraten, aus denen wir sonst nicht mehr herauskommen. Durch eine kleine Erweiterung können wir aber auch auf partiellen Funktionen arbeiten (siehe hier). Ich schreibe dann später noch ein par Kleinigkeiten dazu sobald ich alle Kurseinheiten nochmal überarbeite.

Merke: während man die primitiv rekursiven Funktionen also in $WHILE$-Schleifen nachbilden kann, kann man $\mu$-rekursiven Funktionen nur in $WHILE$-Schleifen und nicht in $LOOP$-Schleifen nachbilden. Das liegt daran, dass die Anzahl der Iterationen bei der primitiven Rekursion im Vorfeld bekannt ist (FOR 1 TO 5 DO X) und bei der $\mu$-Rekursion (DO X WHILE i NOT 0) nicht. Dieses "Nullstellen" unserer Funktion besorgt uns der $\mu$-Operator.

Update: Ein ausführliches Beispiel mittels partieller Subtraktion zum Nullsetzen habe ich im oben verlinkten Beitrag zur $\mu$-Rekursion selbst gebracht. Dort wurde gezeigt, wie man die $\mu$-Rekursion anwendet um eine Funktion, die nicht mittels primitiver Rekursion (LOOP) berechenbar ist, als berechenbar nachzuweisen.

Es stellt sich die Frage, warum der $\mu$-Operator auf totalen Funktionen definiert ist und der $\tilde{\mu}$-Operators auch auf partiellen Funktionen arbeiten kann.

Beispiel $f:\subseteq\mathbb{N}\rightarrow\mathbb{N}$ mit $f(x)=\sqrt{x}$ als $\mu$-berechenbar nachweisen

Was müssen wir hier tun? Offensichtlich ist $\sqrt{x}$ auf den natürlichen Zahlen partiell, denn $\sqrt{5}=div$, da das Ergebnis keine natürliche Zahl ist. Wenn wir diese Funktion nun als $\mu$-rekursiv nachweisen wollen, müssen wir folgendes tun:

Wir basteln uns durch "Nullsetzen" aus unserer Wurzelfunktion $f$ eine neue Funktion $h$, die uns in Abhängigkeit von $y$ eine $0$ ausgibt wenn $\sqrt{x}$ korrekt berechnet wurde und ansonsten etwas anderes als eine $0$ als Ergebnis hat. Kann die Berechnung nicht korrekt abgeschlossen werden, erhöht $\mu$ auf $h$ das $y$ und läuft ewig weiter.

Sie darf aber kein undefiniertes Ergebnis bringen, da wir ansonsten mit dem nächsten $y$ nicht fortfahren könnten. Das ist der Grund, warum der $\mu$-Operator nur auf totalen Funktionen definiert ist. Wäre die "nullgesetzte" Funktion $h$ nicht total, hätte das einen Abbruch zur Folge und unser $\mu$ würde uns nichts brauchbares liefern.

Die aus daraus entstehende Funktion $\tilde{\mu}(h)(x)$ ist aber partiell. Denn wir bekommen das Ergebnis, die kleinste Nullstelle, nur dann wenn die Berechnung in Ordnung war. Ansonsten läuft unser $\mu$ ja durch die Totalität von der "nullgesetzten" Funktion endlos weiter und wir kommen nie zum Stillstand.

Formal ausgedrückt wäre dies:

$\tilde{\mu}(h)(x)=\begin{cases}0\text{ wenn }\sqrt{x}\text{ existiert}\\div\text{ sonst}\end{cases}$

Damit ist $\tilde{\mu}$ partiell.

PS: betrachtet $\tilde{\mu}(h)(x)$ bitte als "Die aus $h$ entstehende Funktion", d.h. als komplettes Gebilde und nicht als Funktion $\tilde{\mu}$ auf $h$ auf $x$.

Schaut euch, wie gesagt, noch einmal ein konkretes Beispiel zur partiellen Subtraktion hier an. Dort seht Ihr auch, wie man eine Funktion nullsetzen kann.

Antwort zum Lernziel: die $\mu$-rekursiven Funktionen können - im Gegensatz zu primitiv-rekursiven - auch partiell sein. Sie werden ebenfalls durch die gleichen Grundoperationen und Substitution und primitive Rekursion gebildet wie die primitiv rekursiven Funktionen.

Durch den $\mu$-Operator jedoch wird eine Möglichkeit geschaffen die Anzahl der Schleifendurchläufe, nicht von Anfang an festlegen zu müssen (wie das bei der primitiven Rekursion der Fall ist), indem man die Funktion "Nullsetzt" und mit dem $\mu$-Operator die erste Nullstelle sucht.

Es gibt damit Funktionen, die mittels $WHILE$-Schleife implementierbar, aber nicht primitiv-rekursiv sind (Ackermann-Funktion z.B.). Die Klasse der implementierbaren Funktionen ist damit größer als die Klasse der primitiv-rekursiven Funktionen.

Lernziel 6

Erläuterung der Churchschen These

Etwas Vorarbeit: es gibt zunächst einen großen Unterschied zwischen maschinell berechenbar und Register-(und damit auch Turing-)berechenbar. Worin liegt der?

Nehmen wir als Beispiel die Ackermann-Funktion. Wir können sie implementieren und wissen daher, dass sie ($WHILE$-)berechenbar ist und mit einer Turing- oder Registermaschine berechnet werden kann.

Wollt Ihr mal $Ackermann(10)$ berechnen? Macht das mal. Und dann könnt Ihr hier weiterlesen. Okay, das war gemein: es gibt keinen Rechner, der genügend Speicher hätte diese Zahl zu speichern. Ebenfalls würde selbst das Alter des Weltalls nicht ausreichen um einen Speicher mit dieser Zahl zu füllen (Satz geklaut aus dem Skript).

Vielleicht habt Ihr nun eine kleine Vorstellung, was den Unterschied ausmacht zwischen intuitiv berechenbar und maschinell-berechenbar.

In der theoretischen Informatik ist uns diese "maschinelle Berechenbarkeit" aber nicht wirklich wichtig; wir kümmern uns eher um die erste Eigenschaft: die intuitive Berechenbarkeit. Die Speicherkapazität und die Geschwindigkeit der Maschinen ändert sich und es gibt immer mehr Funktionen, die maschinell berechnet werden können. Aber die (intuitiv) berechenbaren Funktionen ändern sich nicht nicht. Sie können entweder berechnet werden, oder eben nicht.

Kommen wir daher zur Churchschen These selbst (aus der Wikipedia, die aber  etwas von der im Skript abweicht. Warum sage ich gleich):

Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.

Wir erinnern uns an den Begriff der intuitiven Berechenbarkeit: es gibt einen Algorithmus für eine Funktion $f:\subseteq X\rightarrow Y$, der die Funktion berechnet. Auch können wir uns auf einstellige Zahlenfunktionen $f:\mathbb{N}\rightarrow\mathbb{N}$ beschränken, da wir Wortfunktionen mittels der Standardnummerierung in Zahlen codieren können und mehrstellige Zahlenfunktionen letztendlich durch die Cantorsche Paarungsfunktion in einstellige Zahlenfunktionen überführt werden können. Wir betrachten also im Endeffekt nur noch die Einband-Turing- (Wortfunktionen) oder die Registermaschinen (Zahlenfunktionen).Aufgrund der Äquivalenz beider Berechnungsmodelle können wir uns zudem aussuchen, was wir betrachten.

Lange Rede, kurzer Sinn: um uns also nicht mit "maschinell" und "intuitiv" auseinandersetzen und den Begriff "maschinell" alle paar Jahre neu definieren zu müssen, setzen wir einfach "maschinell" mit "intuitiv" gleich. Und da wir mit Register- und Turing-Berechenbarkeit (durch die Standardnummerierung) ein Äquivalentes Berechnungsmodell haben, können wir statt dem oben genannten Satz aus der Wikipedia, problemlos auch die Churchsche These aus dem Skript herleiten:

Die Register-berechenbaren Funktionen sind genau die maschinell berechenbaren Zahlenfunktionen.

Deutlich geworden?

Die These bedeutet also nichts anderes, als dass man mit der Turing- oder Registermaschine alle intuitiv/maschinell berechenbaren Funktionen berechnen kann. Sie ist zwar nicht beweisbar, da wir den Begriff "intuitiv berechenbar" nicht exakt formulieren können, sie wird aber allgemein akzeptiert.

Gelingt es uns ein Computermodell anzugeben, dass Funktionen berechnen kann, die mit der Turingmaschine nicht berechnet werden können, so könnten wir die These widerlegen (Ihr wisst, also was zu tun ist!).

Noch ein paar Hintergrund-Details:

Es ist noch niemandem gelungen eine maschinell-berechenbare Funktion anzugeben, die nicht Turing/Register-berechenbar ist, daher liegt der Schluss nahe, dass wir (ohne Berücksichtigung der Faktoren wie Zeit und Speicher) sagen können, dass die maschinell-berechenbaren Funktionen wirklich genau die intuitiv Register/Turing-berechenbaren Funktionen sind.

Antwort zum Lernziel: Die Churchsche These besagt, dass alle intuitiv bzw. maschinell berechenbaren Funktionen genau die Turing- bzw. Register-berechenbaren Funktionen sind. Sie ist aufgrund des fehlenden Formalismus des Begriffs "intuitiv" nicht beweisbar, konnte aber auch nicht widerlegt werden.

Lernziel 7

Beweis der Existenz von nicht-berechenbaren Funktionen durch Diagonalisierung

Wir rekapitulieren auch hier (im Beitrag über Entscheidbarkeit könnt ihr euer Wissen darüber auffrischen): eine Menge ist entscheidbar (d.h. rekursiv) wenn für jede Eingabe aus der Definitionsmenge entschieden werden kann, ob sie eine Eigenschaft besitzt oder nicht. Formal ausgedrückt:

Entscheidbar/rekursiv: eine Menge heißt entscheidbar falls die charakteristische Funktion berechenbar ist.

Ich wiederhole hier aus dem oben verlinkten Beitrag die formale Definition:

Eine Menge $T \subseteq M$ ist entscheidbar/rekursiv wenn die charakteristische Funktion $\chi_T: M \rightarrow \{0,1\}$ definiert durch

$\chi_T(t)=\begin{cases} 1, & \mbox{ falls } t \in T \\ 0, & \mbox{ sonst}\end{cases}$

berechenbar ist (Achtung: sie muss berechenbar sein!)

Wir haben also eine definitive Aussage zu einer Eigenschaft eines Elements: wir können für jedes Element entscheiden ob es diese Eigenschaft besitzt oder nicht.

Was wäre so eine entscheidbare Eigenschaft? Die Entscheidung ob eine Zahl $x$ eine Primzahl ist oder nicht wäre entscheidbar.

Den Begriff der Entscheidbarkeit haben wir aber nur für Mengen definiert. Wir interessieren uns hier aber für Funktionen und wollen zeigen, dass es Funktionen gibt, die nicht berechenbar sind. Wir gehen im Prinzip genauso vor, wie Cantor das in seinem zweiten Diagonalisierungsbeweis getan hat. Im Beitrag über Entscheidbarkeit bekommt Ihr einen Einblick über diese Beweismethode am Beispiel der Mächtigkeit von reellen und natürlichen Zahlen.

Aber wollen wir den Beweis aus dem Skript mal Schritt für Schritt durchgehen und die Diagonalisierung nicht auf Mengen, sondern auf Funktionen anwenden. Was haben wir vor? Wir wollen zeigen, dass es nicht-berechenbare Funktionen gibt. Und so gehen wir dazu vor:

1. Zunächst definieren wir uns eine surjektive Funktion $\psi$ mit $\psi:\mathbb{N}\rightarrow P^{(1)}$.Was sie genau macht, zeigen wir gleich.

2. $\Gamma$ ist das Alphabet der $WHILE$-Programme, während $WP\subseteq\Gamma^{*}$ dann die Menge aller $WHILE$-Programme ist. Kann es über $\Gamma$ auch "Nicht-$WHILE$-Programme geben? Sicher: irgendwelches Kauderwelsch, dass aus den Zeichen des Alphabets $\Gamma$ besteht.

3. Wir Standard-nummerieren auch $\Gamma^{*}$ mit $\nu_\Gamma$, diese ist also bijektiv. Alle Worte über $\Gamma$ haben also eine eindeutige Nummer. Bereits jetzt haben wir das Gefühl, dass in der Menge $WP$ weniger drin ist, als in der Menge $\Gamma^{*}$. Aber langsam.

Was haben wir bis jetzt? Die Nummerierung aller Worte über unserem Alphabet $\Gamma$ mit $\nu_\Gamma$. Hier ist das Spannende, dass selbstverständlich nicht alle Worte über $\Gamma$ ein $WHILE$-Programm sind (siehe Punkt 2). Es kann auch irgendwelches Kauderwelsch sein. Die Menge der $WHILE$-Programme $WP$ ist damit eine Teilmenge der Worte über $\Gamma$: $WP\subseteq\Gamma^{*}$.

Und wir haben eine "Nummerierung" der ggf. partiell einstelligen, berechenbaren Funktionen $f\in{P^{(1)}}$ mittels $\psi$.

Während wir $WHILE$-Programme mit der Eingabe für Registermaschinen (d.h. unsere Registerbelegung) füttern, füttern wir Funktionen einfach nur mit einem Eingabewert. Ist $P$ unser $WHILE$-Programm, so bezeichnet $AC(\tau(P)(EC(x)))$ die von $P$ berechnete Zahlenfunktion.

Schon wieder diese Kompositionen. Am besten wir kümmern uns direkt um ein

Beispiel: $f(x)=x+5$

Diese Funktion $f\in P^{(1)}$ addiert zu einem Eingabewert $x$ einfach nur eine $5$. Das folgende $WHILE$-Programm $W\in{WP}$ tut dies ebenfalls:

i=5;
WHILE $i\neq 0$ DO

   x=x+1;

   i=i-1;

END;

Da die $WHILE$-Programme mittels Register- oder Turingmaschinen definiert werden, brauchen wir ein passendes Flussdiagramm $F$:

Seht Ihr das Problem?

Das $WHILE$-Programm $W$ können wir nicht einfach mit unserem Funktions-Eingabeparameter $x$, füttern, sondern brauchen eine Registerbelegung $(R_0,R_1,...)$. Was tun? Unsere Eingabecodierung bemühen, die wir bereits kennen. Wir definieren:

$EC(x)=(0,x)$

(nicht vergessen, das 1. Register $R_0$ bleibt leer, da es unser Ausgaberegister ist).

Soweit so gut. Wir starten unser $WHILE$-Programm $W$ nun mit $W(EC(x))=W((0,x))$ und bekommen als Ausgabe $W(0,x)=(x+5,x,0)$. Auch hier ist die Ausgabe des Flussdiagramms nicht der Ausgabewert, den wir bei der Funktion $f$ erwarten!

Ihr ahnt es sicherlich schon: wir brauchen eine Ausgabecodierung und definieren:

$AC(d_0,d_1,d_2)=d_0$

Für uns ist also nur das 1. Register spannend.

Und wenn wir uns die Definition von $\tau(W)$ (damit wird die von $W$ berechnete Funktion bezeichnet) vor Augen führen, erschließt sich auch direkt unser $AC(\tau(W)(EC(x)))$. Lassen wir es mal mit $x=5$ laufen:

$\begin{array}{}AC(\tau(W)(EC(5)))&=AC(\tau(W)(0,5))\\&=AC(10,5,0)\\&=10\end{array}$

Done!

Nennen wir also $AC(\tau(W)(EC(x)))$ die von $W$ berechnete, einstellige Zahlenfunktion.

Für unser Vorgaben brauchen wir noch eins: $Z:\mathbb{N}\rightarrow\mathbb{N}$, unsere Nullfunktion. Egal, was wir da rein werfen, wir bekommen immer eine $0$ heraus: $Z(n)=0$ für alle $n$.

Jetzt sind wir gerüstet um $\psi$ für unser Vorhaben zu definieren:

$\psi(i):=\begin{cases}AC(\tau(W)(EC(x)))&\text{ falls }\nu_\Gamma(i)\in{WP}\\Z&\text{ sonst}\end{cases}$

Ist ein $i$ eine Nummer eines legitimen $WHILE$-Programms, d.h. es gilt $\nu_\Gamma(i)\in{WP}$, so berechnet dieses $WHILE$-Programm natürlich auch etwas: irgendeine Funktion aus $P^{(1)}$. Ihre Ausgabe ist (wie wir oben gesehen haben) ja genau $AC(\tau(W)(EC(x)))$. Und das ist dann unser $\psi(i)$.

Es kann aber auch Nummern geben, die nicht zu einem $WHILE$-Programm gehören (unser oben genanntes Kauderwelsch). Da Kauderwelsch nichts berechnen kann, haben wir auch keine Ausgabe. Wir brauchen aber für unseren Beweis in jedem Fall eine und definieren in diesem Fall einfach, dass wir mit unserer Nullfunktion $Z$ eine bekommen.

Durch die Surjektivität von $\psi$ hat jede Funktion aus $P^{(1)}$ eine zugehörige Zahl und es müsste also auch für die folgende Funktion $g$ eine Zahl $i$ geben:

$g(i):=\begin{cases}1&\text{ falls }\psi(i)(i)=0\\0&\text{ sonst}\end{cases}$

Was ist $\psi(i)(i)$? Ganz einfach: $\psi(i)$ ist die von $W$ berechnete, einstellige Zahlenfunktion $AC(\tau(W)(EC(x)))$ wenn es ein richtiges $WHILE$-Programm und kein Kauderwelsch ist. Damit ist $\psi(i)(i)$ einfach nur das $WHILE$-Programm mit der Nummer $i$, welches als Eingabeparameter die Nummer $i$ bekommt.

Die Bedeutung erschließt sich hier am besten auch an einem

Beispiel:

Nehmen wir an, das obige $WHILE$-Programm $W$ hat die willkürliche Nummer $561$. Da es ein echtes $WHILE$-Programm ist, gilt damit $\nu_\Gamma(561)\in{WP}$ und

$\begin{array}{}\psi(561)&=AC(\tau(\nu_\Gamma(561))(EC(x)))\\&=AC(\tau(\nu_\Gamma(561))(0,x))\\&=AC(x+5,5,0)\\&=x+5\end{array}$

Und nun übergeben wir $\psi(561)$ die $561$ als Parameter:

$\begin{array}{}\psi(561)(561)&=AC(\tau(\nu_\Gamma(561))(EC(561)))\\&=AC(\tau(\nu_\Gamma(561))(0,561))\\&=AC(561+5,5,0)\\&=566\end{array}$

Damit ist $\psi(561)(561)=566$.

Und unser $g$ wäre der obigen Definition nach $g(561)=0$.

Was würde passieren, wenn $W$ kein $WHILE$-Programm wäre? D.h. $\nu_\Gamma(561)\notin{WP}$?

Dann wäre $\psi(561)(n)=0$ der Definition nach für jedes $n$. Und $g$? $g$ wäre:

$g(561)=1$.

Wie wir an dem Beispiel erkennen, ist sichergestellt, dass $g$ in jedem Fall einen anderen Funktionswert annimmt als $\psi(i)$ wenn beide Funktionen mit $i$ gefüttert werden.

Dämmert es euch bereits? Was ist denn $\psi$ nochmal? Das ist unsere "Nummerierung" aller einstelligen, berechenbaren Funktionen aus $P^{(1)}$! In $\{\psi(0),\psi(1),...\}$ liegen sie alle drin. Und wo ist $g$? $g$ gehört zweifelsohne auch in die Menge aller einstelligen, berechenbaren Funktionen aus $P^{(1)}$. Dann liegt es doch sicherlich auch irgendwo $\{\psi(0),\psi(1),...\}$, oder?

Nein! $g$ ist von jeder Funktion aus $\{\psi(0),\psi(1),...\}$ durch seine Definition, dass es immer einen anderen Wert bei $g(i)(i)$ annimmt als $\psi(i)(i)$ verschieden, obwohl es definitiv zu $P^{(1)}$ gehört. Widerspruch!

Allgemein beweist man, dass Funktionen nicht berechenbar sind durch Widerspruchsbeweise. Im Skript wird dazu genau das gleiche Verfahren angewandt wie im zweiten Diagonalisierungsbeweis von Cantor: man geht von Vollständigkeit aus, zeigt, dass man noch etwas hinzufügen kann, was sich auf jeden Fall von allen anderen Einträgen unterscheidet (bei Diagonalisierungsbeweisen wird das Diagonalelement eines Eintrags für den neuen Eintrag abgeändert und verändert, so dass beide Einträge mindestens an der abgeänderten Stelle unterschiedlich sind) und stößt so auf einen Widerspruch.

Damit haben wir eine Funktion definiert, die offensichtlich nicht berechnet werden kann. Es folgt: $g\notin{P^{(1)}}$.

Antwort zum Lernziel: die Angabe einer nicht berechenbaren Funktion gelingt durch Widerspruchsbeweis mittels Diagonalisierung, ähnlich dem Verfahren, das Georg Cantor bereits für sein zweites Diagonalargument angewendet hat um die Überabzählbarkeit der reellen Zahlen zu beweisen.

Dazu wird angenommen, man habe alle berechenbaren Funktionen aufgelistet und zeigt, dass es eine weitere Funktion gibt, die sich definitiv von allen anderen Funktionen unterscheidet. Woraus folgt, dass diese nicht berechenbar sein kann. Zumindest nicht wenn wir Berechenbarkeit mit dem üblichen Begriff für Berechenbarkeit, der Register- und/oder Turing-Berechenbarkeit gleichsetzen.

Das war viel Stoff. Sicherlich sind irgendwo noch Ungenauigkeiten drin oder es haben sich evtl. auch Fehler eingeschlichen. Über Hinweise in den Kommentaren würde ich mich freuen.

Inhaltsverzeichnis

1. Berechenbarkeit von Zahlen- und Wortfunktionen
2. Entscheidbarkeit (rekursiv) und Semi-Entscheidbarkeit (rekursiv aufzählbar)
3. Erstes und zweites Diagonalargument von Cantor

Im Skript wird dieses Thema schnell durchgekauft. Persönlich halte ich es jedoch für sehr wichtig, sich diese Begrifflichkeiten unbedingt zu merken. Also fangen wir auch direkt an:

Berechenbarkeit

Noch einmal kurz als Wiederholung bzgl. Berechenbarkeit: dem Begriff selbst liegen Berechnungsmodelle zugrunde. Wir haben hier die LOOP-Berechenbarkeit (primitiv rekursive Funktionen) und die WHILE-Berechenbarkeit ($\mu$-rekursive Funktionen). Während jedes LOOP-Programm durch ein WHILE-Programm ersetzt werden kann, kann nicht jedes WHILE-Programm durch ein LOOP-Programm ersetzt werden, d.h. die LOOP-Programme sind eine echte Untermenge der WHILE-Programme. Wann ist eine Funktion denn nun berechenbar? Genau dann:

Eine (ggf. partielle) Zahlenfunktion $f : \subseteq \mathbb{N}^k \rightarrow \mathbb{N}$ ist genau dann berechenbar, wenn es eine Registermaschine $M$ gibt, die die Funktion berechnet. Wenn also $f = f_M$ gilt.

Und was ist mit Wortfunktionen für Turing-Maschinen?

Eine (ggf. partielle) Wortfunktion $g : \subseteq (\Sigma^*)^k \rightarrow \Sigma^*$ ist genau dann berechenbar, wenn es eine Turing-Maschine $T$ gibt, die die Funktion berechnet. Wenn also $g =g_T$ gilt.

Aber eig. brauchen wir die Turing-Maschinen garnicht. Warum? Zauberwort: Standardnummerierung. Wir können dadurch die Berechenbarkeit von Worten auf die Berechenbarkeit von Zahlen zurückführen indem wir die Wortfunktionen mittels Standardnummerierung in Zahlen codieren und diese mit Registermaschinen berechnen. Da die Standardnummerierung bijektiv ist, können wir den Spaß auch anders herum aufziehen und unsere Zahlenfunktionen durch Turing-Maschinen berechnen lassen nachdem wir die Zahlenfunktionen in Worte codiert haben.

Schaut dazu in den entsprechenden Beitrag für die Kurseinheit 4. Dort wird das Thema dann etwas genauer behandelt. Wichtig ist, dass man sich den Zusammenhang zwischen Wort- und Zahlenfunktionen und das Bindeglied (Standardnummerierung) zwischen diesen merkt.

(Semi-) Entscheidbarkeit

Wir unterscheiden hier die Entscheidbarkeit und die Semi-Entscheidbarkeit. Ihr Kern ist die charakteristische Funktion. Wozu brauchen wir sie? Der Begriff "Entscheidbarkeit" ist auf Mengen fokusiert, für uns sind aber eher Funktionen spannend, wo nur der Begriff "Berechenbarkeit" verwendet wird. Die charakteristische Funktion ist das Bindelglied zwischen diesen Mengen und der Funktionen (den Satz habe ich aus dem Buch von Dirk W. Hoffmann geklaut). Formalisieren wir das:

Eine Menge $T \subseteq M$ ist entscheidbar/rekursiv wenn die charakteristische Funktion $\chi_T: M \rightarrow \{0,1\}$ definiert durch

$\chi_T(t)=\begin{cases} 1, & \mbox{ falls } t \in T \\ 0, & \mbox{ sonst}\end{cases}$

berechenbar ist (Achtung: sie muss berechenbar sein!)

Was ist damit gemeint? Damit ist gemeint, dass man hier eindeutig entscheiden kann ob ein Element $t$ aus der Menge $M$ in der Menge $T$ sind. Es wird nach endlicher Zeit also eindeutig entschieden ob JA oder NEIN.

Beispiel: ob eine Zahl gerade ist oder eine Primzahl ist, ist entscheidbar/rekursiv (Wikipedia). Diese Zahlen sind auch rekursiv aufzählbar (denn ich kann sie ja aufzählen).

Und nun zur Semi-Entscheidbarkeit/rekursiver Aufzählbarkeit.

Eine Menge $T$ ist semi-entscheidbar/rekursiv aufzählbar wenn die partielle charakteristische Funktion $\chi^{'}_T: M \rightarrow \{1\}$ definiert durch

$\chi^{'}_T(t)=\begin{cases} 1, & \mbox{ falls } t \in T \\ \perp, & \mbox{ sonst}\end{cases}$

Diesen Spaß nennt man also semi-entscheidbar.  D.h. wenn das Element $t$ aus $M$ in $T$ liegt, so wird nach endlicher Zeit ein JA (oder auch NEIN wenn man anders herum testen möchte) ausgegeben. Wenn nicht, so hängen wir ggf. in einer Endlosschleife. Der Unterschied hier ist, dass wir nicht wissen ob wir einfach noch länger warten müssen bis wir (irgendwann) ein JA/NEIN bekommen oder wir tatsächlich in einer Endlosschleife sind.

Beispiel: Das Halteproblem (ob alle Paare (Turingmaschine, Eingabe)) für alle Eingaben und Turingmaschinen halten ist semi-entscheidbar/rekursiv aufzählbar, aber nicht entscheidbar/rekursiv. Denn für einige Eingaben kann eine Turingmaschine in eine Endlosschleife laufen und wir können nicht mit Sicherheit sagen ob sie nicht doch vielleicht irgendwann hält. Damit ist das Halteproblem eben nur rekursiv aufzählbar, denn wir können die Menge der Paare mit der Eigenschaft ja aufzählen.

Achtung: jede rekursiv aufzählbare/semi-entscheidbare Menge ist abzählbar. Aber nicht jede abzählbare Menge ist rekursiv aufzählbar/semi-entscheidbar. Z.B. ist die Menge der falschen Formeln einer PL1-Sprache (dazu in einem späteren Beitrag mehr) abzählbar, jedoch nicht entscheidbar/rekursiv aufzählbar. Ebenso ergeht es uns mit dem Busy Beaver Problem (auch hierzu folgt später ein Beitrag). Das Halteproblem, wie im Abschnitt vorher angegeben, ist ein Beispiel für die andere Richtung.

Abzählbarkeit: erstes und zweites Diagonalargument (Cantor)

Wir bezeichnen Mengen als abzählbar wenn diese die gleiche Mächtigkeit hat, wie $\mathbb{N}$. In dem Eintrag für die Cantorsche Tupelfunktion wir beschrieben, wie man prüft ob zwei Mengen gleichmächtig sind. Wir prüfen also den Fall $\left| M \right| = \left| \mathbb{N} \right|$? Um das zu tun müssen wir eine bijektive Abbildung $f: M \rightarrow \mathbb{N}$ aufzeigen, die jedem Element aus $M$ eindeutig ein Element aus $\mathbb{N}$ zuordnet. Durch die Bijektivität ist diese Funktion natürlich umkehrbar und wir können zu einem Element aus $\mathbb{N}$ wieder eindeutig ein Element aus $M$ zuordnen. Das nennt man das erste Diagonalisierungsargument von Cantor.

Wie in dem oben verlinkten Beitrag können wir z.B. eine bijektive Abbildung $f: \mathbb{Z} \rightarrow \mathbb{N}$ angeben und so zeigen, dass die ganzen Zahlen ($\mathbb{Z}$) genauso mächtig sind wie die natürlichen Zahlen ($\mathbb{N}$) obwohl die ganzen Zahlen gefühlt mehr Zahlen enthalten als die natürlichen Zahlen. Ebenso können wir durch diese Cantorsche Tupelfunktion $n$-Tupel aus $\mathbb{N}^n$, z.B. $(1,5)$ aus $\mathbb{N}^2$ auf eine einzige Zahl aus $\mathbb{N}$ abbilden. Das gleiche geht für Tripel usw. Damit ist bewiesen, dass der $n$-dimensionale Raum $\mathbb{N}^n$ gleichmächtig zu $\mathbb{N}$ ist, egal welches $n$ wir wählen.

Gibt es ein Beispiel für nicht abzählbare Mengen? Ja: die reellen Zahlen sind nicht gleichmächtig zu $\mathbb{N}$ und damit auch nicht abzählbar. Es gibt also keine bijektive Abbildung $f: \mathbb{R} \rightarrow \mathbb{N}$. Cantor bewies dies 2x. Sein letzter Beweis ist einfacher, deswegen möchte ich diesen hier kurz skizzieren: es ist sein zweites Diagonalisierungsargument.

Beispiel: zweites Diagonalisierungsargument von Cantor

Zunächst einmal sollten wir uns klar machen, was wir mit einer bijektiven Abbildung denn eigentlich machen. Eine bijektive Abbildung kann es nur zwischen zwei gleichmächtigen Mengen geben. Im vorherigen Beitrag hatten wir z.B. $M_1 = \{a,z,d\}$ und $M_2 = \{5,1,9\}$. Wir geben eine bijektive Abbildung für diese Mengen an: $f: M_1 \rightarrow M_2$ definiert durch $a=5, z=1, d=9$ (Umkehrabbilung $f^{-1}$ ist dann genau umgekehrt).

Wir wir sehen können wir zu einem Element aus $M_1$ eindeutig ein Element aus $M_2$ zuordnen und aufgrund der Eindeutigkeit geht es auch anders herum und wir bekommen ein eindutiges Element aus $M_1$ zu einem Element aus $M_2$. Damit sind die beiden Mengen gleichmächtig.

Eine bijektive Abbildung können wir auch für $\mathbb{Z}$ und $\mathbb{N}$ angeben und zeigen, dass diese Mengen ebenfalls gleichmächtig sind. Wir verwenden wieder das Beispiel aus dem Beitrag für die Cantorsche Tupelfunktion: $f:\mathbb{Z} \rightarrow \mathbb{N}$ definiert durch:

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

Die Umkehrabbildung ist:

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

Unsere Abbildung sieht nun für ein paar Zahlen so aus:

Wie wir sehen, sind auch diese Mengen gleichmächtig. Wir haben wieder eine eindeutige Zuordnung zwischen den Elementen aus $\mathbb{R}$ und $\mathbb{N}$. Probieren wir das gleiche doch für $\mathbb{N} \rightarrow \mathbb{R}$. Es reicht uns sogar einfach nur alle reellen Zahlen zwischen 0 und 1 anzuschauen (also: 0,72636..., 0,12238383...., ...). Für eine bijektive Abbildung müssen wir allen diesen Zahlen dann natürliche Zahlen zuordnen. Dazu basteln wir uns eine Matrix und eine willkürliche Abbildungsfunktion, die allen Zahlen aus $\mathbb{N}$ eine Zahl aus dem Intervall $(0,1)$ aus $\mathbb{R}$ zuordnet.

Wir weisen z.B. dem Definitionswert $0$ aus $N$ den Funktionswert $0,1574...$, dem Definitionswert $1$ die $0,0701...$ usw. zu. Mit $...$ haben wir angedeutet, dass die Matrix aus unendlich vielen Zeilen und die Dezimalbruchdarstellung aus unendlich vielen Nachkommastellen besteht. Lasst euch von den Kästchen nicht verwirren, $0,1574...$ ist ein Element, die Kästchen dienen nur dem, was wir gleich vor haben: wir zeigen jetzt mit dem Diagonalisierungsargument, dass die Matrix nie vollständig sein kann, dass es also einen Wert zwischen $0$ und $1$ aus $\mathbb{R}$ gibt, auf den wir nicht abbilden.

Wir führen einen Widerspruchsbeweis: nehmen wir an die Matrix sein vollständig und wir haben alle Zahlen aus $\mathbb{R}$ zwischen 0 und 1 in Dezimaldarstellung durchnumemriert. Wir basteln uns einen neuen Funktionswert, der von allen anderen Funktionswerten verschieden ist: wir verwenden die diagonalen Elemente der Matrix (grüne Markierung) und erhöhen oder erniedrigen sie um 1 ($<5$: neue Zahl wird erhöht, $\geq 5$: neue Zahl wird erniedrigt) und verwenden diese Zahlen als Nachkommastellen unseres neuen Eintrags. Damit ist sichergestellt, dass wir diesen Eintrag noch nicht als Funktionswert in unserer Matrix haben, denn die reelle Zahl in der $i$-ten Zeile unserer Matrix unterscheidet sich min. in der $i$-ten Stelle von unserer neuen Zahl (wir haben sie ja erniedrigt oder erhöht).

Damit ist $0,2658...$ unser neuer Eintrag, der definitiv noch nicht un unserer Matrix ist. Soweit so gut, nur wie wird er jetzt mit einer Zahl aus $\mathbb{N}$ nummeriert?! Wir sind doch von der Vollständigkeit unserer Matrix ausgegangen und haben damit doch alle unsere Elemente aus $\mathbb{N}$ ausgeschöpft, haben aber trotzdem ein neues aus $\mathbb{R}$, dass wir nummerrieren müssen! Also: Widerspruch! Damit sind $\mathbb{R}$ und $\mathbb{N}$ nicht gleich mächtig, $\mathbb{R}$ ist sogar deutlich größer, da wir ja nicht einmal das Intervall $(0,1)$ mit allen Elementen aus $\mathbb{N}$ nummerrieren konnten. $\mathbb{R}$ und $\mathbb{N}$ stehen also für zwei unterschiedliche Unendlichkeiten. Ein sehr cooler Beitrag auf youtube zeigt das nochmal in bewegten Bildern.

So schließt sich auch der Kreis zu den Funktionen: die Menge aller berechenbaren mehrstelligen Wortfunktionen ist ebenfalls abzählbar. Warum? Weil wir die Menge der mehrstelligen Wortfunktionen in einstellige Wortfunktionen überführen können, diese durch die Standardnummerierung in einstellige Zahlenfunktionen überführt wird und wir diese anschließend durchnummerieren können.