TIA: Standardnummerierung und -Komplexität Phi und das Phi-Theorem (Lernziele KE5, 1/3, Update 7)
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 sowie dem utm- und smn-Theorem noch etwas zu verdeutlichen.
Update: Fehler beseitigt.
Update: ein paar Details zur Standardnummerierung 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 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:
Wir starten im ersten Teil direkt mit dem ersten Lernziel: der Standardnummerierung für
Lernziel 1
Erläuterung der Definition der Standardnummerierung von
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 und einer anderen Menge. Im letzten Beitrag haben wir alle Worte über dem Alphabet , nämlich standard-nummeriert. In diesem Beitrag kümmern wir uns um die einstelligen, berechenbaren Zahlenfunktionen .
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 keinen Bestand hat.
Im Skript ist die Menge der normierten Bandmaschinen mit dem Alphabet . 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 zu einem Bandprogramm kommen. Von diesem ausgehend kommen wir mit auf eine normierte Bandmaschine (bzw. das Flussdiagramm aus diesem). Anschließend können wir diese mit in eine einstellige, berechenbare Funktion aus abbilden und haben zum Schluss über mehrere Wege also eine Nummerierung der einstelligen, berechenbaren Funktion erreicht. Aber mal langsam.
Die Nummerierung besteht im Skript aus vier Komponenten:
- Ordnungsfunktion für das Alphabet , so dass wir mit die Standardnummerierung aller Worte aus , d.h. von haben. Also nicht nur Programme, sondern auch Kauderwelsch wie z.B. .
- , z.B. als die Nummerierung des Bandprogramms . Es ist definiert durch:
Wir bekommen damit zur Nummer das zugehörige Bandprogramm wenn es tatsächlich ein Bandprogramm ist. Oder einfach nur eine Endlosschleife wenn die Nummer zu irgendwelchem Kauderwelsch gehört, denn mit haben wir (siehe oben) alle Worte über , d.h. auch Unsinn, nummeriert.- , damit bekommen wir zum Wort aus die zugehörige Bandmaschine (dazu gleich mehr)
- Funktion mit . ist also die Funktion aus , welche die Funktion der Bandmaschine berechnet.
Damit kann die Standardnummerierung als eine Komposition zwischen definiert werden.
Das Problem ist nun, dass diese Standardnummerierung nicht bijektiv ist, wie die Standardnummerierung ! Das liegt an der Surjektivität der verwendeten Funktionen, u.a. . Denn zu einer Funktion aus kann es durchaus mehrere Bandmaschinen aus 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 ist ja total: wir erwischen durch die Definition von tatsächlich nur richtige Bandprogramme. Und zwar alle.
Und zu einem Bandprogramm bekommen wir die zugehörige Bandmaschine mit . Der Definitionsberech der Funktion ist durch die Totalität von die komplette Menge .
Die Komposition aus ist damit auch total. Und weil auch total ist (wir haben zu allen Funktionen aus min. eine Bandmaschine, die sie berechnet), ist die Komposition 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 , welches unsere Zeichen
beinhaltet. Achtung ist unser Trennzeichen, da das Komma zum Alphabet gehört.
Aus diesen Zeichen kann ein Bandbefehl unseres Programms bestehen, welches die Form
mit oder
mit
hat. Das kennt Ihr alles schon von den Turingmaschinen. Der erste Befehl der Marke schreibt entweder ein , eine auf das Band oder geht nach inks oder echts und springt anschließend in die Marke .
Der zweite Befehl ist eine Verzweigung: in der Marke wird geprüft ob unter dem Lesekopf aktuell ein oder eine steht. Ist das der Fall, wird in die Marke verzweigt und ansonsten in die Marke gesprungen.
An den Beispiel weiter unten wird es gleich deutlicher.
Ein Bandbefehl aus der Menge ist damit ein Wort über , d.h. . Ein Bandprogramm aus der Menge ist eine Folge von Bandbefehlen (es kann auch nur eines seit) und ist damit auch nur eine Kombination aus Worten über :
Kommen wir nun zu unserer Funktion, die uns zu einem Bandprogramm aus eine Bandmaschine aus gibt, die die gleiche Funktion berechnet:
Die Maschine , die das Bandprogramm , welches aus einer Folge von Bandbefehlen aus der Menge besteht, berechnet, wird durch ein Flussdiagramm beschrieben. Damit gilt:
D.h. mit der Funktion bekommen wir zum Bandprogramm die passende Maschine
Wir haben noch die Definition von im Kopf? Nein? Macht nichts: .
: ist die Menge unserer Marken, d.h. die Beschriftung der Befehle und Verzweigungen (Rechtecke und Rauten) im Flussdiagramm.
: ist unser Arbeitsalphabet. Wir beschränken uns im Skript auf , da sie die einzigen Zeichen sind, die wir benötigen (Satz über Hilfssymbole!)
: die auszuführenden Aktionen für die Marken. Ist z.B. eine Marke, so ist der auszuführende Befehl.
: unsere Startmarke. Diese ist der Definition nach das erste Element aus , 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 bekommen wir
und für gibt es ein
Was mich zunächst aus dem Konzept gebracht hat, sind Befehle und Übertragung dieser in ein Flussdiagramm in folgender Form: , doppelte Zuweisungen zu einer Marke und -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 mehrere Befehle gibt, so zählt nur der erste von links.
2. Kommt irgendwo eine Zahl/Marke vor und beginnt kein Befehl mit , so ist es der HALT-Befehl.
Beispiel: aus dem Skript
Was müssen wir hier also zunächst tun? Wir schreiben uns alle Marken raus, die wir finden: 2 (aus ), 0 (aus ) und 1 (aus ). Nun schauen wir uns die Definitionen unserer Marken 0,1 und 2 an.
- Marke 0: . Bedeutet: wenn , gehe zu Marke , ansonsten zu Marke . wird ignoriert, da doppelte Zuweisung.
- Marke 1: . Es wird auf die Marke in Marke und verwiesen, aber es gibt keinen Befehl dafür. Also ist es unsere -Marke.
- Marke 2: . Bedeutet: wenn , gehe zu Marke , ansonsten zu Marke . 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 aufmalen (versucht es mal selbst und prüft eure Lösung mit dem Spoiler-Ausklapp-Text unten) und habt damit euer .
Und nun tun wir das wozu wir hier sind: wir definieren wir die Standardnummerierung dem Skript nach.
- Ordnungsfunktion , welche die Zeichen (siehe oben) unserer Programmiersprache nummeriert. , , usw. Mit wird dann die Standardnummerierung von bezeichnet, denn 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.
- Mit haben wir eine Funktion, die uns zu einer Zahl das zugehörige Bandprogramm aus (bzw. eine Kombination aus den oben definierten Zeichen) zurückgibt: nämlich (aber nur wenn es ein echtes Bandprogramm ist, welche wiederum aus Bandbefehlen der Menge besteht. Es könnte aber auch irgendwelches Kauderwelsch sein, was nicht ausführbar ist).
Wenn es also Kauderwelsch ist, wird ein . zurückgegeben, d.h. eine Endlosschleife. Damit ist nur surjektiv, da man einige Nummern mit durchaus mehrfach auf abbildet wenn sie nicht Nummern von legitimen Bandprogrammen sind.- , damit bekommen wir zum Wort aus (von wem wir durch sicher wissen, dass es sich um ein Bandprogramm handelt), die zugehörige Bandmaschine
- Durch mit haben wir die von der Bandmaschine berechnete Funktion aus . Zudem: . Bei den beispiel gleich wird es deutlicher.
- Als letztes definieren wir durch: . Auch hier hilft zum besseren Verständnis das Ausklammern: .
Punkt 4 baut auf der ganzen Vorarbeit auf und standard-nummeriert uns schlussendlich unsere einstelligen, berechenbaren Funktionen aus . Und nicht vergessen: die Standardnummerierung von 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:
Die Nummer des Bandprogramms ist in der Aufgabenstellung . Das ist relativ willkürlich gewählt uns ist uns auch ziemlich egal. Wir könnten durch die ordnungsfunktion 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 nutzen wir die Funktion aus der Definition und haben so auch unsere Nummerierung von allen Worten über dem Alphabet , nämlich .
2. Nun brauchen wir . Da unser Wort korrekt ist und aus kommt, bekommen wir das zurück (siehe Definition):
.
Wäre nicht in , so hätten wir nur ein bekommen. Daraus basteln wir uns nun ein wunderschönes Flussdiagramm. Auch hier: alleine versuchen, dann Lösung öffnen.
Was macht das schöne Stück? Nehmen wir an wir geben in die Maschine und starten bei Marke . Der Lesekopf ist anfangs ja auf dem letzten (Blank) vor dem Eingabewort. Wir gehen nun nach rechts (Marke ) auf die erste auf dem Band. Dann sind wir bei Marke und prüfen ob unter dem Lesekopf ein (Blank) steht. Tut er das, gehen wir zu Marke und halten. Befindet sich jedoch eine unter dem Lesekopf, gehen wir wieder zu Marke 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 unserer Maschine ist somit: . Zur Auffrischung. Das ist einfach nur die Anzahl der Einsen. Wir geben also Einsen auf das Band und am Ende steht der Lesekopf auf Position und wir haben als Ausgabe links vom Lesekopf also Einsen auf dem Band. Sprechen wir von "normalen" Funktionen, die dezimal () und nicht unär () definiert sind, wäre das .
Nun brauchen wir noch unser (ich erkläre die Berechnung weiter unten um die Übersichtlichkeit nicht zu killen):
Fertig!
Wir haben es also geschafft mit die Funktionen aus zu nummerieren. Geben wir also die dezimale Nummer der Maschine und einen dezimalen Parameter aus mit, bekommen wir als Ausgabe auch einen dezimalen Ausgabewert zurück, obwohl die Maschine, die diesen Wert berechnet nur mit der unären Darstellung arbeitet. Wir verkürzen das in den Merksatz:
ist die von der Bandmaschine berechnete Funktion aus , der Menge der einstelligen partiell-rekursiven Funktionen.
Hier die Erklärung der Berechnung von oben (Danke an Carsten für den letzten Hinweis).
: nur schöner umgeschrieben, einfach der Definition nach
: der Definition nach ist . Ich habe hier nur ausgeklammert. Und da wir mit einem Parameter füttern, hängt er eben mit hinten dran.
: war ja die willkürliche Nummer unserer Maschine. ist demnach unser Wort für die Maschine (siehe Definition von ).
: ist also unsere Maschine mit dem Flussdiagramm, welche unsere Funktion berechnet. Die von der Maschine berechnete Funktion nennen wir ja immer .
: ist unserer Definition nach ja eben . Da wir ja immernoch den Parameter mitschleppen, hängt er weiterhin einfach nur mit.
: Jetzt wird es lustig. In der Definition steht, dass ist. D.h. einfach die Anzahl von Einsen. wäre z.B. . Das dient uns als Eingabe für unsere Funktion . Die Bandmaschinen werden ja mit der unären Darstellung von Dezimalzahlen gefüttert. Daher brauchen wir hierfür um eine Dezimalzahl in ihre unäre Darstellung umzuwandeln damit wir unsere Maschine damit bedienen können.
: Was macht unsere Funktion wenn man sie mit der Eingabe startet? Genau: sie gibt uns als Ausgabe auch wieder zurück.
: Und ist die Inverse zu und macht genau das umgekehrte. Es bekommt als Parameter die unäre Darstellung der Zahl als Parameter und gibt uns die dezimale Darstellung zurück.
Damit haben wir auch die Standardnummerierung der einstelligen, berechenbaren Funktionen abgehakt.
Ich gehe in diesem Abschnitt jetzt nicht strikt den Lernzielen, da zu dieser Aufgabe auch noch die Standardkomplexität 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 der einstelligen, berechenbaren Funktionen besteht aus den Komponenten:
- Ordnungsfunktion mit für die geordnete Nummerierung des Alphabets
- . Durch die Ordnungsfunktion induzierte Standardnummerierung von von .
- . Funktion um zu einer Nummer das zugehörige Bandprogramm zu bekommen wenn tatsächlich ein Bandprogramm ist
- . Funktion um zur einem Bandprogramm die zugehörige Bandmaschine zu bekommen.
- . Funktion um zu einer Maschine die zugehörige Funktion zu erhalten.
Dadurch ist es möglich, ausgehend von einer Zahl eine Funktion aus zu erhalten:
Lernziel 2
Erläuterung des -Theorems
Wir starten zunächst mit der Definition der Standardkomplexität selbst:
heißt Standardkomplexität zu und ist definiert durch:
ist die Anfangsmarke, die Schrittzahlfunktion der Bandmaschine .
Was haben wir hier?
Im Endeffekt bekommen wir mit also einfach nur die Anzahl der Schritte, die die Maschine braucht um für eine Eingabe , ausgehend von Marke und der Bandbelegung (unter dem Lesekopf steht das Blank vor der Eingabe, einer unären Darstellung von ) die Berechnung durchzuführen und schließlich auf stehen zu bleiben (oder eben nicht). Dafür brauchen wir die Schrittzahlfunktion , die wir bereits kennen.
schreckt euch doch nach dem Abschnitt zur Standardnummerierung von 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 zu hat zudem drei schöne Eigenschaften:
1. Die Funktion zur Standardkomplexität einer Maschine gehört zu den einstelligen, berechenbaren Funktionen .
Ist auch klar, denn es ist die Rechenzeitfunktion der -ten Bandmaschine.
2. Der Definitionsbereich von ist gleich dem Definitionsbereich von . Beide Funktionen verwenden den selben Parameter aus für ihre Eingabe.
Während uns das Ergebnis aus seinem Bildbereich liefert, bekommen wir mit die zur Berechnung von notwendige Schrittanzahl .
Dass sein kann (mit etwas Zufall ist die Anzahl der Schritte gleich dem Ergebnis, aber das ist dann auch nur Zufall), für das gleiche , ist auch klar. Aber es bleibt das gleiche , daher ist
.
3. Die Menge 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 ist:
Was bedeutet das?
Ganz einfach: wir bekommen mit der Funktion eine zurück wenn die Maschine bei der Eingabe von nicht mehr als Rechenschritte bis zur -Marke braucht. Braucht sie mehr, so bekommen wir eine zurück.
Als Beweis benutzen wir wieder eine Funktion, die unserem (Erläuterung von ist im nächsten Lernziel) sehr ähnlich ist.
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 ?
1. ist ja die kleinste Zahl , bei der gilt, da uns ja die Anzahl der Schritte liefert, die die Maschine braucht um bei der Eingabe zum Ende der Berechnung zu kommen.
2. gibt es nur wenn es die Schrittzahlfunktion und auch die Ausgabe gibt. Ansonsten wäre sie nicht vorhanden: keine Ausgabe, keine Schritte, keine Standardkomplexität .
3. Da berechenbar ist (weisen wir gleich nach), auch Kompositionen aus den Funktionen berechenbar sind, so ist auch unsere charakteristische Funktion berechenbar.
Was sollte klar sein, ich schreibe es trotzdem mal auf:
Wir bekommen mit der Funktion den kleinsten Wert aus der Auswahl von zwei Werten. Und wir haben die Auswahl zwischen und dem Funktionswert von .
Unser gibt aber nur den Funktionswert zurück wenn die Maschine die Berechnung mit maximal Rechenschritten abschließt, denn ist die Anzahl der Schritte, die wir maximal rechnen dürfen. Ansonsten gibt es nur den Zonk, ähm, ich meine die . In diesem Fall hat die Maschine bereits Schritte gerechnet und ist noch nicht bei der -Marke angekommen, d.h. die Berechnung ist nach Schritten noch nicht zu Ende.
Wir haben daher immer wenn oder wenn . Passt.
Damit ist gewiesen, dass die Menge tatsächlich rekursiv/entscheidbar ist, denn wir können entscheiden ob Maschine bei der Eingabe von nach Schritten hält oder nicht.
Naja, streng genommen müssen wir dazu noch als berechenbar nachweisen, aber das tun wir ja gleich im 3. Lernziel.
Und was ist mit der
Beispielaufgabe zu 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. , d.h. drei Einsen um bis zur -Marke zu gelangen und wie sieht die Ausgabe dann aus? Spielt das Flussdiagramm einfach mal damit durch und Ihr werden feststellen, dass Ihr genau Schritte braucht.
Bei der Eingabekonfiguration von kommen wir nach Schritten dann bei der Endkonfiguration an. Wenn man das Flussdiagramm nun genauer betrachtet kommt man drauf, dass man bis zur Endkonfiguration genau Schritte passiert hat. Bei der Eingabe von Einsen muss man die Schleife Mal passieren und führt so am Ende Schritte durch, was uns zu unserer Übergangsrelation führt:
Und da nun genau die Anzahl der Schritte ist bis die Maschine bei der Eingabe von erreicht, ist
Damit ist die Standardkomplexität zu bei der Eingabe von genau . Würde die Maschine nicht halten, so wäre .
Hiermit ist die Standardnummerierung für abgehakt und wir kümmern uns jetzt um den Beweis von .
Antwort zum Lernziel: das -Theorem besagt drei Dinge:
- dass die Schrittzahlfunktion der Maschine zu den einstelligen, berechenbaren Funktionen gehört
- der Definitionsbereich von ist gleich dem Definitionsbereich von , da beide Funktionen den selben Eingabeparameter benötigen
- und die Menge rekursiv/entscheidbar ist, da die charakteristische Funktion berechenbar ist.
Mit dieser Standardkomplexität können wir bestimmen wie viele Berechnungsschritte die Maschine bei der Eingabe von benötigt () oder feststellen ob die Maschine bei der Eingabe von nach Berechnungsschritten hält oder nicht () um die Menge zu entscheiden.
Lernziel 3
Beweis der Berechenbarkeit von
Für die Formalisierung des utm-Theorems brauchen wir diese hilfreiche Funktion auch, also aufpassen! Definieren wir zunäüchst:
mit
Okay, dreistellige Funktion auf den natürlichen Zahlen, die ein einstelliges Ergebnis ausgibt. Wir bekommen eine und das Ergebnis der Maschine bei der Eingabe von wenn die Standardkomplexität existiert und kleiner/gleich ist, d.h. wir kommen zum Ergebnis (-Marke noch bevor wir Rechenschritte absolviert haben). Ansonsten gibt es nur eine Null zurück. Fair.
Um zu beweisen, dass die Funktion berechenbar ist wird wie folgt vorgegangen:
Wir zeigen, dass die Wortfunktion zu berechenbar ist. Anhand der Standardnummerierung können wir ja Worte in Zahlen und Zahlen in Worte codieren. Unsere Wortfunktion wäre damit: .
Schaut euch die Standardnummerierung noch einmal an, falls euch das nicht mehr viel sagt. Anschließend basteln wir uns eine Turing-Maschine mit . Diese Funktion sieht dann so aus:
Führen wir uns einfach mal vor Augen, dass die Turing-Maschine nur Eingaben in Form von , also Mal die entgegen nimmt und auch wieder ausgibt. Für die Funktion wandeln wir unsere und daher einfach in die entsprechende Anzahl ein Einsen um (unäre Darstellung einer Dezimalzahl).
Während wir bei der Funktion als Ergebnis dann den dezimalen Ausgabewert, also bekommen hätten, bekommen wir hier einfach die dazu entsprechende Anzahl von Einsen (); die unäre Darstellung des Ergebnisses. Das der Ausgabewert jedoch nicht in unserem vorher definierten Alphabet für die Maschine ist, nutzen wir das leere Wort zur Codierung von .
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:
mit der zugehörigen Nummer , der willkürlichen Eingabe und den maximal durchzuführenden Rechenschritten .
Ein Ergebnis sollten wir auch herausbekommen, da wir aus dem letzten Beitrag ja wissen, dass die Standardkomplexität der Funktion ja und bekanntlich ist ist. Unser sieht mit der willkürlichen Wahl der Eingangsparameter nun so aus:
Wir haben folgende Teil-Flussdiagramme mit den entsprechenden Aufgaben:
- : Transformiert die Eingabe auf die einzelnen Bänder (siehe unten).
- : Kopiert die Anfangsmarke auf Band .
- : Sucht auf Band nach dem Befehl mit der Marke von Band . Wird keine passende Marke auf Band gefunden, so muss es eine -Marke sein.
- : Simuliert den gefundenen Befehl von Band auf dem Band , wo unser Eingabewort steht.
- : Testet ob weitergerechnet werden darf, d.h. ob noch Einsen auf Band stehen.
- : Subtrahiert eine Eins von Band bei jedem simulierten Rechenschritt von .
- : Kopiert vom Arbeits- und Eingabeband am Ende alle Einsen auf Band und erzeugt uns so auf dem gewünschten Band eine Ausgabe.
Wir transformieren die Eingabecodierung und setzen jeden der drei Parameter als ein Eingabewort aus Einsen auf ein eigenes Band. Was jedoch mit gemacht wird, ist etwas spannender: Aus wird , unser Bandprogramm aus (zur Auffrischung: siehe Lernziel 1), welches nun auf Band unserer Maschine steht.
Auf Band (Eingabeband) steht die Eingabe (). Auf diesem Band werden die einzelnen Berechnungsschritte von Band (dem Programmband) simuliert. Band (Schrittzahlband) ist der Schrittzähler mit , wo bei jedem Schritt von eine gelöscht wird. Auf Band (Markenband) wird die aktuelle Marke gespeichert. Unsere Bänder sehen nun so aus:
Das hat unser Teil-Flussdiagramm gemacht. Nun kommt und kopiert die Anfangsmarke nach Band 4:
Nun sucht Teil-Flussdiagramm auf Band , wo unser Programm gespeichert ist das erste Teilwort, wo die gespeicherte Marke von Band vorkommt. Wenn es einen passenden Befehl findet, führt Teil-Flussdiagramm den Befehl auf Band 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 -Marke).
Da die Marke von gefunden wird, wird der Befehl auf Band von Teil-Flussdiagramm ausgeführt. Wenn er die Form hat, wird die Bandoperation auf Band ausgeführt und die gespeicherte Marke auf Band mit der Folgemarke ersetzt. Hat der Befehl die Form , so testet ob unter dem Kopf steht und ersetzt die Marke auf Band entsprechend dem Ergebnis durch (nein, steht nicht unter dem Lesekopf) oder (ja, steht unter dem Lesekopf). Das Teil-Flussdiagramm prüft ob auf dem Zählerband noch Einsen stehen, d.h. ob weitergerechnet werden kann.
In unserem Fall sehen unsere Bänder anschließend so aus, da der Befehl auf Band gefunden und ausgeführt wurde. Auch ist eine auf Band unter dem Lesekopf, so dass wir nicht in die Marke , sondern in die "leere" Folgemarke springen werden und diese Folgemarke auf unser Folgemarkenband schreiben. Auch haben wir eine von unserem Zählerband, Band mit dem Teil-Flussdiagramm gelöscht.
Da noch Einsen auf dem Zählerband stehen ( hat das geprüft), dürfen wir weiterrechnen. Nun wird nach der "leeren" Marke auf Band gesucht, diese auf Band durch ausgeführt, wieder eine vom Zählerband durch gelöscht, die Folgemarke auf Band durch geschrieben, diese wieder auf Band durch 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 - es ist also eine Endmarke) hat. Dann geht es von zu , welches die Ausgabe von Band auf Band kopiert. Wäre es keine Endmarke, würde von 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 zur Ausgabe zu addieren und den Lesekopf rechts von der Ausgabe zu positionieren werden am Ende noch die Befehle und ausgeführt. Am Ende sehen unsere Bänder wie folgt aus:
Die gesuchte Ausgabe steht auf dem Ausgabeband .
Damit haben wir die Berechenbarkeit der Funktion bewiesen. Und damit wir die ganze Arbeit nicht umsonst gemacht haben, nutzen wir gleich für das smn- un das utm-Theorem.
Antwort zum Lernziel: Um die charakteristische Funktion für das -Theorem zu berechnen, ist es notwendig die Maschine mit der Nummer auf einer (sog. universellen) Turingmaschine zu simulieren.
Dazu wird das zu simulierende Bandprogramm , die Eingabe , die maximale Anzahl der Schritte auf jeweils ein Band der neuen Maschine geschrieben und die einzelnen Befehle des Bandprogramms auf dem Eingabeband, wo steht simuliert. Bei jedem Berechnungsschritt wird 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 auf dem Schrittzahlband zu geworden ist, war die Berechnung erfolgreich und es ist . Ist auf dem Schrittzahlband jedoch bereits , so wird die Berechnung abgebrochen und es gilt . Damit braucht die Maschine bei der Eingabe von mehr Berechnungsschritte als um zur Endmarke zu gelangen.
Diese Funktion ist nicht nur für das -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.
Februar 13th, 2013 01:47
Was genau ist denn P(1)?
Das steht auf ein Mal im Script, anschließend wird darüber diskutiert aber nirgendwo steht was P(1) eigentlich ist.
Februar 13th, 2013 09:20
Was ist, steht in einem Nebensatz in KE5.
Seite 121: "... sei die Menge aller WHILE-Programme ... zu jedem WHILE-Programm ..."
Seite 122: "Modellprogrammiersprache für die einstelligen berechenbaren Zahlenfunktionen ..."
Da doch recht häufig benutzt wird, wäre eine explizitere Erwähnung im Skript wahrscheinlich wirklich sinnig gewesen 😉
März 16th, 2013 15:13
Hallo,
ich bin auch über P(1) gefallen. Ist P(1) nun also die Menge aller einstelligen berechenbaren Zahlenfunktionen?
Ich habe offenbar eine andere Version als ihr. Meine ist von 10/07 und da steht zum Beispiel gar nichts von der Definition zur Modellprogrammiersprache.
Ich habe irgendwo gelesen, dass diese Menge P(1) abzählbar unendlich ist, also die gleiche Mächtigkeit wie die natürlichen Zahlen haben. Ist das so?
Ich danke euch schon mal,
Marco
Juli 1st, 2013 08:53
Hallo Marco,
sorry für die späte Antwort. Ja, das ist der Fall.
In Kurseinheit 4 (http://fernuni.digreb.net/?p=837) wurden diese das erste Mal angesprochen. In dieser Kurseinheit haben wir die Menge mit "standard-nummeriert".
Eine *Standard*-Nummerierung hat im Gegensatz zu einer normalen Nummerierung die Eigenschaft der Bijektivität, die einfache Nummerierung muss nur surjektiv sein. Eine bijektive Abbildung zwischen zwei Mengen bedeutet, dass diese die gleiche Mächtigkeit haben. Haben wir das Glück und ist eine Menge davon die natürlichen Zahlen, so ist die andere Menge gleichmächtig dazu. Und da die natürlichen Zahlen abzählbar unendlich sind, ist es die andere Menge ebenfalls.
Gruß
Anton
August 9th, 2013 13:15
P^(k) wird in KE2 in Definition 4.3.1 eingeführt, bzw. definiert. Gleich zusammen mit R^(k), P, R.
Ist mir gerade bei der Vorbereitung für die mündliche Prüfung aufgefallen.
Großes Lob an die Seite!
Gruß Philipp
Oktober 17th, 2013 11:00
Hi,
die Seite scheint irgendwie "zerschossen" zu sein, jedenfalls werden bei mir im Gegensatz zu allen anderen Seiten die Mathe-Symbole nicht richtig an den Stellen dargestellt, sondern sind durch die gesamte Seite verteilt.
Die JavaScript-Console wirft hier ebenfalls einen Fehler: "Uncaught TypeError: Cannot read property 'preProcess' of undefined".
Magst du mal schauen, ob du das gefixt bekommst?
Oktober 17th, 2013 11:36
Ich habe keine Probleme, schau mal mit einem anderen Browser 😉
Juli 4th, 2014 13:14
Standardkomplexität
Die Formulierung "Ist auch klar, denn es ist die Schrittzahlfunktion einer Maschine i." ist etwas ungenau.
Phi_i ist die _Rechenzeitfunktion_ der i-ten Bandmaschine (Phi_i :subseteq N -> N) und nicht die Schrittzahlfunktion (SZ :subseteq KON -> N).
(Absatz oberhalb von Def. 7.1.6, S. 126)
Juli 9th, 2014 15:21
Bedankt! Ist gefixt.
September 10th, 2015 08:15
Hallo Anton,
kleiner Tippfehler bei Lernziel 3:
"Auf Band 2 (Eingabeband) steht die Eingabe 1^{n_1}. Auf diesem Band werden die einzelnen Berechnungsschritte von Band 1 (dem Programmband) simuliert."
Auf Band 2 steht die Eingabe 1^n mit n=3, also 1^3. Mit n_1 hattest du die Nummer eines Bandprogramms BP definiert.
Gruß,
Marcel