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
Tipp auf eine Zeit – das Video springt genau dorthin.
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.
Zum Nachlesen
Universelle TuringmaschineEine universelle Turingmaschine (UTM) ist in der Informatik eine Turingmaschine, die eine beliebige Turingmaschine auf beliebiger Eingabe simuliert.
TuringmaschineEine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach …
HalteproblemDas Halteproblem beschreibt eine Frage aus der theoretischen Informatik. Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt …
Nichtdeterministische TuringmaschineEine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine …