Der Plan für heute ist, dass wir noch ein letztes Faktum über Reduktionen von Touring-Maschinen

nachschieben, was wir letztes Mal in den letzten fünf Minuten leider nicht mehr geschafft haben.

Und anschließend so ein paar grundlegende Dinge über Touring-Maschinen ansehen, insbesondere

die universelle Touring-Maschine und Unentscheidbarkeit. Und so als Bonbon beweisen

wir am Ende in der letzten Viertelstunde den ersten Gödlchen-Unvollständigkeitssatz.

Ich mache mal jetzt ohne Überschrift weiter in meiner Serie von Fakten. Also das hier hätte

eigentlich der Schlusspunkt der letzten Stunde sein sollen, das haben wir jetzt nicht geschafft.

Also wir hatten uns, um da mal kurz wieder in Stimmung zu kommen, angesehen leichte Varianten

der Definition einer Touring-Maschine. Was sind Varianten? Gut, was für ein Alphabet hat die?

Wie viele Bänder hat die? Dergleichen mehr. Wir haben gesehen, dass das also alles im Wesentlichen

bis auf polynomialen Veränderungen der Laufzeit keine Rolle spielt. So auch hier in diesem letzten

Fall, wo es geht um beidseitige Unendlichkeit. Also. Kein Fakt drei? Achso, dann hatte ich vergessen,

die Nummer zu vergeben. Das mit den Oblivious Touring-Maschinen, das war Fakt drei. Kann sein,

dass ich vergessen hatte, die Nummer dran zu schreiben. Also zur Orientierung, Fakt eins war

Alphabetreduktion, Fakt zwei war Reduktion der Bandanzahl, Fakt drei war mehr oder weniger ein

Korrelar dazu. Das war also die Annahme, dass wir eine Touring-Maschine haben, die Oblivious ist,

das heißt, bei der die Kopfposition zu einem gegebenen Zeitpunkt immer nur abhängt von der

Länge des Inputs und nicht vom tatsächlichen Input. Und Fakt vier ist das, was jetzt kommt.

So, da kommt jetzt ein Begriff vor, den haben wir gar nicht eingeführt, der einer Touring-Maschine

mit beidseitig unendlichen Bändern, das führe ich hier so on the fly ein, also es müsste klar sein,

was eine Touring-Maschine mit beidseitig unendlichen Bändern ist. Wir hatten angenommen,

bisher Touring-Maschinen haben Bänder, die irgendwo anfangen, genauso gut kann ich natürlich

unterstellen, dass das Band nach links beliebig lange weitergeht. Und wenn ich das unterstelle,

ist natürlich die Frage, kann ich auf so einer Touring-Maschine, wo ich nach links das Band

beliebig lange weiterlaufen lasse, womöglich mehr oder schneller berechnen als auf einer Touring-Maschine,

wie wir sie eigentlich eingeführt haben? Die Antwort lautet natürlich nein.

Wir behaupten also, wenn das der Fall ist, dann ist F berechenbar auf einer Touring-Maschine. Ich

sage nicht dazu, dass sie dann links abbrechende Bänder hat, denn das sagt ja unsere Definition

von Touring-Maschine, dass das so ist. Also hier habe ich die Zeit vergessen. Also hier in Zeit t von n,

also auf der beidseitig unendlichen Maschine, dann haben wir es auf einer normalen Touring-Maschine,

in Zeit o von t von n. Also wir sind schon langsamer, aber wir sind nur einen konstanten

Faktor langsamer. Ja, die Idee ist, wie immer reißen wir sie nur kurz an. So, die Idee, die man da hat,

ist die, dass, naja gut, ich habe also jetzt einen Band, mir fehlt praktisch die Hälfte des Bandes.

Also wenn ich irgendwie sage, gut das Band hat eine Mitte, dann habe ich gegeben eine Touring-Maschine,

wo sich das Band in beide Richtungen erstreckt und ich muss das podieren auf einer Touring-Maschine,

wo das Band nur in einer Richtung geht. Aber erstmal, ich klappe das rüber. Also die Idee ist,

dass das Band zu falten in der Mitte. Wie sieht das dann aus? Das sieht so aus. Gut, ich habe hier

meine Nullposition, an der Stelle falte ich, gut da bleibt es also wie es ist. Und dann klappe ich

also hier die linke Seite rüber, das heißt, ich habe hier meine Position minus eins, minus zwei,

minus drei und so weiter. Die habe ich da rüber gefaltet, über meine Position, die ich vorher hatte,

eins, zwei, drei und vier und so weiter. Na ja, dann habe ich nur das Problem, dass ich ja jetzt

plötzlich hier an jede Stelle zwei Symbole schreiben muss, weil ich ja die linke Seite

rüber gefaltet habe und das jetzt hier alles aufeinander liegt. Na ja, gut, das heißt,

ich vergrößere das Alphabet. Das Alphabet ist jetzt also nicht mehr Gamma, also wenn es vorher

Gamma war, sondern jetzt Gamma quadrat, also sprich, das ein einzelnes Alphabet-Symbol besteht jetzt

aus zwei alten Symbolen. Na ja, sodass ich dann also hier jeweils zwei Symbole an jede Bandstelle

schreiben kann. Ja, und das war es schon. Wir haben gesehen, dass wir das Alphabet vergrößern können.

Und ja, das ist schon die ganze Geschichte. Gut, wir müssen so ein bisschen aufpassen mit dem

Bewegen des Kopfes, was aber nicht schwierig ist, weil wir im Gegenteil, wir können sogar,

wenn wir ganz schlau sind, hier schneller werden, weil wir vorher mit dem Kopf mühsam von 4 nach