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 Nummerdas 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
..."
für die einstelligen berechenbaren Zahlenfunktionen ..."
Seite 122: "Modellprogrammiersprache
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