Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Das Halteproblem ist unentscheidbar
Das Wichtigste aus dem Video
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