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:

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()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.


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


 

3 Kommentare zu “TIA: utm-Theorem (Lernziele KE5 2/3, Update 2)”

  1. Frank Diederichsen
    Dezember 25th, 2013 13:56
    1

    Hallo,
    "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"
    Mensch, da kennt tatsächlich noch jemand RPG, Respekt!

    Mit freundlichen Grüßen

  2. Steve
    Juli 7th, 2014 00:25
    2

    Hallo Anton,

    vielen Dank, dass du dein Blog weiter pflegst.

    Ein paar Kleinigkeiten zum Lernziel 4 + Beispiel:
    (1^2:1,,1)(:1,1,1^2)(:B,,) (2x) ist das Programm aus Aufgabe 7.1.2,
    gemeint ist wahrscheinlich w1 = (: R, 1)(1 : B, 11, ) aus Aufgabe 7.1.7.

    "zählen unser t ab _1_" und "Führe h(n1,3,1) aus und ..."
    Im Skript beginnt die Registermaschine mit R3=0, also t=0 (Beweis zu Satz 7.2.2).

    Und weiter unten: h(2,3,2) statt h(n1,3,2) bzw. h(n1,3,1)

    Viele Grüße
    Steve

  3. Anton
    Juli 9th, 2014 15:16
    3

    Hallo Steve,

    ich habe jetzt nur drüber gelinst. Aber es scheint okay zu sein. Ich habe ja extra etwas andere Benamungen genommen, als im Skript, damit es verständlicher ist. Aber ich schaue in einer ruhigen Minute nochmal genauer hin.

    In jedem Fall, danke für den Kommentar.

Beitrag kommentieren