Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
HALTEPROBLEM. TURINGMASCHINEN. UNVOLLSTÄNDIGKEITSSATZ. Theoretische Informatik erklärt (2025)
Das Wichtigste aus dem Video
Transkriptautomatisch erstellt · 69 Zeilen
- Willkommen zu unserem Video rund ums Halteproblem, dessen Herleitung und weitreichenden Konsequenzen. Falls ihr Begriffe wie Automatentheorie,
- Touringmaschine oder Berechenbarkeit schon etwas sagen, etwa aus dem Studium, dann hoffen wir eine Übersicht zu bieten, um dein Wissen aufzufrischen und
- den Zusammenhang zu festigen. Doch keine Angst, auch wenn das alles nur nach Fachchinesisch klingt, wollen wir dir einen netten Einblick in die
- wunderbare Welt der theoretischen Informatik bieten. In jedem Fall ist dieses Video lediglich als anschauliche Übersicht konzipiert.
- Die ausführliche formale Behandlung dieser Themen kann nämlich mehrere Monate an Vorlesungen beanspruchen. Beginnen wir mit einem sogenannten
- Automaten. Einem Automaten, den wir alle kennen, dem Kaffeeautomaten. Der hier heißt scheinbar Karel. Doch woher weiß Karl, wie er sich
- verhalten soll? Wir erwarten ja schließlich, dass etwas passiert, wenn wir einen Knopf drücken. Nun, das hängt von Karls aktuellem
- Zustand ab. Wenn er z.B. bereit ist und wir einen Kaffee auswählen, ändert er seinen Zustand entsprechend. Wenn anschließend Geld eingeworfen wird,
- ändert sich der Zustand wieder und ein Kaffee wird ausgegeben. So ein akzeptierender Zustand wird durch einen doppelten Kreis markiert.
- Nach dem gleichen Prinzip können wir weitere Funktionen hinzufügen, z.B. einen Abbrechenknopf, der den Automaten in den Ausgangszustand zurückversetzt.
- Schließlich ergänzen wir noch ein paar fehlende Zustandsübergänge, damit Karl in jedem der drei Zustände jede der drei möglichen Eingaben annehmen kann.
- Anhand von diesem Diagramm, welches Karl strengstens befolgt, kann man nun bestimmen, ob eine Abfolge von Eingaben zur Ausgabe eines Kaffees führt, also ob
- der letztlich erreichte Zustand akzeptierend ist oder nicht. Üblicherweise wird diese Abfolge von Eingaben als Zeichenkette dargestellt.
- Die formale Version von Automaten wie Carl sind die sogenannten deterministischen endlichen Automaten auch bekannt als DEAs.
- Sie bestehen aus Zustandsmenge, Eingabealphabet, Überführungsfunktion, Startzustand und Menge der
- akzeptierenden N-Zände. Die Menge aller Ketten aus Zeichen aus dem Eingabealphabet, welche vom Automat akzeptiert werden,
- wird dessen erkannte Sprache genannt. Der Begriff deterministisch kommt daher, dass jeder Zustandsübergang eindeutig bestimmt ist, während endlich bedeutet,
- dass nur eine feste Anzahl an Zuständen, nicht etwa unendlich viele, erlaubt ist. Doch unser netter Karl hat, wie alle DEA einen wesentlichen Nachteil. Er ist
- vergesslich. Abgesehen vom aktuellen Zustand kann während der Berechnung nichts
- gespeichert werden, sodass man selbst bei etwas einfachem wie z.B. einem Zähler, für jede Zahl einen neuen Zustand benötigt.
- Das wird spätestens dann zum Problem, wenn wir über die feste Anzahl an Zuständen hinauszählen wollen. Wie könnten wir dies lösen?
- Wir fügen einfach ein endloses Speicherband hinzu. Dieses Band dient als Platz für die eingegebene Zeichenkette und kann nun
- nicht nur gelesen, sondern auch beschrieben und frei nach links, rechts oder gar nicht bewegt werden. Möglich ist dies bei jedem
- Zustandsübergang, der weiterhin durch das gelesene Zeichen bestimmt wird. Dies passiert so lange, bis kein passender Übergang mehr verfügbar ist und die
- Berechnung endet. Das was wir hier beschreiben, wurde 1936 vom Mathematiker Allen Touring formal eingeführt und ist seitdem unter dem
- Namen Touring Maschine bekannt. Nennen wir die hier also mal Timo. Formal besteht eine Truding Maschine aus Zustandsmenge,
- Eingabealphabet, Bandalphabet, Überführungsfunktion, Startzustand, Lehrsymbol und Menge der
- akzeptierenden Endzustände. Die erkannte Sprache ist die Menge aller Eingaben, mit denen die Berechnung einen akzeptierenden Zustand erreichen kann.
- Außerdem wird eine Kombination aus momentaner Bandposition, Bandinhalt und Zustand eine Konfiguration der Touringmaschine genannt.
- Wie manch einer an Timo aber vielleicht schon bemerkt hat, haben Touring Machinen im Vergleich zu DEA ein neues Problem. Die Berechnung kann feststecken
- und keinen Fortschritt mehr machen. Was genau das bedeutet, sehen wir uns später an. Dank ihrem unbeschränkt großen
- Speicherband sind Treing Maschinen aber auch extrem mächtig. Durch eine geeignete Codierung können nämlich beliebige Daten wie Zahlen, Tabellen,
- Diagramme oder ähnliches als Zeichenketten dargestellt werden, auf dem Band gespeichert werden und bei Bedarf aufgesucht und genutzt werden.
- Man kann sich das Band praktisch als eine Art unendlich große Pinwand vorstellen, über die die Maschine frei verfügen kann.
- Eine interessante Anwendung davon ist es, eine ganze Touring Maschine wie z.B. Timo codiert auf dem Band einer anderen zu speichern.
- Diese kann dann unter anderem simulieren, was Timo auf einer bestimmten Eingabe machen würde, indem sie einfach einen Teil ihres Bands für
- eine Konfiguration von Timo reserviert und immer wieder bei Timus Überführungsfunktion nachschaut, was für Zustandsübergänge Timo machen würde und
- die Konfiguration entsprechend anpasst. Eine solche Maschine wird, da sie das Verhalten einer beliebigen anderen nachahmen kann, als universelle
- Touringmaschine bezeichnet. Nachdem Touring Maschinen so mächtig sind, könnte man ja auf das Problem des
- endlosen Rechnens zurückkommen und vermuten, dass es irgendeine Maschine gibt, die vorhersagt, ob eine codierte Maschine auf eine Eingabe hält oder
- endlos weiterrechnet. Idealerweise ist sie so konstruiert, dass sie selbst immer hält und entsprechend der Vorhersage akzeptiert.
- Die formalisierte Version dieser Problemstellung ist als das allgemeine Halteproblem bekannt. Nehmen wir doch mal die Viola, die behauptet zu einer
- codierten Touring Maschine und einer Eingabe für diese Maschine immer bestimmen zu können, ob diese hält oder nicht. Glaubst du ihr das?
- Bauen wir Violas Programm nun so um, dass sie eine einzelne codierte Touring Maschine annimmt und diese kopiert, um sie sowohl als Maschine als auch deren
- Eingabe zu verwenden. Es scheint vielleicht etwas komisch, so eine verrückte Eingabe zu versuchen, aber wie wir schon bei den DES gesehen haben,
- muss auch eine Turing Maschine sich zu jeder Eingabe irgendwie verhalten. Die Ausgabe verändern wir auch, indem wir sie invertieren. Für den Fall, das
- bestimmt wird, dass die codierte Maschine hält, soll sofort eine Endlosschleife gestartet werden und im anderen Fall sofort gehalten und
- akzeptiert werden. Jetzt haben wir endlich das gesamte benötigte Setup, um Viola so richtig auszutrixen. Wir geben Viola, sie selbst
- codiert als Eingabe und schauen gespannt, was passiert. Viola nimmt diese Eingabe, kopiert sie und beantwortet dann mit ihrem magischen
- Programmteil die Frage: "Hält Viola auf der Eingabe codierte Viola?" Der Knackpunkt ist, dass das aber auch genau die Gesamtsituation ist, die wir
- gerade betrachten. Es gibt jetzt zwei Möglichkeiten, aber die magische Vorhersage liegt immer falsch. Wenn die Vorhersage ergibt, dass
- Viola hält, geht sie ja sofort in einer Endlusschleife und hält eben nicht. Umgekehrt hält sie hingegen sofort. An dieser Idee orientiert ist es
- möglich, mathematisch zu beweisen, dass es keine Turing Maschine geben kann, die das allgemeine Halteproblem entscheidet.
- Jetzt haben wir also eine Ewigkeit gebraucht, um so eine theoretische Maschine einzuführen, um dann zu sagen, dass sie etwas nicht kann. Du fragst
- dich also bestimmt, was bedeutet das denn jetzt eigentlich? Nun, die Touring Maschine ist bis heute das weit verbreitetste theoretische
- Modell eines mächtigen Computers. Auch historisch ist dies wichtig, dass sie ja bereits 1936 eingeführt wurde und somit die spätere Entwicklung von
- elektronischen Computern beeinflusst hat. Außerdem sind Touring Maschinen und das Haltproblem für viele mathematische Betrachtungen von großer Bedeutung.
- Ein besonderer mathematischer Satz, den wir hier kurz erwähnen wollen, da er sehr eng mit dem Haltproblem zusammenhängt, ist der sogenannte
- Unvollständigkeitssatz. Er wurde vom Mathematiker Kurtgödel aufgestellt und besagt, dass es kein mathematisches Beweisssystem geben kann,
- mit dem alle wahren arithmetischen Formeln bewiesen werden können. Ein solches Beweisssystem enthält eine entscheidbare Menge an Beweisen, welche
- als Zeichenketten dargestellt werden. Zudem sollte es einer Touring Maschine möglich sein, einen Beweis der bewiesenen wahren arithmetischen Formel
- zuzuordnen. Eine mögliche Strategie, den Unfallständigkeitssatz zu beweisen, können wir hier kurz anreißen.
- Die Strategie ist es zu zeigen, dass sich die Aussage die Turing Maschine mit Codierung X hält auf der Eingabe Y als armetische Formel ausdrücken lässt.
- Dies bedeutet, dass eine Turing Maschine, die versucht das allgemeine Halteproblem zu entscheiden, einfach von kurz nach lang mögliche Zeichenketten
- durchsuchen könnte. und über das Beweisssystem prüfen könnte, ob sie gültige Beweise für die Aussage sind. Da entweder die Aussage oder ihre
- Verneinung wahr ist, müsste die Maschine also irgendwann einen gültigen Beweis für eine der beiden finden und somit das allgemeine Haltproblem entscheiden
- können. Dies ist, wie wir gesehen haben, aber nicht möglich, was zu Schlussfolgerung führt, dass es auch kein solches
- Beweissystem geben kann. Wir hoffen, dass dir das Video gefallen hat und du etwas mitnehmen konntest. Mit wenig Aufwand lassen sich zu vielen der
- genannten Konzepte gute spezialisierte Ressourcen finden. Vielleicht besteht ja sogar das Interesse tiefer in die Themen einzutauchen.