Berechenbarkeit #30 - Wortproblem und Halteproblem sind unentscheidbar
NLogSpace
https://www.youtube.com/watch?v=SR1tnOZK3a0

Transkript (automatisch erstellt)

0:00 herzlich willkommen zu diesem video wir wollen uns jetzt von zwei weiteren wichtigen entscheidungsprozessen dass sie unentschuldbar sind nämlich zum
0:09 einen das wort problem wenn man auch das allgemeine wort problem werden schon letztes mal das spezielle wort problem kennen gelernt also das allgemeine wort
0:16 problem und das halte problem diese beiden probleme sind unentschuldbar also hier sind diese beiden probleme zum vergleich das spezielle wort problem
0:25 daten wir als eingabe nur eine touring maschinen dtm und wir haben uns gefragt akzeptiert diese dtm ein ganz bestimmtes wort nämlich code von der ton maschine
0:36 selbst ja das wort problem ist ein viel allgemeines und auch irgendwie viel natürlicheres problem ja wer interessiert sich schon dafür ob eine
0:45 tormaschine ausgerechnet ihre eigene co dio akzeptiert beim allgemeinen wort problem kriegt man als eingabe nicht nur eine tormaschine sondern auch noch
0:55 irgendein wort und fragt sich akzeptiert diese touren maschine dieses wort ja also ein viel allgemeiner formuliertes problem als das spezielle
1:04 wort problem und weil das so viel allgemeiner wirkt ja dann muss es ja auch irgendwie schwieriger sein ja das ist die richtige
1:11 intuition an dieser stelle wenn wir schon nicht für ein bestimmtes wort ein ganz bestimmtes wort entscheiden können ob das akzeptiert wird naja dann kann es
1:21 ja auch nicht entschuldbar sein wenn man sogar dass ich noch ein wort aussuchen darf ja dann es kann kein algorithmus geben der für jedes für jede tormaschine
1:29 und für jedes wort die richtige antwort liefert es gibt ja nicht mal ein algorithmus der für eine beliebige tormaschine und dieses konkrete wort die
1:38 richtige antwort liefert zwischen diesen beiden problemen also dem speziellen wort problem und dem allgemeinen wort problem dann besteht also so eine art
1:45 beziehung und diese beziehung das werden wir im nächsten video dann ganz formal machen da werden wir zeigen was das formal ist
1:53 diese beziehung nämlich eine sogenannte reduktion produktion ist eine beziehung zwischen zwei entscheidungs problemen die uns erlaubt zu schlussfolgern wenn
2:01 eines also wenn das erste von diesen beiden problemen entscheidbar ist das dann auch das zweite unentschieden bar ist ja dass nur schon mal vorweg
2:11 werden aber in diesem video noch nicht konkret über diese reduktionen reden auch wenn wir bereits reduktion durchführen in diesem video ja formal
2:19 machen das aber erst im nächsten video und sobald wir dann gezeigt haben dass das wort problem unentschuldbar ist werden wir noch eine weitere reduktion
2:27 machen da werden wir dann daraus folgern dass das so genannte halte problem unentschuldbar ist das hat genau wie das wort problem als eingabe eine touring
2:36 maschine und ein wort und wir fragen uns aber nicht ob das wort akzeptiert wird sondern wir fragen uns nur hält diese touring maschine an
2:44 irgendwann wenn man sie mit dieser eingabe ausführt und wenn euch das jetzt wieder sehr abstrakt vorkommt irgendwie probleme mit touring maschinen und
2:52 letztendlich fragen uns ja auch gibt es eine tormaschine die diese touring maschinen als eingabe bekommt ja dann stellt euch einfach wieder vor eure
3:00 lieblings programmiersprache also stellt euch statt einer dtm vor einen quelltext in eurer lieblings programmiersprache von einer funktion die den string
3:11 entgegennimmt und insulin zurückgibt trawler falls der tu es akzeptieren falls es verwerfen dh die eingabe für dieses problem während quelltext zb c++
3:22 von einer funktion dieser string entgegennimmt und auch noch der string denen sie entgegennehmen soll und die frage ist gibt diese funktionen
3:31 irgendwann trug zurück oder nicht und hier ist entsprechend nur die frage hält diese funktion irgendwann an also läuft irgendwann durch oder gelangt sie
3:39 irgendwie eine endlosschleife so aber jetzt fangen wir mal an jetzt machen wir diese argumentation noch mal ganz konkret warum folgt ist wenn das
3:46 spezielle wort problem unentschuldbar ist das dann auch das allgemeine wort problem unentschuldbar ist also wir könnten ja mal an nehmen das wort
3:53 problem wäre entscheidend war das wird jetzt ein widerspruchs beweis mitnehmen an das wort problem wäre in scheinbar so das allgemeine dann folgen wir daraus
4:03 dass man mit diesem entscheidungsverfahren für das allgemeine wort problem auch das spezielle problem lösen könnte aber von
4:10 dem wissen wir schon dass es unentschuldbar ist also wenn das wort problem entscheidbar wäre dann gäbe es eine entscheidungsverfahren so
4:17 entscheidungsverfahren für das parkproblem das nimmt also entgegen und todesmaschine m jw natürlich jetzt code von m natürlich
4:25 kriegt immer eine codierung einer tormaschine als eingabe kann ja no strings entgegennehmen und ein wort wie meinetwegen trennzeichen irgendwie
4:33 dazwischen das interessiert uns jetzt mal nicht unser niveau annehmen das ist wirklich ein entscheidungsverfahren dann liefert das immer nach etlicher zeit die
4:39 richtige antwort also ist akzeptiert falls das wort in der von bekannten sprache liegt und das verwirft nach etlicher zeit falls das wort nicht in
4:50 der von markanten sprache liegt und das gerät niemals in der endlos stadt für die entscheidungsverfahren terminieren immer nach etlicher zeit so das ist
4:58 unsere annahme dass es ein solches entscheidungsverfahren gibt und diese entscheidungsverfahren das können wir jetzt benutzen um einen
5:05 entscheidungsverfahren für das spezielle wort problem zu bauen beim speziellen wort problem da bekommen wir als eingabe nur den code von der natur die maschine
5:14 und wir fragen uns akzeptiert diese tormaschine ihre eigene codierung also akzeptiert diese tormaschine das wort code von m
5:22 genau diese frage können wir das lösen indem wir in dieses entscheidungsverfahren hier zweimal code von m reinstecken also einmal kohl von m
5:30 für die tormaschine m und dann noch einmal code von m für das wort was uns interessiert ob es akzeptiert wird oder nicht das heißt dass
5:38 entscheidungsverfahren für das spezielle wort problem würde dann so aussehen wir bekommen irgendeinen string als eingabe und jeder string war noch unsere
5:45 annahme auch kot von natori maschine ja wir schreiben dieses team einfach zweimal hintereinander hin mit dem trennzeichen in der mitte ja schreiben
5:53 hier code von m & grund von m noch mal hin ja einen string verdoppeln das kann man offensichtlich machen in endlicher zeit ja den zwei mal hintereinander aus
6:01 bahn schreiben und genau mit dieser eingabe lassen wir dann dieses entscheidungsverfahren hier laufen nach unserer annahme sagt uns dass
6:08 entscheidungsverfahren danach endlicher zeit ob die maschine m das wort code von m akzeptiert oder nicht und das ist genau die frage die
6:16 wir uns beim speziellen wort problem gestellt haben also wäre das allgemeine wort problem entscheidbar dann würde uns das auf diese weise auch einen
6:25 algorithmus einen entscheidungsverfahren für das spezielle wort problem liefern das ist aber ohne entscheid war wissen wir schon das heißt das ein widerspruch
6:33 das heißt unsere an arme war falsch unserer annahme dass das wort problem entscheidbar ist das heißt das allgemeine wort problem ist
6:41 unentschuldbar und das zeichnen wir dann in unsere grafik einfach mal so mit ein ja wir haben gerade eine reduktion gemacht auch wenn wir noch überhaupt
6:48 nicht wissen was eine reduktion eigentlich ist neben der reduktion durchgeführt vom speziellen wort problem auf das allgemeine wort problem was ich
6:55 mal mit wp hier nur ob kürze und damit wissen wir das wort problem das allgemeine wort problem ist ebenfalls unentscheiden machen jetzt auch noch
7:04 weiter wir reduzieren jetzt noch das wort problem auf das halte problem wollen also zeigen dass halte problem ist unentschuldbar
7:12 auch das machen jetzt wieder mit zum widerspruch beweis wir nehmen erst mal an das halt problem wäre entscheidbar dh es gebe irgend so ein
7:20 entscheidungsverfahren das bekommt als eingabe motoren maschine und ein wort und das gibt uns auch endlich zeit die richtige antwort und zwar das sagt nach
7:28 endlich hat seine jahre als fw irgendwann anhält und das hat nach endlicher zeiten ein falls mw niemals an hält ja und so
7:37 intuitiv gesehen ist dieses dieses nein hier nach etlicher zeit das ist also der grund warum das unentschuldbar ist ja wie können wir nach etlicher zeit
7:47 herausfinden ob diese tormaschine niemals anhalten wird ja das ist sozusagen das schwierige und da liegt so intuitiv gesehen die
7:55 schwierigkeit in diesem von diesem problem aber wir nehmen jetzt einfach mal an es gebe dieses entscheidungsverfahren wir wollen zeigen
8:02 dann wäre auch das wort problem entscheidend war das heißt wir müssen uns fragen wie können wir dieses entscheidungsverfahren hier benutzen um
8:11 das wort problem für eine beliebige tormaschine m und beliebiges wort wie zu lösen ja finden wir irgendwie das wort problem in diesem problem wieder könnte
8:20 man sich fragen also für das wort problem bekommen wir als eingabe einen touring maschinen und ein wort wir würden jetzt gern wissen akzeptiert das
8:30 wort w ja was wir zur verfügung haben ist ein verfahren das sagt uns für jede tour in maschine und für jedes wort hält diese tolle maschine da irgendwann an
8:38 können vielleicht die maschine m so umbauen dass sie genau die wörter akzeptiert bei denen sie auch anhält oder anders
8:46 gesagt dass sie bei allen wörtern die sie verwirft nicht anhält und das ist gar nicht so schwierig wenn man sich das mal überlegt ja wenn wir
8:54 irgendeine touren maschine haben also irgendwo eine tormaschine hier ja die können wir ganz leicht umbauen in eine tormaschine die immer noch genau die
9:02 gleichen wörter akzeptiert die aber bei allen worten die sie verwirft in einer endlosschleife geht ja die also nie mehr verwirft und anhält
9:12 ja wir gucken uns einfach alle zustände an die verwerfen sind in dem fall ist es nur zustand 1 und dann gucken wir uns alle symbole an bei denen die
9:21 tormaschine stoppen würde also alle symbole für die wir hier keine ausgehenden kante haben wenn das alphabet sagen wir mal nur aus
9:28 0 1 und blanken besteht dann wir haben hier keine ausgehende einst kannte das heißt wenn wir in diesem zustand hier eine 1 lesen das sind alle fälle in dem
9:40 diese touring maschinen wort verwirft und in dem fall gehen wir jetzt einfach in eine endlosschleife das könnte man so machen indem man sagt
9:48 wenn wir in diesem zustand der einst lesen also dass nur wo sie eigentlich sonst angehalten hat dann lassen wir die einen verstehen und bewegen uns auch
9:55 nicht und gehen in diesen neuen zustand und in dem machen wir nichts anderes als für immer wieder hier diese selbe tradition zu benutzen das heißt wir
10:03 laufen in eine endlosschleife und wenn es mehrere solche kombinationen aus zustand und eingabe symbol gibt wo die todesmaschine anhalten und verwerfen
10:12 würde dann machen wir halt von jeder solchen kombinationen einen übergang in dieser endlosschleife hier und jetzt ist so wenn uns für diese neue touren
10:21 maschine fragen ob sie auf einem wort wie irgendwann anhält dann ist die antwort genau die gleiche wie auf die frage ob die ursprüngliche maschine das
10:33 wort akzeptiert das heißt für das entscheidungsverfahren für das wort problem würden wir folgendes machten wir gucken uns an welche touring maschine m
10:42 wie hier bekommen haben wir konstruieren eine neue touren maschine im strich ja das war diese hier die konstruieren will genau wm erstmal alles außer immer wenn
10:52 man hält und verwirft dann geht einem strich stattdessen in einer entführung wenn wir jetzt diese neue touren maschine im strich und das ursprüngliche
11:01 wort w hier rein geben dann gucken wir mal was passiert also angenommen wir hatten vorher ja instanz von unserem problem also eine tormaschine m & w so
11:11 dass ihm das wollen wir akzeptiert naja dann wird auch im strich das wort akzeptieren weil wir hier in einer akzeptierenden stopp konfiguration
11:20 anhalten da haben wir nichts verändert dran ja das heißt wir werden immer noch irgendwann anhalten das heißt wenn wir jetzt dieses
11:27 entscheidungsverfahren herausführen mit dieser modifizierten maschine dann werden wir ja antworten und ja ist auch die richtige antwort auf die frage ob
11:36 die maschine im das wort w akzeptiert obwohl wir hier nur gefragt haben hält der maschine im strich an ja das ist trotzdem die richtige antwort
11:44 die herauskommt genauso ist es bei neuen instanzen das wird auch die richtige antwort sein wenn wir hier einen neuen instanz hatten
11:51 also eine tormaschine m die das wort weh nicht akzeptiert dann gibt es jetzt zwei möglichkeiten warum sie es nicht akzeptiert hat die eine
12:00 möglichkeit ist dass die tormaschine m auf dem wort wie gar nicht angehalten hat ja wir haben dann zwei möglichkeiten entweder hält sich nicht an oder sie
12:10 hält an in der verwerfung stock konfirmation machen erstmal die eine möglichkeit wenn die maschine m auf dem wollen wir gar nicht angehalten hat dann
12:19 wird auch die maschine im strich nicht anhalten und wenn wir dann dieses entscheidungsverfahren für einem strich
12:25 ausführen dann wird halt nein rauskommen und nein ist jetzt auch die richtige antwort denn man will ja nicht akzeptiert und jetzt
12:33 kommt der letzte und entscheidende fall wenn es das wort wie nicht akzeptiert hat weil es irgendwann angehalten hat in einer verwerfen stock konfiguration wie
12:43 zum beispiel in diesem zustand hier wenn wir eine 1 lesen die antwort hier ist also nein das wollte es nicht in der sprache
12:50 dann wird jetzt aber auch diese maschine im strich auf dem vw nicht anhalten denn wir haben jetzt da extra dieser endlosschleife angebaut das heißt wir
12:58 werden auch in diesem fall hier gelang also um nicht zu verwirren schreibe ich jetzt mal hier überall im strich hin weil wir jetzt in unserem konkreten
13:06 problem wie wir diese entscheidungsverfahren verwenden ist jetzt im strich die maschine die wir hier rein getan haben ja wir haben im
13:14 strich und das wort weh getan und ja das ganze wäre jetzt ein entscheidungsverfahren für das wort problem bekommen code von natur maschine
13:23 m & w wir modifizieren m so ein bisschen zur natur maschine im strich aber das kann man machen ja so ein paar mond manipulationen an der tormaschine
13:35 vornehmen sind unendlich viele solche kombinationen und ist man endlich viele änderungen durchgehend das dauert nun endlich lange nach etlicher zeit haben
13:44 wir also den code von dem strich berechnet und stecken das ganze hier in dieses entscheidungsverfahren rein und das gibt dann auch nach etlicher zeit ja
13:53 oder nein aus also akzeptiert oder verwirft und die antwort ist genau die richtige auf die ursprüngliche frage nämlich ob die maschine mjb akzeptiert
14:03 das heißt unter unserer annahme dass das halt problem entscheidbar wäre wäre dann auch das wort problem entscheid war aber wir haben gesehen dass wahre problem ist
14:12 unentschuldbar das ist ein widerspruch das heißt unsere annahme war falsch dh das halt problem muss ebenfalls unentschuldbar sein
14:20 das heißt wir können das halt problem ebenfalls hier eintragen in die liste unserer ohne entscheid barren probleme und dieser teil der deutet an dass wir
14:28 hier eine reduktion gerade durchgeführt haben vom wort problem auf das problem vielleicht habt ihr schon so eine
14:34 leichte idee was eine reduktion ist ja irgendwie eine übersetzung vom einen in das andere probleme aber was genau das klären wir im
14:42 nächsten video