Kategorie: Theoretische Informatik

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.
Done!