Das Halteproblem ist unentscheidbar
Вставка
- Опубліковано 13 чер 2015
- Wir sehen in diesem Video einen anschaulichen Beweis dafür, dass das Halteproblem unentscheidbar ist. Es handelt sich quasi um den originalen Beweis von Alan Turing in bildlicher Form.
![Aufgaben zu Entscheidbarkeit und Satz von Rice [Klausuraufgaben Berechenbarkeit #03]](http://i.ytimg.com/vi/jpbGGNbpYzM/mqdefault.jpg)
Nach 7 Jahren hilft es mir immer noch für meine Klausur. Vielen Dank
Der Widerspruch hat mir Probleme bereitet, aber ich glaube, dass ich es jetzt habe :D
Danke!
..sooo hilfreich, danke! :D
Sehr gutes Video, sehr verständlich erklärt, super👍👍👍
Gute Videos, aber das Mikrofon macht leise Störgeräusche, auch im letzten Video. Sehr leise, sehr hoch, aber sehr nervig.
"Wenn du herausgefunden hast, dass du anhälst, dann gehe jetzt in eine Endlosschleife"
Evtl. versteh ich das gerade nicht, weil ich schon zu lange am Stück am lernen bin oder ich habe was verpasst.
Wieso ist das so? Warum sagen wir das, wegen dem Widerspruchsbeweis nehme ich an.
Genau, um einen Widerspruch zu erzeugen! Wir nehmen an, dass es eine Maschine gibt, die das Halteproblem löst. Dann bauen wir eine neue Maschine U, für die die ursprüngliche Maschine die falsche Antwort gibt. Das ist ein Widerspruch, da wir ja angenommen hatten, dass die ursprüngliche Maschine das Halteproblem löst. Somit gibt es keine Maschine, die das Halteproblem löst.
31415 2635
Du kannst zu jedem Programm ein Unkehrprogramm schreiben indem du in dem Umkehrprogramm das eigentliche Programm ausführst und das Ergebnis negierst. Deshalb geht das trivialerweise
Ich glaube es hilft mehr wenn man es so betrachtet dass man sagt wenn du merkst du bist in einer endlosschleife dann sag es also entscheide ja endlosschleife doch wenn er in endlosschleife ist kann er das nicht
gut erklärt, ich danke
Gut zusammengefasst, sehr verständlich.
Vielen lieben Dank :)
Das Halteproblem ist Semi-entscheidbar und somit rekursiv aufzählbar und berechenbar aber das Kompliment des Haltproblems ist nicht enscheidbar. Eine Sprache ist dann erst entscheidbar, wenn es selber und sein Kompliment rekursiv aufzählbar sind. Dies trifft aber nicht beim Haltproblem zu, deswegen ist es unentscheidbar. Liege ich richtig ?
Alles richtig!
Gilt bei diesem Problem, dass der Haltealgorithmus nicht in das Programm sehen kann? Oder anders: Was weiß der prüfende Haltealgorithmus? Kennt er den Status der Variablen des Programmes P? Weiß er bei welcher Code-Zeile das Programm P gerade ist? Denn wenn dem so ist, dann weiß er genau wann es in einer Endlosschleife ist. Sobald alle Variablen sich nach nach der zweiten gleichen Abfolge der gleichen Codezeilen nicht mehr verändern. Was übersehe ich hier?
Wir nehmen an, dass ein Haltealgorithmus existiert und dieser bekommt das Programm und die Eingabe für das Programm. Er kann also den "Quelltext" sehen, er kann die Eingabe sehen, er könnte anfangen zu simulieren, was passiert, wenn das Programm auf der Eingabe läuft, er könnte sogar, wie Du vorschlägst, sich jede Konfiguration merken und vergleichen, ob eine Konfiguration ein weiteres Mal auftritt und in diesem Fall erkennen, dass das Programm nicht hält.
Die Antwort auf deine Frage liegt darin, dass "Endlosschleife" nicht unbedingt bedeutet, dass alle Variablen wieder genau gleich belegt sind wie in einem früheren Schritt, sondern es kann sein, dass das Programm unendlich viele verschiedene Konfigurationen durchläuft und deshalb niemals halten wird. Bestes Beispiel: Ein Endlosschleife, die bei realen Computern zu einem Stack-Overflow führt. In jedem Schritt wird mehr auf den Speicher geschrieben, d.h. der Speicher nimmt in jedem Schritt eine neue Konfiguration an, die es vorher noch nicht gab. Es kommt also keine Konfiguration doppelt vor, das Programm hält aber nicht an.
Wie bei pi da gibt es ja kein pattern
Wieso kann man einfach sagen dass ein Programm jetzt in eine Endlosschleife geht oder einfach anhält? Das hängt doch vom Programm ab ob es hält oder nicht. So erzwingt man ja einen Widerspruch der eigentlich nicht da ist. Was verstehe ich falsch?
U ist kein gegebenes Programm. Wir schreiben das Programm U selber, d.h. wir können auch sagen, dass es in eine Endlosschleife gehen soll, wenn der Unteraufruf vom Haltealgorithmus gesagt hat, dass es anhält.
@@NLogSpaceAchse weil der Fakt dass es in einer endlosschleife ist schließt ja nicht aus dass es anhält wenn es so eine Maschine oder einen Algorithmus gibt muss es so oder so anhalten da es um entscheidbar zu sein eine Entscheidung fällt was ja dann nicht passiert weil es nicht anhalten kann
Danke!
Ich verstehe nicht, warum das Programm in eine Endlosschleife gehen muss wenn es raus findet, dass es anhält. Kann man nicht einfach sagen, wenn du raus findest, dass du anhältst gib true aus und lass den Rest des Programms ablaufen bis es fertig ist?
Wir machen einen Widerspruchsbeweis, d.h. wir haben angenommen man könnte das Halteproblem entscheiden und wir führen diese Annahme jetzt zum Widerspruch. Dafür konstruieren wir dieses Programm U, bei dem sich der Halte-Algorithmus falsch verhalten soll. Wenn U also rausfindet, dass U anhalten wird, dann wollen wir U jetzt so bauen, dass es gerade nicht anhält. Deshalb gehen wir in eine Endlosschleife, einfach damit die Antwort vom Haltealgorithmus nicht stimmt.
@@NLogSpace Ahhhhh ok, ja jetzt machts Sinn, ich stand echt auf dem Schlauch. Vielen lieben Dank :)
@@NLogSpace Aber damit hat man doch ein komplett neues Programm, das nicht mehr U sonder U' ist?
Warum nehmen wir an das die Maschine U immer die negierte Antwort von dem Halte-Algorithmus ausgibt? Ohne diese Annahme würde die Mschine H ja wieder die richtige Antwort auf die Annahme ausgeben.
+Martin C. Wir nehmen an, dass es eine Maschine gibt, die das Halteproblem löst, und wollen das zum Widerspruch führen. Sobald wir einen Widerspruch erhalten, wissen wir, dass die Annahme falsch war, also dass das Halteproblem unentscheidbar ist. Und um den Widerspruch zu erhalten, müssen wir U eben gerade so konstruieren. Wie Du schon gesagt hast, würden wir bei einer anderen Konstruktion immer richtige Antworten erhalten und somit auch keinen Widerspruch.
finde die gedachte schleife auch verwirrent. in der negation bildet sich bei unsere annahme der widerspruch, um anzuzeigen, dass ich als programm nicht halte müsste ich halten.
Wo finde ich denn das Video zu den Reduktionstechniken? ^^'
Das findest Du hier auf meinem Kanal! Bald. :)
@@NLogSpace und wo finde ich dieses Video auf deinem Kanal jetzt? :D
@@igorkudryk2199 In der Serie über Komplexität mache ich viele Reduktionen. Die Videos 11-22 beschäftigen sich mit NP-vollständigen Problemen, da wird jedes mal eine Reduktion gemacht. In der Serie über Berechenbarkeit kommen die Videos mit Reduktionen von unentscheidbaren Probleme demnächst.
@@NLogSpace danke!
Eingabe E ist ja identische zu Programm P, theoretisch ist beides beispielsweise binär kodiert, somit würde die Universelle TM Mp zunächst P und E:=P jeweils auf die Bänder schreiben und nach P abarbeiten, richtig? Mich verwirrt immer die eigene Kodierung als Eingabe. Da P==E, handelt es sich doch theoretisch um das spezielle Haltproblem, ist das „SPEZIELLE“ daran, dass nicht alle Eingaben e wie beim allgemeinen Halteproblem betrachtet werden, sondern wirklich nur eine einzige Eingabe also w und ist somit eine Teilmenge? Würde mich über eine Antwort freuen...
Ja, man zeigt quasi dass das spezielle Halteproblem unentscheidbar ist. Aber das spezielle Halteproblem ist quasi ein Teilproblem vom "echten" Halteproblem, daher folgt auch direkt, dass das Halteproblem unentscheidbar ist.
Danke (y)
Also dass sie eine bessere Form des Lügenparadoxon auf irgendeine Entscheidungsfrage anwenden lasst ist ja nichts neues, da hast du vollkommen recht, wobei das noch nicht sagt dass man keinen - zwar nicht hundertprozent sicheren aber doch funktionsfähigen - Algorithmus basteln könnte der fast immer greift bevor sich der PC aufhängt wegen einer Endlosschleife.
Lieber Leif,
wäre es nicht möglich, das Halteproblem zu lösen, wenn man in der Lage wäre, Programme von hinten nach vorne ablaufen zu lassen? Wenn man bereits den Output "True, das Programm hält" nimmt, und dann rückwärts alle Schritte nachvollzieht und schaut, ob es mit dem Input kompatibel ist?
Wir haben gezeigt, dass das Halteproblem unentscheidbar ist, also nein, das wird nicht funktionieren. Das Problem dabei wäre genau das gleiche: Wenn ein Programm nicht anhält, dann weiß man nie wie lange man noch weiter simulieren soll, bevor man aufhört. Dabei ist egal, ob man das Programm vorwärts oder rückwärts simuliert.
Ist U mit U als Input nicht auch eine Endlosschleife? Also wenn man U mit U dem Haltealgorithmus übergeben würde, würde dieser dann nicht zum Ergebnis kommen, dass U auf U nicht terminiert?
Egal was man annimmt, beides führt zum Widerspruch. Wenn U auf U tatsächlich nicht terminiert, dann folgt daraus, dann findet der Haltealgorithmus dies nach endlicher Zeit heraus, und unser U ist so gebaut, dass es dann terminiert. Widerspruch.
NLogSpace Danke für die schnelle Antwort. Wir kennen zwar die Implementierung nicht, aber ich stelle mir das so vor, dass der in U eingebettete Haltealgorithmus aufgrund des Widerspruchs nicht terminieren könnte. Dann könnte doch eine andere Instanz des Haltealgorithmus quasi von außen das U-Konstrukt betrachten und würde zu eben diesem Ergebnis kommen. Was habe ich falsch verstanden?
Ich erkläre es mir indem ich denke wenn ein Programm rein kommt das eine endlosschleife hat dann muss ja ein Ergebnis kommt also eine Entscheidung ja es hält oder nein es hält nicht aber während er guckt ob es hält hält es nie da vielleicht in Zukunft es doch halten könnte was aber die endlosschleife verursacht und es gibt keine Entscheidung 😅
4:49 Verstehe ich nicht. Warum würde man das machen?
Ich denke es geht darum zu sagen, dass es prinzipiell eine Maschine geben kann, die beim Halten in eine Schleife geht.
Und wenn sie in eine Schleife geht haltet.
Und das wäre widersprüchlich, wie man aber überhaupt auf die Idee bekommt das zu behaupten ist mir schleierhaft.
Mhh, für mein Verständnis läuft das ganze Halteproblem dann im Endeffekt doch nur auf "einfache" Rekursion hinaus?
Sobald ich etwas mit sich selbst füttere, dass sich mit sich selbst füttert, dass sich mit sich selbst füttert, dass sich mit sich selbst füttert, dass sich mit sich selbst füttert
Könntest du die mathematische Form Schritt für Schritt erklären ?
ich gebe u1 u2 als eingabe. was kriegt u2 als eingabe?
Wir haben hier nur U, kein U1 und U2. U ist ein Programm, d.h. wir können es einerseits mit irgendeiner Eingabe ausführen, andererseits auch als String (Quellcode von U) betrachten. Wenn wir U mit der Eingabe U aufrufen heißt das, wir geben dem Programm U seinen eigenen Quellcode als Eingabe.
Hallo, danke für die Antwort. Braucht nicht der Quellcode auch eine Eingabe dann? Nehmen wir an U(x). U ist das Haltetestprogramm und x die Eingabe. Wie schaut es dann aus wenn sich das Halteprogramm selbst testet? U(U(?)) Für alle anderen Programme ist es klar. Ich meine das U erwartet eine Eingabe, dann muss dass Simulierte U auch eine Eingabe haben oder verstehe ich da was falsch. Oder an nem anderen Beispiel. Ich habe einen Debugger. Mit dem will ich jetzt den Debugger selbst durchsteppen. Ich rufe "debug debugger.exe" auf. Im debugmodus erwartet debugger.exe eine Eingabe.
Der Quellcode von U, den wir dem Programm U übergeben, braucht keine weitere Eingabe, denn wir führen ihn nicht aus! U ist ein Programm, das eine Eingabe erwartet. Wann immer wir U ausführen, dann sagen wir auch, auf welcher Eingabe. An des besagten Stelle, führen wir das U jedoch nicht aus, sondern betrachten es nur als einen String, nämlich den Quellcode von U: Der Halte-Algorithmus erwartet nämlich 1. ein Programm, das er ausführen soll, und 2. einen String, den er als Eingabe für das Programm benutzt. Dieser String ist in unserem Fall der Quellcode von U, es muss sich im Allgemeinen gar nicht um ausführbaren Quellcode handeln.
ok thx.
Müsste nicht die Formulierung heißen: "Man versucht das neue Problem auf das Halteproblem zu reduzieren" und nicht "Man versucht das Halteproblem auf das neue Problem zu reduzieren"?
Das war in einem anderen Video erklärt zu Reduktion
Vielen Dank für dieses schöne Video! Trotzdem erschließt sich mir der Beweis noch nicht so ganz. Mein Problem ist, dass man ja eigentlich nur gezeigt hat, dass U mit sich selbst als Eingabe nicht funktioniert. Alle anderen Eingaben könnten ja immer noch funktionieren. In der Mathematik beispielsweise kann man ja auch teilen, auch wenn durch 0 nicht geht.
So wie ich das verstanden habe könnte ich ja sonst auch beweisen, dass man in der Mathematik nicht teilen kann:
1. Gegenannahme, teilen funktioniert. Wir definieren eine Funktion f(x)=1/x. Analog: Gegenannahme, Maschine existiert, Definition von U.
2. Wir setzten x=0. Geht nicht, Widerspruch, teilen ist unmöglich. Analog: Wir fütter U mit sich selbst, geht nicht, Widerspruch, Halteproblem ist unentscheidbar.
Wie wir aber wissen kann man aber sehr wohl teilen, eben nur für x aus R\{0}. Also könnte doch auch das Halteproblem entscheidbar sein, nur eben nicht für sich selbst.
Der Punkt, den Du ansprichst, habe ich schon oft gehört. Zunächst mal ist es ganz einfach, wenn man sich an die Definitionen der Begriffe erinnert: Ein Problem ist "entscheidbar", wenn es einen Algorithmus gibt, der das Problem für *jede beliebige Eingabe* korrekt löst. Das ist eine ganz natürliche Forderung. Und genau diese Bedingung haben wir bei unserem Widerspruch ausgenutzt. Es gibt keinen Algorithmus, der das Halteproblem für *jede beliebige Eingabe* löst, denn wir konnten zeigen, dass ein solcher Algorithmus auf mindestens einer Eingabe falsch antwortet. Das Halteproblem ist also unentscheidbar.
Nun könnte man denken, dass es sich so verhält wie in deinem Beispiel mit der Division. Gibt es vielleicht nur eine einzige Ausnahme? Gibt es einen Algorithmus, der das Halteproblem auf allen Eingaben mit nur einer einzigen Ausnahme richtig löst? Nein, dem ist nicht so. Gäbe es einen solchen Algorithmus, der nur auf einer einzigen Eingabe U falsch antwortet, könnte ich ihn leicht umschreiben, sodass er U am Anfang als Spezialfall abfängt und auch hier die richtige Antwort gibt. Und falls die Eingabe nicht U war, dann führe ich den ursprünglichen Algorithmus aus. Damit hätte ich dann wieder ein Entscheidungsverfahren, das für alle Eingaben korrekt funktioniert, doch wir wissen schon, dass es kein solches gibt, Widerspruch!
Mit ähnlicher Argumentation kann man auch zeigen, dass es keinen Algorithmus gibt, der das Halteproblem auf allen Eingabe bis auf endlich viele Ausnahmen löst. Das ist übrigens eine nette Übungsaufgabe, danke für die Idee! :)
Man kann natürlich von vielen Programmen recht einfach sehen, ob sie anhalten oder nicht. Doch wir wissen nun, kein Algorithmus kann das Problem in völliger Allgemeinheit - also für alle Eingaben - korrekt lösen. Im Gegenteil: Jeder Algorithmus für das Halteproblem wird sogar auf unendlichen vielen Eingaben falsch antworten.
@@NLogSpace Ahh ich glaube jetzt habe ich es verstanden! Vielen, vielen Dank für deine schönen Videos und auch dass du auf Kommentare wie meinen so ausführlich antwortest. Ein echter Segen für Studenten der theoretischen Informatik :D
Ich versuche seit mehr als 2h den Beweis zu verstehen.. Ich verstehe aber eine Sache nicht.
Wir bauen uns hier U, welches den Halte-Algorithmus enthaelt.. U ist eine modifizierte Version von dem Halte-Algorithmus. Wenn wir zeigen, dass U bei Eingabe von U nicht funktioniert, sagt das doch nichts ueber den Halte-Algorithmus aus, oder? U benutzt diesen doch lediglich ..
Alle Videos über Turings Halteproblem bauschen Unwesentliches dermassen auf, dass die Trivialität des eigentlichen Kerns kaum mehr zu erkennen ist.
Das Ganze ist doch lediglich eine Abwandlung des Lügnerparadoxons:
Lügnerparadoxon:
Es gibt keine allgemeine Methode, logische Aussagen entweder als wahr oder falsch einzuordnen. Dazu muss man nur ein Beispiel finden, wo das tatsächlich nicht geht:
"Ich lüge".
Ja, stimmt. Aber was soll das? Wir sind doch keine Mathematiker, sondern Informatiker!
In Wahrheit hat man GENAU EIN Programm konstruiert, wo das nicht geht, und das auch nur auf praktisch vollkommen irrelevante Weise. Mit diesen Massstäben müsste man z.B. weiten Teilen der Kryptographie jegliches Fundament absprechen, denn mathematisch ist leicht einzusehen, dass Hashfunktionen nicht kollisionsresistent sind. Praktisch, und das ist ja entscheidend, sind sie es aber durchaus!
Ich spreche dieser Art von Beweis jegliche informationstechnische Relevanz ab.
Danke für deinen Kommentar!
Zunächst mal: Es geht auf meinem Kanal vor allem um theoretische Informatik, die ich vom Charakter her eher der Mathematik als der Informatik zuordnen würde. Wir beweisen Aussagen ganz formal, wie in der Mathematik. Ich lege gleichzeitig den Fokus darauf, die Ideen dieser formalen Beweise anschaulich darzustellen.
Du hast Recht, dass wir in diesem Video genau ein Programm konstruiert haben, an dem man bereits sieht, dass das Halteproblem unentscheidbar ist. Und das ist meiner Ansicht nach ein riesiger Erkenntnisgewinn:
- Einerseits sagt es uns, dass man mit Turingmaschinen so etwas wie das Lügnerparadoxon überhaupt ausdrücken kann! Turingmaschinen (und damit auch alle anderen vernünftigen Berechnungmodelle, siehe Church-Turing-These) sind also mächtig genug hierfür, während das gleiche Argument für schwächere Automaten (z.B. DEAs oder sogar LBAs) nicht funktioniert, für diese ist das Halteproblem nämlich entscheidbar.
- Andererseits zeigt es uns, dass es überhaupt unentscheidbare Probleme gibt, was a priori gar nicht klar ist. Dass man von einem Probleme so direkt zeigen kann, dass es unentscheidbar ist, ist (für mich) schon relativ überraschend. Umso überraschender wäre es, wenn genau dieses Problem gleichzeitig auch noch von höchster praktischer Relevanz wäre. Und auch wenn Du dieses konkrete Problem für irrelevant hältst - es gibt viele sehr relevante Probleme (z.B. das "Entscheidungsproblem" von Hilbert), die ebenfalls unentscheidbar sind und auch sehr eng verwandt sind mit dem Halteproblem.
Ich halte dieses Wissen über theoretische Informatik auch für praxisrelevant. Wenn wir ein Problem in der Praxis lösen wollen, dann sollten wir uns darüber bewusst sein, ob dieses Problem überhaupt lösbar ist und wenn ja, was der effizienteste Weg ist. Und man sollte auch wissen, ob es für ein allgemein formuliertes Problem vielleicht Spezialfälle gibt, von denen bewiesen wurde, dass sie nicht effizient gelöst werden können. Im Bereich der Berechenbarkeit und der Komplexität erforscht man genau diese Fragen, die Grenzen der Entscheidbarkeit und der effizient lösbaren Probleme.
John Smith
Informatik ist ein Teilgebiet der Mathematik und deshalb ist jeder Informatiker auch Mathematiker.
Programmieren und die praktische Umsetzung ist imho kein Gebiet der Informatik sondern lediglich Werkzeug ähnlich wie in statistiklastigen Disziplinen wie Sozialwissenschaften/Psychologie wo auch programmiert wird, aber keiner auf die Idee kommt zu sagen Programmieren sei Bestandteil des Faches.
Problem ist dass es im
@@tcap112Ja leider wüsste ich vorher dass ich indirektes Mathe Studium wage hätte ich es nicht angefangen. Wobei dies auch nicht allgemeingültig in den meisten Universitäten gefordert wird
@@tangerinegames4515 Unis sind aber nicht dazu da, nur Leute für die Praxis auszubilden. Unis forschen auch an weiterführenden Dingen, weil Wissen an sich einen Wert hat, selbst wenn es in keinem Job für irgendeine Firma verwertbar wäre.
Man muss unterscheiden zwischen der Gültigkeit einer Aussage und deren Beweisbarkeit.
Die Hypothese zu den Nullstellen der Riemannschen zeta-Funktion ist (anscheinend) wahr, da es (bisher) keine Gegenbeispiele gibt. Eventuell lässt sie sich aus den Axiomen nicht beweisen, könnte also unabhängig sein.
Falls ein Programm nicht terminiert, kann man das niemals (endgültig) feststellen. Selbst ein terminierendes Programm kann Milliarden von Jahren laufen bevor es stoppt.
Ein Quasi-Halteprogramm sollte 3 Ergebnis-Optionen haben: "hält", "läuft ewig", "läuft eventuell ewig".
Beim informatikstudieren hatten wir mal eine Aufgabe wo wir auch irgendwas programmieren mussteten. Ich habe mir da einen Spaß gemacht und auch sowas mit einer Endlosschefie gemacht, als ich es dann hochgeladen habe sind die Server der TU gecrashed und alles war kaputt. Das war lustig
Was ein bullshit :D
Nachdem ich mir das Video ganze 4 Minuten lang angesehen habe, wurde noch immer nicht damit begonnen, den Beweis auch nur wenigstens zu skizzieren. Nichts. Nur Bla bla. Daher werde ich mir auch den Rest nicht ansehen.