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

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.

Datum: 3. Dezember 2012
Kategorie: Theoretische Informatik
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url

Sie können zum Ende springen und ein Kommentar hinterlassen. Pingen ist im Augenblick nicht erlaubt.