HALTEPROBLEM. TURINGMASCHINEN. UNVOLLSTÄNDIGKEITSSATZ. Theoretische Informatik erklärt (2025)
Käpsele TV
https://www.youtube.com/watch?v=nGJme7RlS40

Transkript (automatisch erstellt)

0:00 Willkommen zu unserem Video rund ums Halteproblem, dessen Herleitung und weitreichenden Konsequenzen. Falls ihr Begriffe wie Automatentheorie,
0:10 Touringmaschine oder Berechenbarkeit schon etwas sagen, etwa aus dem Studium, dann hoffen wir eine Übersicht zu bieten, um dein Wissen aufzufrischen und
0:20 den Zusammenhang zu festigen. Doch keine Angst, auch wenn das alles nur nach Fachchinesisch klingt, wollen wir dir einen netten Einblick in die
0:28 wunderbare Welt der theoretischen Informatik bieten. In jedem Fall ist dieses Video lediglich als anschauliche Übersicht konzipiert.
0:37 Die ausführliche formale Behandlung dieser Themen kann nämlich mehrere Monate an Vorlesungen beanspruchen. Beginnen wir mit einem sogenannten
0:45 Automaten. Einem Automaten, den wir alle kennen, dem Kaffeeautomaten. Der hier heißt scheinbar Karel. Doch woher weiß Karl, wie er sich
0:55 verhalten soll? Wir erwarten ja schließlich, dass etwas passiert, wenn wir einen Knopf drücken. Nun, das hängt von Karls aktuellem
1:03 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,
1:13 ändert sich der Zustand wieder und ein Kaffee wird ausgegeben. So ein akzeptierender Zustand wird durch einen doppelten Kreis markiert.
1:21 Nach dem gleichen Prinzip können wir weitere Funktionen hinzufügen, z.B. einen Abbrechenknopf, der den Automaten in den Ausgangszustand zurückversetzt.
1:32 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.
1:42 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
1:53 der letztlich erreichte Zustand akzeptierend ist oder nicht. Üblicherweise wird diese Abfolge von Eingaben als Zeichenkette dargestellt.
2:04 Die formale Version von Automaten wie Carl sind die sogenannten deterministischen endlichen Automaten auch bekannt als DEAs.
2:14 Sie bestehen aus Zustandsmenge, Eingabealphabet, Überführungsfunktion, Startzustand und Menge der
2:22 akzeptierenden N-Zände. Die Menge aller Ketten aus Zeichen aus dem Eingabealphabet, welche vom Automat akzeptiert werden,
2:32 wird dessen erkannte Sprache genannt. Der Begriff deterministisch kommt daher, dass jeder Zustandsübergang eindeutig bestimmt ist, während endlich bedeutet,
2:43 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
2:55 vergesslich. Abgesehen vom aktuellen Zustand kann während der Berechnung nichts
3:02 gespeichert werden, sodass man selbst bei etwas einfachem wie z.B. einem Zähler, für jede Zahl einen neuen Zustand benötigt.
3:12 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?
3:22 Wir fügen einfach ein endloses Speicherband hinzu. Dieses Band dient als Platz für die eingegebene Zeichenkette und kann nun
3:31 nicht nur gelesen, sondern auch beschrieben und frei nach links, rechts oder gar nicht bewegt werden. Möglich ist dies bei jedem
3:40 Zustandsübergang, der weiterhin durch das gelesene Zeichen bestimmt wird. Dies passiert so lange, bis kein passender Übergang mehr verfügbar ist und die
3:49 Berechnung endet. Das was wir hier beschreiben, wurde 1936 vom Mathematiker Allen Touring formal eingeführt und ist seitdem unter dem
4:00 Namen Touring Maschine bekannt. Nennen wir die hier also mal Timo. Formal besteht eine Truding Maschine aus Zustandsmenge,
4:10 Eingabealphabet, Bandalphabet, Überführungsfunktion, Startzustand, Lehrsymbol und Menge der
4:19 akzeptierenden Endzustände. Die erkannte Sprache ist die Menge aller Eingaben, mit denen die Berechnung einen akzeptierenden Zustand erreichen kann.
4:30 Außerdem wird eine Kombination aus momentaner Bandposition, Bandinhalt und Zustand eine Konfiguration der Touringmaschine genannt.
4:40 Wie manch einer an Timo aber vielleicht schon bemerkt hat, haben Touring Machinen im Vergleich zu DEA ein neues Problem. Die Berechnung kann feststecken
4:49 und keinen Fortschritt mehr machen. Was genau das bedeutet, sehen wir uns später an. Dank ihrem unbeschränkt großen
4:57 Speicherband sind Treing Maschinen aber auch extrem mächtig. Durch eine geeignete Codierung können nämlich beliebige Daten wie Zahlen, Tabellen,
5:06 Diagramme oder ähnliches als Zeichenketten dargestellt werden, auf dem Band gespeichert werden und bei Bedarf aufgesucht und genutzt werden.
5:14 Man kann sich das Band praktisch als eine Art unendlich große Pinwand vorstellen, über die die Maschine frei verfügen kann.
5:23 Eine interessante Anwendung davon ist es, eine ganze Touring Maschine wie z.B. Timo codiert auf dem Band einer anderen zu speichern.
5:33 Diese kann dann unter anderem simulieren, was Timo auf einer bestimmten Eingabe machen würde, indem sie einfach einen Teil ihres Bands für
5:40 eine Konfiguration von Timo reserviert und immer wieder bei Timus Überführungsfunktion nachschaut, was für Zustandsübergänge Timo machen würde und
5:48 die Konfiguration entsprechend anpasst. Eine solche Maschine wird, da sie das Verhalten einer beliebigen anderen nachahmen kann, als universelle
5:57 Touringmaschine bezeichnet. Nachdem Touring Maschinen so mächtig sind, könnte man ja auf das Problem des
6:05 endlosen Rechnens zurückkommen und vermuten, dass es irgendeine Maschine gibt, die vorhersagt, ob eine codierte Maschine auf eine Eingabe hält oder
6:14 endlos weiterrechnet. Idealerweise ist sie so konstruiert, dass sie selbst immer hält und entsprechend der Vorhersage akzeptiert.
6:24 Die formalisierte Version dieser Problemstellung ist als das allgemeine Halteproblem bekannt. Nehmen wir doch mal die Viola, die behauptet zu einer
6:32 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?
6:44 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
6:52 Eingabe zu verwenden. Es scheint vielleicht etwas komisch, so eine verrückte Eingabe zu versuchen, aber wie wir schon bei den DES gesehen haben,
7:01 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
7:11 bestimmt wird, dass die codierte Maschine hält, soll sofort eine Endlosschleife gestartet werden und im anderen Fall sofort gehalten und
7:18 akzeptiert werden. Jetzt haben wir endlich das gesamte benötigte Setup, um Viola so richtig auszutrixen. Wir geben Viola, sie selbst
7:27 codiert als Eingabe und schauen gespannt, was passiert. Viola nimmt diese Eingabe, kopiert sie und beantwortet dann mit ihrem magischen
7:36 Programmteil die Frage: "Hält Viola auf der Eingabe codierte Viola?" Der Knackpunkt ist, dass das aber auch genau die Gesamtsituation ist, die wir
7:46 gerade betrachten. Es gibt jetzt zwei Möglichkeiten, aber die magische Vorhersage liegt immer falsch. Wenn die Vorhersage ergibt, dass
7:55 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
8:05 möglich, mathematisch zu beweisen, dass es keine Turing Maschine geben kann, die das allgemeine Halteproblem entscheidet.
8:15 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
8:23 dich also bestimmt, was bedeutet das denn jetzt eigentlich? Nun, die Touring Maschine ist bis heute das weit verbreitetste theoretische
8:32 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
8:42 elektronischen Computern beeinflusst hat. Außerdem sind Touring Maschinen und das Haltproblem für viele mathematische Betrachtungen von großer Bedeutung.
8:53 Ein besonderer mathematischer Satz, den wir hier kurz erwähnen wollen, da er sehr eng mit dem Haltproblem zusammenhängt, ist der sogenannte
9:00 Unvollständigkeitssatz. Er wurde vom Mathematiker Kurtgödel aufgestellt und besagt, dass es kein mathematisches Beweisssystem geben kann,
9:10 mit dem alle wahren arithmetischen Formeln bewiesen werden können. Ein solches Beweisssystem enthält eine entscheidbare Menge an Beweisen, welche
9:20 als Zeichenketten dargestellt werden. Zudem sollte es einer Touring Maschine möglich sein, einen Beweis der bewiesenen wahren arithmetischen Formel
9:29 zuzuordnen. Eine mögliche Strategie, den Unfallständigkeitssatz zu beweisen, können wir hier kurz anreißen.
9:38 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.
9:50 Dies bedeutet, dass eine Turing Maschine, die versucht das allgemeine Halteproblem zu entscheiden, einfach von kurz nach lang mögliche Zeichenketten
9:59 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
10:10 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
10:18 können. Dies ist, wie wir gesehen haben, aber nicht möglich, was zu Schlussfolgerung führt, dass es auch kein solches
10:27 Beweissystem geben kann. Wir hoffen, dass dir das Video gefallen hat und du etwas mitnehmen konntest. Mit wenig Aufwand lassen sich zu vielen der
10:37 genannten Konzepte gute spezialisierte Ressourcen finden. Vielleicht besteht ja sogar das Interesse tiefer in die Themen einzutauchen.