Das Halteproblem ist unentscheidbar
NLogSpace
https://www.youtube.com/watch?v=_T4okKt2A18

Transkript (automatisch erstellt)

0:00 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
0:08 ist und danach werden wir uns überlegen warum es sich bei dem halteproblem um ein unentscheidbares Problem handelt aber immerhin um ein semientscheidbares
0:17 Problem okay stellen wir uns mal folgende Situation vor wir sind mal wieder am Programmieren haben irgendein Programm geschrieben was irgendwas
0:25 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
0:35 ä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
0:43 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
0:52 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
1:01 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
1:09 einen Fehler gemacht haben bei den wi schleifenbedingungen ja damit würden wir wahrscheinlich auch gleichzeitig noch allen anderen Programmierern auf der
1:15 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
1:24 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
1:32 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
1:42 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
1:52 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
2:01 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
2:11 unserem haltealgorithmus aber leider werden wir enttäuscht ja ein solchenten haltealgorithmus gibt es nicht ja das ist das Resultat aus der theoretischen
2:21 Informatik das halteproblem ist unentscheidbar das heißt es gibt keinen Algorithmus der für jedes Programm P und jede Eingabe e
2:30 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
2:38 ü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
2:46 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
2:55 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
3:05 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
3:18 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
3:27 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
3:35 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
3:45 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
3:54 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
4:03 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
4:12 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
4:20 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
4:29 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
4:37 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
4:47 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
4:56 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
5:06 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
5:13 selbst herausgefunden hast dass du anhältst dann geh jetzt in der entlussschleife und wenn du über dich selbst herausgefunden hast dass du nicht
5:22 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
5:32 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
5:40 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
5:49 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
6:00 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
6:10 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
6:21 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
6:31 und tut die erstmal in beide Eingänge hier vom haltealgorithmus rein dann stimmt das natürlich hier unten nicht mehr P hält
6:40 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
6:51 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
6:59 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
7:09 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
7:19 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
7:30 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
7:37 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
7:46 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
7:55 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
8:03 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
8:12 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
8:21 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
8:27 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
8:36 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
8:48 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
8:56 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
9:07 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
9:16 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
9:24 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
9:33 bewiesen hat der den tatsächlich auch gebracht hat allerdings ist das hier in einer sehr anschaulichen Form und nicht in so einer
9:42 mathematischen Form ja also in der mathematischen Form kann man vielleicht kaum noch wieder erkennen dass es sich hier um denselben Beweis handelt aber
9:51 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
10:02 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
10:11 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
10:20 dann auch stimmt ja aber wie ist es mit semientscheidbarkeit semientscheidbar hieß ja hier noch mal ein sem Entscheidungsverfahren das soll nur in
10:31 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
10:40 gewisser Weise das prototypische semi entscheidbare Problem denn was kann man einfach tun wenn wir ein semientscheidungsverfahren haben wollen
10:49 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
11:00 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
11:10 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
11:20 nicht auf E und dann hält auch unser Algorithmus hier unser semientscheidungsverfahren niemals an ja also das haltproblem ist das typische
11:29 semi entscheidbare Problem okay und jetzt abschließend vielleicht noch ein paar Worte dazu warum das halteproblem so besonders ist in der theoretischen
11:37 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
11:46 unentscheidbare Probleme gibt aber das halteproblem das ist unentscheidbar und das kann man halt mit dieser Konstruktion hier ziemlich direkt zeigen
11:55 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
12:03 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
12:11 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
12:21 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
12:31 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
12:41 Problem ist auch ein Entscheidungsproblem was wieder Ja und Nein Instanzen hat und andersrum die neininstanzen sollen auch auf
12:47 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
12:58 eine berechenbare Übersetzung gibt ja also diese Übersetzung muss auch von irgendeinem Programm machbar sein und
13:06 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
13:14 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
13:21 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
13:30 Probleme reduzieren um dann von denen auch zu zeigen dass sie nicht entscheidbar sind ja und diese Übersetzung hier die nennt sich
13:38 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
13:47 auch warum es unentscheidbar ist und wir wissen aber auch dass es semi entscheidbar ist und sogar das typische semi entscheidbare Problem das sollte
13:56 man hier aus diesem Video mitnehmen