Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Berechenbarkeit #30 - Wortproblem und Halteproblem sind unentscheidbar
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 105 Zeilen
- herzlich willkommen zu diesem video wir wollen uns jetzt von zwei weiteren wichtigen entscheidungsprozessen dass sie unentschuldbar sind nämlich zum
- 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
- problem und das halte problem diese beiden probleme sind unentschuldbar also hier sind diese beiden probleme zum vergleich das spezielle wort problem
- 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
- 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
- tormaschine ausgerechnet ihre eigene co dio akzeptiert beim allgemeinen wort problem kriegt man als eingabe nicht nur eine tormaschine sondern auch noch
- irgendein wort und fragt sich akzeptiert diese touren maschine dieses wort ja also ein viel allgemeiner formuliertes problem als das spezielle
- wort problem und weil das so viel allgemeiner wirkt ja dann muss es ja auch irgendwie schwieriger sein ja das ist die richtige
- 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
- 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
- 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
- richtige antwort liefert zwischen diesen beiden problemen also dem speziellen wort problem und dem allgemeinen wort problem dann besteht also so eine art
- beziehung und diese beziehung das werden wir im nächsten video dann ganz formal machen da werden wir zeigen was das formal ist
- diese beziehung nämlich eine sogenannte reduktion produktion ist eine beziehung zwischen zwei entscheidungs problemen die uns erlaubt zu schlussfolgern wenn
- 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
- werden aber in diesem video noch nicht konkret über diese reduktionen reden auch wenn wir bereits reduktion durchführen in diesem video ja formal
- 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
- 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
- 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
- irgendwann wenn man sie mit dieser eingabe ausführt und wenn euch das jetzt wieder sehr abstrakt vorkommt irgendwie probleme mit touring maschinen und
- letztendlich fragen uns ja auch gibt es eine tormaschine die diese touring maschinen als eingabe bekommt ja dann stellt euch einfach wieder vor eure
- lieblings programmiersprache also stellt euch statt einer dtm vor einen quelltext in eurer lieblings programmiersprache von einer funktion die den string
- 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++
- von einer funktion dieser string entgegennimmt und auch noch der string denen sie entgegennehmen soll und die frage ist gibt diese funktionen
- 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
- irgendwie eine endlosschleife so aber jetzt fangen wir mal an jetzt machen wir diese argumentation noch mal ganz konkret warum folgt ist wenn das
- spezielle wort problem unentschuldbar ist das dann auch das allgemeine wort problem unentschuldbar ist also wir könnten ja mal an nehmen das wort
- 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
- dass man mit diesem entscheidungsverfahren für das allgemeine wort problem auch das spezielle problem lösen könnte aber von
- dem wissen wir schon dass es unentschuldbar ist also wenn das wort problem entscheidbar wäre dann gäbe es eine entscheidungsverfahren so
- entscheidungsverfahren für das parkproblem das nimmt also entgegen und todesmaschine m jw natürlich jetzt code von m natürlich
- kriegt immer eine codierung einer tormaschine als eingabe kann ja no strings entgegennehmen und ein wort wie meinetwegen trennzeichen irgendwie
- dazwischen das interessiert uns jetzt mal nicht unser niveau annehmen das ist wirklich ein entscheidungsverfahren dann liefert das immer nach etlicher zeit die
- 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
- 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
- unsere annahme dass es ein solches entscheidungsverfahren gibt und diese entscheidungsverfahren das können wir jetzt benutzen um einen
- 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
- und wir fragen uns akzeptiert diese tormaschine ihre eigene codierung also akzeptiert diese tormaschine das wort code von m
- 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
- 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
- entscheidungsverfahren für das spezielle wort problem würde dann so aussehen wir bekommen irgendeinen string als eingabe und jeder string war noch unsere
- annahme auch kot von natori maschine ja wir schreiben dieses team einfach zweimal hintereinander hin mit dem trennzeichen in der mitte ja schreiben
- 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
- bahn schreiben und genau mit dieser eingabe lassen wir dann dieses entscheidungsverfahren hier laufen nach unserer annahme sagt uns dass
- entscheidungsverfahren danach endlicher zeit ob die maschine m das wort code von m akzeptiert oder nicht und das ist genau die frage die
- 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
- 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
- das heißt unsere an arme war falsch unserer annahme dass das wort problem entscheidbar ist das heißt das allgemeine wort problem ist
- 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
- nicht wissen was eine reduktion eigentlich ist neben der reduktion durchgeführt vom speziellen wort problem auf das allgemeine wort problem was ich
- 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
- weiter wir reduzieren jetzt noch das wort problem auf das halte problem wollen also zeigen dass halte problem ist unentschuldbar
- 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
- 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
- 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
- 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
- herausfinden ob diese tormaschine niemals anhalten wird ja das ist sozusagen das schwierige und da liegt so intuitiv gesehen die
- schwierigkeit in diesem von diesem problem aber wir nehmen jetzt einfach mal an es gebe dieses entscheidungsverfahren wir wollen zeigen
- 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
- 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
- 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
- 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
- können vielleicht die maschine m so umbauen dass sie genau die wörter akzeptiert bei denen sie auch anhält oder anders
- 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
- 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
- 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
- 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
- tormaschine stoppen würde also alle symbole für die wir hier keine ausgehenden kante haben wenn das alphabet sagen wir mal nur aus
- 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
- 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
- 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
- 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
- laufen in eine endlosschleife und wenn es mehrere solche kombinationen aus zustand und eingabe symbol gibt wo die todesmaschine anhalten und verwerfen
- 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
- 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
- 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
- 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
- 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
- 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
- dass ihm das wollen wir akzeptiert naja dann wird auch im strich das wort akzeptieren weil wir hier in einer akzeptierenden stopp konfiguration
- 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
- entscheidungsverfahren herausführen mit dieser modifizierten maschine dann werden wir ja antworten und ja ist auch die richtige antwort auf die frage ob
- 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
- die herauskommt genauso ist es bei neuen instanzen das wird auch die richtige antwort sein wenn wir hier einen neuen instanz hatten
- 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
- 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
- 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
- wird auch die maschine im strich nicht anhalten und wenn wir dann dieses entscheidungsverfahren für einem strich
- ausführen dann wird halt nein rauskommen und nein ist jetzt auch die richtige antwort denn man will ja nicht akzeptiert und jetzt
- 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
- zum beispiel in diesem zustand hier wenn wir eine 1 lesen die antwort hier ist also nein das wollte es nicht in der sprache
- 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
- 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
- problem wie wir diese entscheidungsverfahren verwenden ist jetzt im strich die maschine die wir hier rein getan haben ja wir haben im
- 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
- 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
- vornehmen sind unendlich viele solche kombinationen und ist man endlich viele änderungen durchgehend das dauert nun endlich lange nach etlicher zeit haben
- 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
- 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
- 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
- unentschuldbar das ist ein widerspruch das heißt unsere annahme war falsch dh das halt problem muss ebenfalls unentschuldbar sein
- 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
- hier eine reduktion gerade durchgeführt haben vom wort problem auf das problem vielleicht habt ihr schon so eine
- leichte idee was eine reduktion ist ja irgendwie eine übersetzung vom einen in das andere probleme aber was genau das klären wir im
- nächsten video
Zum Nachlesen
HalteproblemDas Halteproblem beschreibt eine Frage aus der theoretischen Informatik. Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt …
TuringmaschineEine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach …