Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Das Halteproblem ist unentscheidbar
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 93 Zeilen
- so in diesem Video geht es um das halteproblem aus der theoretischen Informatik ich möchte zunächst mal erklären was das halteproblem überhaupt
- ist und danach werden wir uns überlegen warum es sich bei dem halteproblem um ein unentscheidbares Problem handelt aber immerhin um ein semientscheidbares
- Problem okay stellen wir uns mal folgende Situation vor wir sind mal wieder am Programmieren haben irgendein Programm geschrieben was irgendwas
- ausrechnen soll ja und dann starten wir das Programm und wir erwarten natürlich dass es dann irgendwann anhält und uns die Ausgabe uns das Ergebnis liefert ja
- äh aber das tut es nicht ja das Programm hält irgendwie nicht an und ja es liegt wahrscheinlich mal wieder an irgendeiner while Schleife wo wir die Bedingungen
- falsch gesetzt haben oder irgendwas vergessen haben ja wie auch immer unser Programm hält nicht an und dann kommt uns der Gedanke okay machen wir doch ein
- für alle mal schluss damit wir können doch ein Programm schreiben was einfach irgendein anderes Programm als Eingabe bekommt und dann überprüft
- ob das Programm anhalten wird oder nicht und damit könnten wir dann schon im Voraus checken ob ein Programm anhalten wird oder nicht also ob wir irgendwie
- einen Fehler gemacht haben bei den wi schleifenbedingungen ja damit würden wir wahrscheinlich auch gleichzeitig noch allen anderen Programmierern auf der
- Welt großen Gefallen tun ja wenn sich endlich niemand mehr darüber ärgern muss dass das Programm nicht hält obwohl es eigentlich anhalten sollte was wir damit
- eigentlich tun wollen ist wir wollen das halteproblem Lösen ja das heißt wir wollen ein solch Algorithmus hier schreiben er bekommt irgendein Programm
- P und irgende eine Eingabe für dieses Programm die nennen wir mal e die Eingabe ja dann soll unser halteralgorithmus laufen und wenn P auf
- der Eingabe e irgendwann anhält dann soll unser halteralgorithmus ja sagen und wenn P niemals anhalten wird dann soll unser algorimus nein sagen ja ja
- und der der springende Punkt ist halt insbesondere hier bei der neinausgabe also wenn P niemals auf E hält also P auf E würde endlich lange laufen unser
- haltealgorithmus soll das aber schon nach endlicher Zeit feststellen und Nein antworten ja also insbesondere das hier wäre dann die Besonderheit an unserem an
- unserem haltealgorithmus aber leider werden wir enttäuscht ja ein solchenten haltealgorithmus gibt es nicht ja das ist das Resultat aus der theoretischen
- Informatik das halteproblem ist unentscheidbar das heißt es gibt keinen Algorithmus der für jedes Programm P und jede Eingabe e
- immer nach endlicher Zeit sagen kann ob P auf der Eingabe e hält oder nicht ja und wenn man sich jetzt noch nicht so genau vorstellen kann warum das
- überhaupt scheitert also warum es so ein Algorithmus nicht geben kann wir werden es gleich einmal anschaulich beweisen allerdings möchte ich auch ein kurzes
- Beispielprogramm geben bei dem das schon schwierig zu entscheiden ist ja schauen wir uns mal kurz diesen Mix hier aus Java und PSO Code an wir nehmen als
- Eingabe irgendeine Zahl ja und solange die Zahl nicht eins ist tun wir folgendes wenn sie gerade ist dann halbieren wir Sie und wenn sie ungerade
- ist dann rechnen wir mal 3 und + 1 und die Funktion habe ich kollat genannt weil die berühmte kollat Vermutung ist aus der Mathematik ja egal mit welcher
- Zahl wir hier anfangen mit welcher natürlichen Zahl wir gelangen irgendwann immer zur ein das konnte aber noch nicht bewiesen werden ja man weiß also noch
- nicht also obwohl sich da ganz viele Mathematik den Kopf dran zerbrochen haben weiß man nicht ob dieses iterieren hier ja mit irgendeiner natürlichen Zahl
- anfangen und dann immer wieder entweder halbieren oder mal 3 und + 1 rechnen ob das immer irgendwann bei der 1 endet oder nicht ja und offenbar hält das
- Programm hier genau dann an wenn wir irgendwann die eins erreichen ja das heißt wenn wir so ein haltealgorithmus hätten dann könnten wir ihn auch hierauf
- anwenden und damit dann die Antwort auf die kollatzvermutung finden ja hält das auf jeder Zahl oder nicht ja das könnte man sich daraus dann bauen ja also es
- liegt einfach daran dass die Bedingung von while schleifen und das was in der while Schleife passiert das kann einfach zu unvorhersehbar sein als dass man
- schon nach endlicher Zeit sagen kann ob das jemals anhalten wird oder nicht okay jetzt aber zurück zu unserem Beweis wir wollen zeigen es gibt diesen
- haltealgorithmus nicht und zu zeigen dass es ein solchen Algorithmus nicht geben kann das klingt erstmal schwierig ja man müsste ja irgendwie von jedem
- einzelnen Algorithmus zeigen dass der nicht das tut was das halte was der haltealgorithmus tun soll aber wie kann man das zeigen man kann es mit demem
- widerspruchsbeweis zeigen ja wir nehmen an es gebe den haltealgorithmus der also für jedes Programm und jede Eingabe das hier entscheiden kann und dann bauen wir
- uns damit ein neues Programm und das jetzt eigentlich die interessante Idee an dem BEWEI dieses neue Programm das soll über sich selbst herausfinden ob es
- anhalten wird oder nicht das soll schon herausfinden ob es selber anhält oder nicht bevor es überhaupt angehalten hat ja also während es noch läuft und dann
- kann es abhängig von dem was es rausgefunden hat noch weitere Entscheidung treffen ja und dann sagen wir einfach folgendes wenn du über dich
- selbst herausgefunden hast dass du anhältst dann geh jetzt in der entlussschleife und wenn du über dich selbst herausgefunden hast dass du nicht
- anhältst ja niemals anhältst dann halte jetzt einfach sofort an und dann wird klar die Antwort die uns der halteralgor gegeben hat die muss falsch gewesen sein
- ja und dann hat der haltealgorithmus also in diesem Fall versagt ja das heißt der haltealgoritmus der kann nicht in jedem Fall die richtige Antwort liefern
- das ist die Idee ja und dieses neue Programm das bauen wir uns jetzt ja es wird also den haltealgorithmus als Unterprogramm benutzen dieses Programm
- was für uns jetzt hier drum rumbauen das nennen wir mal u das Unmögliche Programm also u soll ja jetzt über sich selbst herausfinden ob es hält oder nicht ja
- dann machen wir das doch so u bekommt als Eingabe ein Programmcode da werden wir dann am Ende das Programm u selbst nehmen ja dann wird also u mit der
- Eingabe u aufgerufen ja das heißt hier wollen wir dann gucken ob u auf Eingabe u hält das heißt was wir hier tun wir nehmen eine Eingabe hier oben eine
- Eingabe die nenne ich jetzt mal P und diese Eingabe P die tun wir sowohl hier als auch hier rein ja also u tut einfach folgendes ist das es nimmt die Eingabe
- und tut die erstmal in beide Eingänge hier vom haltealgorithmus rein dann stimmt das natürlich hier unten nicht mehr P hält
- auf Eingabe ja das ist dann auch P und hier P hält nicht auf P und was hatten wir uns dann überlegt ja wenn P auf P hält dann wollen wir nicht halten also
- gehen wir hier in der Endlosschleife und wenn wir raus hatten P hält nicht auf P dann wollten wir terminieren ja und die Ausgabe hier ist
- völlig egal es geht uns nur darum ob das hält oder nicht das Programm so und jetzt noch mal kurz die Frage was genau bedeutet das dass wir P reinstecken hier
- und weiterleiten nach da nach da wir stellen uns einfach vor sämtliche unserer Programme nehmen nur Strings als Eingabe ja also ein Programm P kann z.B
- als Quellcode eingegeben werden ja und der halteralgorithmus der soll das Programm P auch als Quellcode erhalten und die Eingabe als ein String ja und
- der qucode ist auch ein String ja das heißt hier ist ein String hier ist String und das dann okay dass wir einfach hier einen String reinnehmen den
- String tun wir in beide Eingänge des haltealgorithmus rein und der läuft dann wie gewohnt ab dass wir nur Strings nehmen das ist auch keine Einschränkung
- man kann ja jede beliebige Eingabe von irgendeinem Programm immer als String codieren ja das sind alles nur Bits und Bits kann man auch als Strings
- interpretieren okay und was tun wir jetzt wir hatten diesen haltealgorithmus ja von wir annehmen es gibt ihn wirklich ja dann können wir auch dieses Programm
- u hier schreiben ja das hat nur ein paar Veränderungen am Anfang es nimt eine Eingabe tut die in beide Eingänge rein und ab abhängig davon was der
- haltealgorus ausgibt tut es dann noch am Ende so ein bisschen was ja aber wenn der halteralgorithmus existiert dann gibt's davon einen Quellcode dann gibt's
- auch von U einen Quellcode und den kennen wir dann ja wenn wir den vmaltealgorithmus kennen würden dann würden wir auch den Quellcode von U
- kennen und dann können wir den hier ob reinstecken ja wir könnten dann hier oben einfach das Programm u reinstecken und dann gucken wir mal was passiert wir
- rufen dann also u mit der Eingabe u auf dann geben wir hier u und U rein der haltealgorithmus sagt dann entweder hält das Programm u auf der Eingabe u dann
- gehen wir aber in der endlusschleife ja Moment das kann doch nicht sein wenn u auf der Eingabe u hält dann müssen wir doch hier rauskommen der
- halteralgorithmus sagt dann aber wir gehen in end Schleife andersrum wenn der haltealgorithmus uns sagt das Programm u wird nicht auf U halten ja sprich
- müssten eigentlich in diesem Fall hier landen dann hält unser Programm aber an ja das heißt ganz egal ob u auf U hält oder ob u auf U nicht hält der
- haltealgorithmus hat in beiden Fällen die falsche Antwort geliefert ja und das heißt der haltealgorithmus der kann nicht in allen Fällen die richtige
- Antwort liefern es kann keinen solchen Algorithmus geben und dieser Beweis hier ist tatsächlich eigentlich derselbe Beweis den Alen ting der das als erstes
- bewiesen hat der den tatsächlich auch gebracht hat allerdings ist das hier in einer sehr anschaulichen Form und nicht in so einer
- mathematischen Form ja also in der mathematischen Form kann man vielleicht kaum noch wieder erkennen dass es sich hier um denselben Beweis handelt aber
- das ist genau die Kernidee des Beweises gewesen also ein Programm u findet heraus über sich selbst was es tun wird wenn es sich selbst als Eingabe
- bekommt ja und abhängig davon trifft noch eine Entscheidung die einfach diese Antwort hier falsch macht genau und dann haben wir gezeigt das halteproblem ist
- unentscheidbar das heißt es gibt keinen Algorithmus der immer die richtige Antwort liefert ja der auf jeder Eingabe entweder Ja oder Nein sagt und das es
- dann auch stimmt ja aber wie ist es mit semientscheidbarkeit semientscheidbar hieß ja hier noch mal ein sem Entscheidungsverfahren das soll nur in
- den ja Fällen nach endlicher Zeit die Antwort liefern und in den neinfällen kann es auch unendlich lange weiterlaufen und das halteproblem ist in
- gewisser Weise das prototypische semi entscheidbare Problem denn was kann man einfach tun wenn wir ein semientscheidungsverfahren haben wollen
- ja das ganze können wir dann ein semialtealgorithmus nennen Programm P Eingabe e falls P auf der Eingabe e hält soll er irgendwann ja Antwort und sonst
- nicht terminieren ja und die Antwort dafür ist ganz einfach wir simulieren einfach das Programm P auf der Eingabe e ja wir müssen nur P auf E simulieren und
- wenn diese Simulation irgendwann endet dann hat P offenbar auf E gehalten und wir können ja antworten und falls diese Simulation nie endet ja dann hält P halt
- nicht auf E und dann hält auch unser Algorithmus hier unser semientscheidungsverfahren niemals an ja also das haltproblem ist das typische
- semi entscheidbare Problem okay und jetzt abschließend vielleicht noch ein paar Worte dazu warum das halteproblem so besonders ist in der theoretischen
- Informatik na ja es ist einfach ein Problem von dem man ziemlich direkt zeigen kann dass es unentscheidbar ist ja es ist erstmal gar nicht klar dass es
- unentscheidbare Probleme gibt aber das halteproblem das ist unentscheidbar und das kann man halt mit dieser Konstruktion hier ziemlich direkt zeigen
- und wenn man das dann erstmal hat wenn man ein unentscheidbares Problem hat dann kann man von ganz vielen weiteren Problemen zeigen dass sie unentscheidbar
- sind und zwar mit einer Technik die nennt sich Reduktion also wenn man dann für irgendein neues Problem zeigen möchte dass es auch unentscheidbar ist
- dann versucht man das halteproblem auf dieses neue Problem zu reduzieren das heißt also wenn man dann eine solche Übersetzung hätte ja die jede Eingabe
- für das halteproblem in der Eingabe von unserem neuen Problem übersetzt ja so dass immer die jahinstanzen also immer dann wenn das Programm P auf der Eingabe
- e hält ja wenn die Antwort ja lautete soll auch hier in einer Eingabe x übersetzt werden die in unserem neuen Problem eine jinanz ist ja unser neues
- Problem ist auch ein Entscheidungsproblem was wieder Ja und Nein Instanzen hat und andersrum die neininstanzen sollen auch auf
- neininstanzen also alle Programme plus Eingabe so dass das Programm mit der Eingabe nicht hält das soll hier in eine neininstanz übersetzt werden ja wenn es
- eine berechenbare Übersetzung gibt ja also diese Übersetzung muss auch von irgendeinem Programm machbar sein und
- wenn es dann auch noch für dieses neue Problem einen solchen Algorithmus gäbe der das entscheidet dann könnte man durch Verknüpfung der beiden Programme
- hier auch das halteproblem entscheiden aber wir wissen schon dass es unentscheidbar ja und dann kann man folgern das es auch für unser neues
- Problem einen solchen Algorithmus hier nicht geben kann und das halteproblem das eignet sich sehr gut dafür also man kann oft vom te Problem auf andere
- Probleme reduzieren um dann von denen auch zu zeigen dass sie nicht entscheidbar sind ja und diese Übersetzung hier die nennt sich
- Reduktion aber Reduktion werden dann noch mal ein eigenes Thema hier ging es erstmal nur darum dass das haltepr unentscheidbar ist und wir wissen jetzt
- auch warum es unentscheidbar ist und wir wissen aber auch dass es semi entscheidbar ist und sogar das typische semi entscheidbare Problem das sollte
- man hier aus diesem Video mitnehmen
Zum Nachlesen
HalteproblemDas Halteproblem beschreibt eine Frage aus der theoretischen Informatik. Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt …
EntscheidbarkeitIn der theoretischen Informatik heißt eine Eigenschaft auf einer Menge ... (Halteproblem) oder die Funktionsgleichheit zweier Programme (Äquivalenzproblem).
Theoretische InformatikIhre Inhalte sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeits- und Komplexitätstheorie, aber auch die Logik und formale …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …