YT YouTube2Text

YouTube2Text → Transcripts → Unentscheidbarkeit und das Halteproblem

Unentscheidbarkeit und das Halteproblem — Transcript

by Prof. Markus · 6,817 words · 1,156 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00so willkommen zurück es geht heute um
0:03zeitreisen und natürlich und touring
0:06maschinen
0:07wir werden uns beschäftigen mit dem
0:09interessanten thema der entscheid
0:12barkeit einnahme ist marcus krietsch
0:14willkommen zurück zu diesem kleinen kurs
0:17zum thema automaten und auch formale
0:19sprachen momentan mehr automaten und
0:22grundlagen der informatik in form der
0:25touring maschine beim letzten mal hatte
0:27ich ihnen bereits eine ganze menge über
0:29touring maschinen erklärt wir haben
0:30gelernt dass laut church touring these
0:34alles was berechenbar ist auch mit
0:37touring maschinen berechnet werden kann
0:39das heißt es ist eines von vielen
0:43universellen berechnungsmodellen und das
0:47gibt uns natürlich eine ganz
0:49interessante und besondere handhabe zu
0:52untersuchen was unsere computer
0:54eigentlich können die intuition die
0:59viele menschen natürlich zunächst haben
1:01ist dass unsere computer alles können
1:06mit entsprechenden aufwand und
1:08ressourcen
1:09das ist natürlich falsch wieder als
1:11informatiker wissen und in diesem video
1:14wäre ich ihnen auch konkret zeigen was
1:16zum beispiel nicht möglich ist das führt
1:19uns zum thema der sogenannten
1:23unendlichkeit das ist etwas was wieder
1:26mal mit formalen sprachen zu tun hat und
1:28ganz allgemein sich definieren lässt
1:31aber auch mit hilfe von touring
1:33maschinen festgelegt ist wir sagen eine
1:36sprache ist entscheidend
1:38manchmal sorgen wir auch berechenbar
1:39oder re kursiv wenn es eine touring
1:42maschine m gibt die ihr wort problem
1:46entscheidet also dass der sprache
1:47natürlich das heißt ist entscheider und
1:51es ist genau die sprache von herrn das
1:54ist also die voraussetzung dafür dass
1:56eine sprache entscheidbar ist es gibt
1:58einen entscheider für sie es gibt einen
2:00algorithmus der für jedes wort uns ein
2:04ergebnis liefert nach endlich vielen
2:06schritten und das ergebnis wird korrekt
2:08feststellen ob das wort nun in der
2:10sprache ist oder nicht
2:12falls es keinen solchen algorithmus gibt
2:15dann nennen wir die sprache und
2:18scheinbar weiterhin sagen wir manchmal
2:21dass eine sprache die entscheider ist
2:24das nennt man auch touring erkennbar
2:26oder re kursiv auf silber oder auch
2:30repressiv abzählbar wenn es eine touring
2:34maschine gibt die l als sprache hat auch
2:38wenn sie keinen schalter ist das sind
2:40also zwei unterschiedliche situationen
2:42das hatten wir bisher bei anderen
2:43automaten modellen so nicht ich hatte
2:45das ja schon erwähnt touring maschinen
2:47können unendlich laufen sie müssen nicht
2:50unbedingt halten und trotzdem kann ihr
2:52verhalten der in dem sinne korrekt sein
2:54dass sie unendlich nur dann laufen wenn
2:57die eingabe abgelehnt würde und wir
3:00haben ja definiert ein unendlicher lauf
3:01entspricht auch einer art des verwerters
3:03das heißt die sprache die dann
3:04beschrieben wird ist richtig
3:05allerdings wissen wir nicht nach endlich
3:08vielen schritten ob das wort nun
3:09abgelehnt wird oder nicht weil wenn die
3:11tormaschine eben noch läuft wissen wir
3:13nicht braucht sie einfach noch ein
3:14bisschen oder ist sie gerade dabei
3:16unendlich lange zusammen das heißt wir
3:19haben diese situation semi entscheid
3:20barkeit und entscheid barkeit als den
3:23besonders wünschenswerten fall in dem
3:25die touring maschine garantiert ein held
3:27bei anderen automaten mussten wir diese
3:29beiden fälle nicht unterscheiden da war
3:31das 1 man konnte sicherstellen dass du
3:33selbst die keller automaten immer halten
3:35okay das also ist entscheid barkeit
3:39unentschuldbar kite semi entscheid
3:41barkeit schon an dieser definition sehen
3:43wir dass entscheid bau und
3:46unentschuldbar gegensätze sind das aber
3:49semi entscheid bei einer art von
3:54zusicherungen ist die also sicherstellt
3:59dass es überhaupt eine tui maschine gibt
4:00das ist eine positive eigenschaft wenn
4:03etwas semi entscheidbar ist es ist keine
4:05negative eigenschaft also insbesondere
4:07sind alle entscheid barren sprachen auch
4:09semi entscheidbar wir sind eben nur
4:12zusätzlich entscheidbar oft ist es so im
4:15praktischen sprachgebrauch dass menschen
4:18dann von semih entscheid barkeit
4:19sprechen
4:20also speziell menschen aus der
4:22informatik natürlich die wenn sie meinen
4:26dass eine sprache nicht mehr
4:27entschuldbar ist nur noch semi entscheid
4:29war das ist aber nicht ganz korrekt ja
4:31also semi entscheidbar ist eigentlich
4:33eine obere schranke es sagt uns die
4:35touring maschine reicht um diese sprache
4:37zu beschreiben sie reicht dafür aus auch
4:39wenn es vielleicht nicht immer mit dem
4:41endlichen halten klappt ok dazu noch ein
4:47beispiel wir hatten schon ein paar
4:49sachen erwähnt in diesem kurs die mit
4:51entscheid barkeit zu tun hatten nämlich
4:53zum beispiel dass die äquivalenz zweier
4:56kontext freier grammatiken
4:57unentschuldbar ist das heißt es gibt für
4:59die keine touring maschine und wir
5:03könnten das jetzt ein bisschen formaler
5:05machen
5:05als ich damals machen konnte ich könnte
5:08sagen wir codieren zunächst erstmal in
5:11irgendeiner weise die grammatik das geht
5:13sicherlich also man kann eine grammatik
5:15in einer datei speichern und das ist
5:17dann automatisch auch schon eine binäre
5:18kotierung das heißt wir nehmen
5:20irgendeine codierung der regeln einer
5:21grammatik in g das schreibe ich als ngn
5:26kodierung und formal bedeutet die
5:30unscheinbarkeit jetzt dass eine sprache
5:32die ich aus wörtern bildet die eine
5:36codierung von einer ersten grammatik hat
5:38und dann einen trennzeichen und danach
5:41eine codierung der zweiten grammatik und
5:45wobei die sprache die wörter nur dann
5:47enthält wenn die sprachen die die beiden
5:49grammatiken beschreibungen beschreiben
5:53borderlands sind also gleich sind oder
5:56eins von beiden keine grammatik
5:58darstellt keine kontext freiheit
6:01grammatik dass diese sprache
6:04unentschuldbar also so kommt man von so
6:08einem berechnungs problem was sagt wir
6:11wollen die äquivalenz entscheidend zu
6:12einem problem was mit einer bestimmten
6:15sprache zu tun hat ja also das scheint
6:17vielleicht erst eine einschränkung zu
6:18sein ist aber in der wirklichkeit
6:21eigentlich keine einschränkung wir
6:22können alle möglichen probleme als
6:24sprache auffassen und in dem fall habe
6:27ich eben die hier zwei verschiedene
6:30bedingungen eingefügt
6:32für diese sprache weil dieses problem
6:35sich speziell auf die äquivalenz kontext
6:37freier grammatiken bezieht also das
6:41heißt die fälle in denen eine der
6:43grammatiken keine kontext freier ist da
6:45können wir getrost akzeptieren da das
6:48ist auch leicht zu erkennen das kann der
6:49touring maschine entscheiden ob eine
6:50kommen grammatik kontext frei ist aber
6:52falls beide kontext frei sind und ihre
6:56sprachen gleich sind dann wird es
6:58schwierig oder wenn sie nicht gleich
6:59sind ja wir wissen es nicht es lässt
7:01sich eben nicht herausfinden okay das
7:03also ein erstes beispiel für eine
7:05unentschuldbare sprache die wir schon
7:07kennen gelernt haben auch wenn wir da
7:10natürlich auch noch nicht gezeigt hat
7:11und warum die unentscheiden ist das
7:13wollen wir heute zum ersten mal mit
7:15einem konkreten problem anschauen
7:19natürlich ist das alles hoffentlich
7:22nicht allzu überraschend für sie also
7:23wenn ich jetzt sage es gibt dinge die
7:25man mit hohem maschinen nicht berechnen
7:27kann es gibt sprachen die man mit tui
7:28maschine nicht beschreiben kann dann ist
7:30das natürlich irgendwo ein alter hut für
7:32sie erinnern sich wir hatten schon mal
7:34herr georg cantor hier zu gast und wir
7:36wissen dass es natürlich viel zu viele
7:38sprachen gibt um sie mit irgendeinem
7:41endlichen formalismus alle beschreiben
7:43zu können und die touring maschinen sind
7:44natürlich auch eine art endlicher
7:46darstellung also wenn ich irgend eine
7:47sprache darstellen kann mit natur
7:49maschine dann korrespondiert diese
7:52tormaschine ja irgendwie zu einer
7:53endlichen menge anzeichen auf dem papier
7:56meinetwegen die ich benötige um die
7:57tormaschine zu beschreiben und es gibt
8:00nur eine beschränkte menge von solchen
8:03darstellungen von touring maschinen
8:05nämlich absehbar viele da jede dieser
8:08touring maschinen endlich ist gibt es
8:09absehbar viele ländliche es gibt auch
8:11absehbar viele algorithmen für die
8:13computerprogramme in irgendeiner sprache
8:15das hatten wir schon gesprochen
8:16es gibt aber wie sie wissen überhaupt
8:19sehr viele sprachen also sind die
8:21allermeisten sprachen und scheinbar weil
8:23wir einfach viel zu viele sprachen haben
8:25und viel zu wenig software
8:27das ist insofern keine überraschung
8:29damit bekommt man aber kein konkretes
8:31beispiel für so eine sprache und das was
8:33ihnen gerade genannt hatte ist zwar
8:35konkret aber das kommt bisher erst mal
8:38aus dem nichts da hab ich nichts darüber
8:39gesagt warum das eigentlich entscheiden
8:41wie kommt man also eigentlich zu einem
8:45unentschuldbaren problem wie sieht man
8:47so was wie kann man ein konkretes
8:49berechnungs probleme als ein entscheid
8:51borken und das wollen wir heute machen
8:53sie werden sehen das ist relativ
8:54einfache eigentlich das gehört gar nicht
8:56so viel dazu um dann anfangen zu finden
8:58und das problem für dass wir das machen
9:01wollen ist auch eines der berühmtesten
9:04probleme der informatik nämlich das alte
9:08problem
9:09das halte problem besteht in der
9:11folgenden frage wir geben eine touring
9:13maschinen und ein wort wie wird er für
9:18die eingabe w jemals anhalt wir wissen
9:22dass das nicht immer so ist die
9:24maschinen können unendlich lange laufen
9:26und ich hatte auch schon angedeutet dass
9:29das eine sehr komplizierte sache wenn
9:30sich fünf zustände genügen um touring
9:33maschinen zu definieren von denen kein
9:37mensch weiß ob sie jemals anhalten oder
9:40zumindest keiner sicher weiß ob sie
9:42jemals anhalten wir vermuten weil sie
9:43halt nicht denn wir haben sich schon für
9:44sehr viele schritte simuliert aber wer
9:48weiß schon was genau dahinter steht ok
9:50also das alte problem eine wichtige
9:53frage in der form wie es hier steht
9:55natürlich eine theoretische frage über
9:57touring maschinen und wörter usw aber
9:59letztlich auch eine praktische frage
10:01also sie könnten das ja auch für
10:03beliebige software fragen ja sie haben
10:04ein programm geschrieben sie wollen
10:06wissen ob das jemals anhält oder ob das
10:09eine endlosschleife kommt das wäre ja
10:10vielleicht ganz praktisch wenn ihre idee
10:12dass ihnen mitteilen könnte wenn es dann
10:15mögliches problem gebe dass es in
10:18manchen fällen eine endlosschleife geben
10:19könnt ihr zum beispiel gut geht nicht
10:23werden wir sehen
10:24um das wirklich zu sehen müssen wir
10:28vielleicht noch ein bisschen mehr ins
10:29detail gehen denn so wie ich das hier
10:30schreibe ist das schon wieder zwar ein
10:32problem aber keine sprach essen was ist
10:34ja eigentlich sprache ja die wir als
10:36unentschuldbar erkennen wollen das
10:37müsste ich mal noch erklären und um das
10:40erklären zu können müssen wir die
10:43maschinen als eingaben verwenden das
10:45problem besteht ja darin dass man eine
10:47tui maschine gegeben kriegt und dann
10:48über diese tormaschine eine
10:50bestimmte aussage machen soll das heißt
10:52die tormaschine ist die eingabe und dazu
10:56müssen wir sie irgendwie kotieren ja wir
10:58hatten sie bisher ja als sex trubel von
11:00irgendwelchen mathematischen
11:02sonderzeichen aufgeschrieben das ist
11:03natürlich jetzt darf man noch keine
11:05direkte codierung die man an eine andere
11:07touring maschine weiter geben könnte
11:11wieso auch bei touring maschinen kommt
11:14es auf das detail hier überhaupt nicht
11:16an
11:16also es genügt irgendeine codierung zu
11:19haben die vernünftig ist ja die mich
11:24völlig seltsam ist die man mit einer
11:27tormaschine auswerten kann effektiv ja
11:30die nicht schon so kompliziert ist dass
11:31man sie nicht mit einem computerprogramm
11:34dekodieren kann in einem gewissen sinne
11:37okay was könnten wir zum beispiel nehmen
11:39hier sind grauer kasten
11:40er beschreibt die details ich möchte sie
11:41gar nicht so sehr durch gehen hier
11:43ich denke sie können sich das vorstellen
11:45druckmaschinen kann man ja codieren hier
11:47würden wir konkreten alphabet verwenden
11:50aus 0 1 und raute und wir könnten zum
11:53beispiel sagen die zustände sind einfach
11:55durchnummeriert und wir codieren sie als
11:57eine folge von der codierten zahlen mit
12:000 1
12:02wir können auch für die verschiedenen
12:04bewegungsrichtungen binder codierungen
12:06angeben und dann das herzstück der
12:08touring maschinen sind ja letztlich
12:09diese übergänge also dass für bestimmte
12:11eingaben gibt es bestimmte folgen also
12:15jeweils dieses triple hier
12:17und damit haben wir letztlich für jeden
12:20solchen übergang fünfte stimmungs stücke
12:22zwei zustände zwei symbole eine richtung
12:25die können wir einfach hintereinander
12:26aufschreiben und das ist ein teilgebiet
12:28der kontierung und das können sie mit
12:30allen existierenden allen definierten
12:32übergängen machen dann haben sie die
12:33übergangs funktion die ja endlich ist
12:35ansich codiert das müssen sie jetzt
12:40irgendwie hintereinander hängen
12:41vielleicht durch doppelte trennzeichen
12:42damit sie wissen wo ein bestimmter teil
12:45also die zu stellen zum beispiel enden
12:47und wo das codierte 1 gab s symbol
12:51eingabe alphabet beginnt aber auch das
12:56ist nicht schwierig also so was in
12:57dieser art könnten sie machen und ich
13:00werde solche kurz schreibweisen wie eng
13:01von m
13:02und auch eng von einem bestimmten wort
13:04von einem bestimmten alphabet in den
13:08nächsten ferien verwenden einfach
13:09annehmen dass wir irgendwie definiert
13:12haben wie man diskutiert ok ok touring
13:17maschinen lassen sich codieren und jetzt
13:19kommen wir dazu dass wir das alte
13:22problem formal definieren können das
13:28lässt sich so erreichen wir hier in
13:30diesem kiss in dieser kiste die das alte
13:34problem ist das wort problem für die
13:36sprache die sie hier sehen die sprache
13:38besteht aus wörtern der form codierung
13:40von m trennzeichen trennzeichen
13:42codierung eines wortes wobei die touren
13:47maschine codiert wird halten soll wenn
13:49das wort was hier codiert wird er als
13:52eingabe vorliegt also wir wollen nur
13:55diese wörter bei denen das erfüllt ist
13:57und das ist also eine art wie man dieses
13:59problem als sprache ausdrücken kann
14:00wenn wir in algorithmus haben der für
14:03solche codierten wörter die richtigen
14:06entscheidungen treffen kann dann haben
14:08wir das problem gelöst
14:09wir müssen ja nur ne entsprechende also
14:12wenn wir uns eine bestimmte maschine
14:14interessieren wir sind wir nur diese
14:16maschine codieren und das wird und dann
14:17den einfach etwas mit dieser eingabe
14:20befragen und dann wissen wir was die
14:21antwort wäre okay gut also so haben wir
14:24das alte problem als sprache definiert
14:27wichtiger kleiner subtiler punkt hier an
14:31der stelle ist vielleicht das natürlich
14:33nicht alle wörter die man über 0 1 und
14:35raute bilden kann
14:36überhaupt so eine codierung einer
14:39maschine und eines wortes darstellen ja
14:41also bei wörtern müssen wir vielleicht
14:43noch relativ flexibel aber bei maschinen
14:46ist natürlich das format schon wichtig
14:49und es gibt viele möglichkeiten wie man
14:51hier überhaupt keine maschine kopieren
14:54kann
14:54und es gibt also dann eine fehlerhafte
14:57codierung was definiert unsere angabe
15:00hier für diesen fall ja ja ja die an die
15:03die menge die wir hier aufgeschrieben
15:05haben sagt ja es ist die menge aller
15:07wörter die diese form haben für boeing
15:10maschine und wort mit diesen
15:11eigenschaften
15:12das heißt die sprache enthält nur
15:14korrekt codierte
15:15strings das bedeutet was wir hier
15:20indirekt auch mit definiert haben ist
15:23dass alle fehlerhaften codierungen
15:25abgelehnt werden und das ist typisch
15:27wenn man ein entscheidungs problem
15:29definieren will dass man sagt ja
15:31akzeptanz eines wortes in der sprache
15:34bedeutet die frage die ich gestellt habe
15:36wird mit ja beantwortet ablehnung
15:38bedeutet entweder die frage die ich
15:41gestellt habe wird mit nein beantwortet
15:43oder die eingabe die ich hier kopiert
15:45habe die ich ag diskutiert überhaupt
15:47keine frage
15:48das geht natürlich meistens auch nur die
15:51frage ob die codierung stimmt lässt sich
15:54in der regel sehr einfach entscheiden
15:55das heißt darin besteht keine
15:57schwierigkeit und diese fälle können wir
15:59immer erkennen es ist also keine
16:01praktische problematik irgendwie aber
16:03das nur zur erklärung dass das natürlich
16:05immer mit drin steckt wenn ich das in
16:07der sprache formulieren dass ich nicht
16:09nur korrekte codierungen habe okay
16:12das also ist das formale alte problem
16:14und jetzt möchten wir zeigen dass dieses
16:16problem unentschuldbar ist und das soll
16:21passieren mit hilfe eines widerspruch
16:25des beweises an der stelle kommen wir zu
16:29dem punkt den ich eingangs angesprochen
16:31habe wir wollen das mit zeitreisen lösen
16:34wie konkret meine ich das und zwar ist
16:40die unmöglichkeit der existenz der einer
16:44matten touring maschine die das heil
16:46problem löst eigentlich ziemlich analog
16:48zu der unmöglichkeit der existenz
16:50bestimmter zeitreise maschinen ja sie
16:54könnten
16:55und im prinzip könnten sie es auch genau
16:57mit einem ähnlichen argument widerlegen
16:59angenommen ich hätte eine zeitmaschine
17:02sie erlaubt mir in die zukunft zu
17:05schauen ganz ähnlich wie eine
17:08tormaschine dieses problem löst sie
17:09schaut in die zukunft geschaut ob die
17:10touring maschine jemals hält für die
17:13eingabe hat
17:14ich habe also eine zeitmaschine ich
17:16keine zukunft schauen und nehmen wir an
17:19wir sind jetzt gemeinsam mit dem raum
17:21wie es vielleicht in einer normalen
17:22vorlesung unter normalen bedingungen
17:23wären dann könnte ich in die zukunft
17:26schauen sagen wir fünf minuten und
17:28herausfinden ob jemand den raum verlässt
17:31oder nicht den raum verlässt kann ich
17:33ihnen sagen ja ich weiß wer den raum
17:36verlassen wird in fünf minuten überlegen
17:37sie sich ob sie rausgehen jetzt oder
17:39nicht und ich verhalte mich dann auch
17:45entsprechend nämlich indem ich sage
17:47nennen sie mir einfach irgendeine person
17:49hier im raum und ich weiß ja ob diese
17:51person den raum verlassen wird und ich
17:53verhalte mich dann genau entgegengesetzt
17:56wenn die personen den raum verlässt
17:58setze ich mich hin und warte wenn die
18:01person den raum nicht verlassen wird in
18:02fünf minuten doch da ist dann gehe ich
18:04gleich raus jetzt agieren
18:06das ist eine zeitmaschine und ganz tolle
18:10sache kann leute beeindrucken mit dem
18:13kleinen trick dass ich schon weiß wie
18:14sie sich entschieden haben oder wie sich
18:15entscheiden werden das funktioniert so
18:18lange gut bis jemand der anwesen sind
18:21auf die idee kommen zu sagen ja während
18:24wird doch mal sich selbst als person aus
18:26schauen sie mal was sie selbst in der
18:28zukunft machen und dann verhalten sie
18:30sich entsprechend
18:31dann mache ich das sehe ich ja ich bin
18:34selbst aus dem raum rausgegangen also
18:36setzte ich mich hin und bleibe in dem
18:37raum
18:38aber dann gehe ich ja gar nicht aus oder
18:41ich bin noch im raum also gehe ich
18:43sofort raus was auch nicht funktioniert
18:46ja es ist also ein paradoxon
18:48und sie sehen also damit könnte man
18:51argumentieren dass eine solche
18:53zeitmaschine unmöglich ist in science
18:56fiction narrativen wird es dann zum teil
18:59auch anders gelöst irgendwelche
19:01widrigkeiten hinter nicht daran den raum
19:03zu verlassen obwohl ich wollte das geht
19:06aber der mathematik nicht so einfach
19:07wenn dort etwas paradox ist dann bleibt
19:09auch paradox und im prinzip wollen wir
19:11die genau gleiche idee auch touring
19:15maschinen anwenden das heißt also wird
19:16betrachten jetzt unsere alte problem
19:19maschine als die hypothetische
19:21zeitmaschine die die zukunft kennt und
19:23wir programmieren einer touring maschine
19:25die dann sich entsprechend vor
19:27dann zeigen dass das nicht sein kann
19:29okay das ist der beweis plan
19:32zeitreisen mit den maschinen und jetzt
19:34mache ich noch einmal formal und ich
19:36hoffe dann haben sie das auch gut
19:38verstanden wie das funktioniert also
19:40widerspruchs beweis angenommen es gäbe
19:42eine zeitmaschine
19:45es gebe eine deterministische touring
19:48maschine die das alte problem
19:50entscheidet ich nenne die harvey halte
19:52problem das heißt herr heldt immer es
19:56ist ein entscheider und akzeptiert
19:58eingaben von dieser codierten formen wie
20:01wir sie gerade gesehen haben codierung
20:03einer maschine codierung eines wortes
20:05genau dann wenn die maschine auf diese
20:08eingabe wird anhält so ich nehme an ich
20:12habe sowas dann kann ich diese touring
20:16maschine dieses programm verwenden in
20:21beliebigen anderen toni maschinen ja
20:23auch als zu proteine ich kann noch ein
20:25bisschen ton programmieren und wir
20:28machen das jetzt und entwickeln eine
20:31neue deterministische turi maschine die
20:34die nenne ich die für die agonie sierung
20:39war das was wir machen im prinzip ein
20:41katholisches fast kann tisches diagonal
20:44ii sierung argument wird okay tut aber
20:48nichts zur sache wir nennen sie einfach
20:49die was soll sie tun diese touring
20:52maschinen ja zunächst einmal wenn sie
20:54eine eingabe wie erhält dann schreibt
20:58sie diese zunächst in folgende form und
21:01wie trennzeichen trennzeichen kotierung
21:04des wortes wir können jedes wort
21:08codieren und das wird sich auch
21:09berechnen lassen also das geht irgendwie
21:11ihr eine tormaschine die codierung
21:13nachvollzieht mit einer sinnvollen
21:14codierung mit einer vernünftigen
21:15kotierung klappt das zweiter schritt
21:18die führt die magische heide problems
21:23touring maschine auf dieser eingabe aus
21:25wir haben das jetzt auf dem band jetzt
21:26lassen wir dieses zubrot ihnen laufen
21:28und fahren mal was sie tut das können
21:32wir zum beispiel dadurch erreichen dass
21:33wir einfach die zustände dieser halte
21:36problems touring maschine einfach in
21:37unseren zustands graf einfügen und die
21:40übergänge alle so bearbeiten dass diese
21:42alte maschinen der machen würde und
21:45dabei das ganze worte abarbeiten
21:47bis die maschine hält da landet sie in
21:51irgendwelchen and zuständen und dort
21:53können wir da wird die kontrolle
21:54übernehmen wollte in unseren garten von
21:57d weiter gehen und so funktioniert also
22:00auch konkret mit dieser zucchini die ok
22:02wir führen also auf dieser eingabe aus
22:05und tun jetzt das folgende wenn h die
22:09eingabe nicht akzeptiert also falls
22:11zurück liefert dann hält die
22:15unverzüglich und akzeptiert andernfalls
22:20wenn h die eingabe akzeptiert dann geht
22:23die in eine endlosschleife und hält
22:26nicht das lässt sich auch leicht
22:28realisieren sie wechseln in einen
22:30zustand aus dem es kein entkommen gibt
22:32und in dem man immer weiter irgendetwas
22:34tut es muss nicht mal was produktiv ist
22:37sein sie müssen nicht viele dinge
22:38schreiben es reicht wenn sie einfach nur
22:40immer weiter über geld ausführen okay
22:44gut und das ist jetzt das entspricht
22:47jetzt den beiden aktivitäten ja also
22:49wenn wenn ich sehe dass jemand den raum
22:52verlässt dann bleibe ich im raum wenn
22:55ich sehe dass jemand die ausgewählte
22:57personen den raum nicht verlässt dann
23:00verlasse ich den raum
23:02das sind die gegensätzlichen handlungen
23:04wie bei der zeitreise
23:06die idee ist also ganz einfach die so
23:10wie es hier definiert habe hält und
23:12akzeptiert eine touring maschinen
23:13codierung codierung von m
23:17genau dann wenn m auch der eingabe die
23:23die form hat eng kotierung von m nicht
23:26hält ok
23:30verwirrend vielleicht ja hier hatten wir
23:33ja noch gar nicht davon gesprochen dass
23:35wie eine codierung einer tormaschine ist
23:37aber natürlich wenn wir diese art von
23:39kunden um codierung hier durchführen
23:41dann bedeutet das haar diese alte
23:45maschine macht nur dann etwas
23:47interessantes und sinnvoll dass wenn wir
23:48selbst eine tormaschine codiert das
23:53geben wie dieser touring maschine als
23:55eingabe naja wir schreiben hier die
23:58codierung von w
23:59die wird ja wieder decodiert von h und
24:03wer selbst wird dann die der input für
24:06diese tolle maschine auf dem wir prüfen
24:08ob die tormaschine und held oder nicht
24:10das heißt dass eingabe wort hat wirklich
24:12wörtlich die form von vieh von empathie
24:16und daher kommt dieser diese diese
24:21situation hier also die tor maschine
24:25hält auf ihrer eigenen codierung oder
24:28eben nicht
24:29und die wird genau das gegenteil tun
24:31okay das ist die konstruktion von d und
24:35dieser teil der konstruktion ist nicht
24:38besonders schwierig wenn man denn dieses
24:41jahr hat dieses mysteriöse was wir hier
24:43annehmen und zum widerspruch führen wird
24:45alles andere ist offensichtlich oder
24:47relativ leicht zu argumentieren dass es
24:49machbar ist nur das haar muss man dazu
24:51vorher habe ok also hier nochmal die
24:55zusammenfassung das gleiche stand gerade
24:57schon mal unten
24:58er tut das gegenteil wm auf seiner
25:02eigenen codierung tun wird für solche in
25:05sozial für in puts die eine
25:07continental-maschine wir schreiben für
25:10andere inputs ist verhalten völlig egal
25:11das brauchen wir für den beweis gar
25:13nicht betracht ok so das ist jetzt
25:17soweit passiert das experiment mit der
25:19zeitreise ist vorbereitet und jetzt
25:21kommt jemand und sagt verhalten sie sich
25:25doch mal so wie sie selbst sich in fünf
25:28minuten nicht verhalten werden und das
25:31entspricht genau der idee dass wir nun
25:34diese maschine die für die eingabe
25:40von den ausführen die maschine die wir
25:44sie gerade konstruiert haben unter der
25:46annahme dass es so eine maschine hergibt
25:48ist ja was sehr konkret ist das ist ja
25:50nicht nur eine irgendwie abstrakte oder
25:52als template definierte maschine so und
25:54das ist wirklich eine spezifische
25:56touring maschine die man sodann
25:57konstruieren könnte und die kann man
25:59natürlich auch codieren also das ist ein
26:02endliches gebildete und die hat
26:04irgendwie so eine darstellung als
26:05codierung von dir wenn das also als
26:10eingabe jeden wird was passiert naja
26:13falls die für die eingabe kotierung von
26:17der held dann akzeptiert hat
26:19die eingabe codierung von die codierung
26:22der kotierung von den ball ja
26:25entscheidet ob sie hält ja also wenn sie
26:27hält dann wird das auch akzeptieren und
26:29voraussagen dass sie hält doch wenn hat
26:32das akzeptiert dann haben wir ja die so
26:34definiert dass es nicht halten wird dann
26:37gehen wir ja in die endlosschleife das
26:39machen wir nach der soap routine
26:40das heißt das kann gar nicht passieren
26:43ja das würde ein widerspruch erzeugt
26:45dann hätte er falsch entschieden
26:47übrigens solche doppelten escaping
26:52ausdrücke kennen sie sicherlich auch vom
26:55programmieren
26:56zumindest wenn sie mal versucht mein
26:57bestes zu programmieren oder irgendwas
26:59ähnliches dann ist ihnen das nur allzu
27:02häufig dass man manchmal solche
27:04geschafft hätten escapes benötigt ja ich
27:09hoffe aber wenn sie darüber nachdenken
27:10ich hab's ja gerade schon mal erklärt
27:12dann wird ihnen klar dass wir das so
27:14braun
27:15okay das heißt also der fall dass die
27:19auf seine eigenen codierung hält ist
27:21schon mal ausgeschlossen
27:22denn in diesem fall müsste hat sich
27:25bezüglich die ok schauen wir mal den
27:28anderen fall an falls die auf der
27:30eingabe nicht hält dann sagt ha das
27:34korrekt voraus das heißt h wird die
27:36eingabe die wir ihm geben nicht
27:38akzeptieren doch dann reagiert ja de
27:43genau umgekehrt die wir zu verhalten
27:45weil die soutine fonds zurück geliefert
27:48hat und auch dann hat er
27:50so hat die entscheidung nicht korrekt
27:52vorhergesagt widerspruch ja also
27:57offensichtlich in keiner bekam der
27:59beiden möglichen fälle ist das was wir
28:02hier als konsequenz finden irgendwie
28:05konsistent und und in sich schlüssig das
28:09heißt es kann irgendetwas mit unseren
28:11annahmen nicht gestimmt haben und das
28:13ist natürlich in dem fall höchstens das
28:15ist keine solche maschine hergibt
28:17wir könnten auch ein bisschen anders
28:19sagen wir könnten sagen dann nicht dass
28:21es keine zeitmaschine gibt sondern dass
28:23zeitmaschine nicht das verhalten von
28:24zeitreisen denn vorhersagen können ja
28:28also das wäre vielleicht eine andere
28:30möglichkeit das problem zu lösen und zu
28:32sagen ja bereits gibt es so ein haar
28:35aber für die funktioniert das nicht
28:37das funktioniert dann nicht für alle
28:38touring maschinen nur für manche für
28:41einfacher für richtig
28:42und tatsächlich kann man sich auch in
28:46diese richtung interessante dinge
28:48vorstellen auch mathematisch
28:50interessante dinge vorstellen man kann
28:51zum beispiel sagen ja nehmen wir mal an
28:53wir haben durch maschinen die das alte
28:55problem von anderen touring maschinen
28:56entscheiden können das sind sozusagen
28:57die zeit reisen denn dann können sie
29:01zwar nicht das eigene falle probleme
29:02entscheidend aber vielleicht können sie
29:04dann trotzdem noch andere dinge machen
29:06solche überlegungen sind natürlich sehr
29:09hypothetisch und theoretisch da wir in
29:11der praxis keine computer keine normalen
29:14touring maschinen haben die das lösen
29:15können und das ist genau das was dieser
29:17beweis sei also man kann in verschiedene
29:20richtungen hier weitergehen aber für uns
29:23hier sieht man man kommt zu einem
29:27widerspruch wenn man annimmt dass eine
29:28normale touring maschine
29:30das halte problem für normale touring
29:33maschinen innerlich lösen könnte okay
29:36gut
29:38damit endet der beweise ich habe ihn ein
29:41bisschen ausgedient weil ich viele
29:42sachen dreimal erklärt habe ich hoffe zu
29:47ihrem vorteil
29:50es ist aber insgesamt ein relativ
29:52einfacher beweis gesehen wissen wie sie
29:53gesehen haben also damit schon kann man
29:56konkrete
29:57probleme als unentschuldbar wir wollen
30:01aber nicht mit so einer ganz negativen
30:04sicht vielleicht enden sondern auch
30:06zeigen dass es zumindest möglich ist ein
30:09bisschen was zu tun auch beim halter
30:11problem und um dahin zu kommen möchte
30:15ich noch ein kleiner schritt gehen
30:16nämlich über die universelle touring
30:18maschine reden die universelle die
30:19maschine ist was was relativ leicht zu
30:23erklären ist die idee ist einfach dass
30:26wir eine tui maschine konstruieren die
30:28das verhalten anderer touring maschinen
30:31simuliert also es gibt eine tormaschine
30:35universal die für eingaben der form
30:38codierung einer tormaschine codierung
30:40eines wortes das verhalten von m
30:43auf w simuliert also von der kotierten
30:45touring maschine auf dem konto was heißt
30:48simuliert das heißt falls die touring
30:50maschine m auf dem wort behält dann hält
30:53auch die universelle tormaschine auf
30:55dieser kodierung und zwar mit dem
30:57gleichen ergebnis akzeptanz wird
30:59akzeptanz verwerfen wird verwehrt falls
31:02er auf wenig hält dann hält auch die
31:04universelle boeing maschine auf diese
31:06codierung nicht das heißt die
31:08universität ulm maschinen tut immer
31:09genau das gleiche auf der codierung wie
31:12die eigentliche tolle maschine auf dem
31:13board getan hätte und das ist also auch
31:16ein ziemlich starkes resultat dass es
31:21solche maschinen gibt das heißt im
31:22prinzip dass man beliebige touring
31:27maschinen berechnungen schon mit einer
31:29einzigen sinnvoll kotierten tormaschine
31:32durchführen kann
31:33auch wenn diese einzelne touring
31:34maschinen natürlich ein festes eingabe
31:37alphabet und ein festes band alphabet
31:39hat ja also die tormaschine simulieren
31:42könnten ja beliebige alphabete verwenden
31:43aber in der kultivierung wird alles
31:46irgendwie vielleicht auf 0 mit einzelnen
31:48oder auf 0 und 1 unten trennzeichen oder
31:50wie auch immer zurück gebracht und damit
31:53arbeitet unsere universität turin
31:55maschine
31:56das heißt unabhängig vom alphabet kann
31:59sie immer mit wenigen zeichen auskommen
32:01das im detail zu beschreiben ist etwas
32:04aufwendig skizzenhaft ist es nicht sehr
32:07kompliziert
32:08im detail ist es ziemlich umfangreich
32:11und wird in der regel nicht gemacht ja
32:14intuitiv gleichwertig ist aber das
32:17programmieren eines touring maschinen
32:19simulators in einer beliebigen
32:20programmiersprache und wenn ich so
32:22formulieren dann sagen sie hoffentlich
32:23ja klar das werde man hinbekommen nach
32:25dem was ich ihnen über touring maschinen
32:27gesagt haben wenn sie jetzt in java
32:29python oder c oder wie auch immer in
32:31rast eine touring maschinen simulation
32:33programmieren sollten die mit
32:35irgendeiner kürzung von touring
32:36maschinen dann die schritte ausführt und
32:38einfach das gleiche tut also auch endlos
32:41läuft wenn die tormaschine entwirft dann
32:43wäre das sicherlich nicht allzu schwer
32:45und man sie zumindest dass das machbar
32:46als das dass nichts unmöglich ist da
32:48steht okay das also ist die universelle
32:51touring maschine und warum führe ich die
32:53ihn ein
32:53naja zum einen natürlich weil diese art
32:58von universalität eine ganz wunderbare
33:00sache es in der informatik ist es im
33:02prinzip der grund warum wir software
33:05haben und nicht für jedes problem einen
33:07neuen computer anschaffen müssen also
33:10die universelle tui maschine ist ja
33:12letztlich so etwas wie das gerät in das
33:14sie gerade schauen ein interpret der
33:18beliebige algorithmen ausführen kann und
33:20sie können die algorithmen selbst bin
33:24eher kodieren das nennt man dann eben
33:26ausführbare programme binaries und
33:30universelle touring maschine kann die
33:32dann ausführen ja und was man für eine
33:35sache ja also es würde keine software
33:37geben wenn das nicht ginge für uns hier
33:41in diesem video hat aber noch eine
33:42andere nützliche funktion wir können
33:44nämlich die universelle touring
33:45maschinen verwenden um zu sehen dass das
33:47alte problem von dem ich gerade gezeigt
33:49habe das ist nicht entschuldbar ist
33:51wenigstens semi entscheidbar ist
33:54satz das alte problem ist sie mir ein
33:57scheinbar beweis skizze die besucher
34:03touring maschine also die touring
34:05maschine die das semi entscheidet die
34:06das puppen dieses diese sprache erkennt
34:09auch wenn sie kein entscheider ist
34:11startet intern einfach eine universelle
34:14touring maschine auf der eingabe und
34:19verändert das ergebnis der universellen
34:22touring maschine dann geringfügig indem
34:24sie nämlich immer dann akzeptiert wenn
34:25sie hält egal ob das halten akzeptieren
34:28dass oder verwerfen des halten war
34:30und wenn sie nicht hannah gut dann hält
34:33sie nicht okay das ist auch der einfache
34:38verwendung dieser universitäts idee und
34:41ist natürlich genauso wichtig wie dass
34:43man maschinen simulieren kann also am
34:45ende simulieren wir einfach die touring
34:47maschine und das alte problem zu
34:48entscheiden und wenn wir glück haben
34:50hält sie dann haben wir zunächst die
34:51positive antwort wenn wir pech haben
34:53hält sie nicht dann werden das auch nie
34:54herausfinden mit dieser mit dieser
34:56herangehensweise
34:59es gibt natürlich fälle in denen man
35:01sehen kann dass die tui maschine nicht
35:03halt so ist es nicht aber man kann das
35:04auch manchmal beweisen oder es gibt
35:06vielleicht auch einfacher fälle die man
35:07leicht mit dem algorithmus erkennen
35:09könnte aber wir machen ja gar nicht den
35:11versuch das solche einfach ein fan zu
35:13finden denn wir wissen schon
35:15wir werden niemals alle fälle damit
35:17abdecken ansonsten wäre dieser
35:19widerspruchs beweis den wir gerade
35:20gezeigt haben irgendwo falsch
35:23gut also immerhin semir entscheidbar und
35:26jetzt könnten wir natürlich sagen ja das
35:28heißt wir haben zwar ein unscheinbares
35:30problem aber wir haben immer noch kein
35:31beispiel für einen nicht sehr
35:33entscheidendes problem mir einen nicht
35:35touring erkennbares problem obwohl ja
35:38kantor wiederum und sagt es gibt so
35:40viele probleme dass es garantiert auch
35:43welche gibt die nicht mal erkannt werden
35:45mit irgendeiner touring maschinen es
35:46gibt einfach nicht genug touring
35:47maschinen können wir also bitte noch ein
35:49konkretes problem sehen das nicht semi
35:52entscheidbar ist das nicht touring
35:54erkennbar wäre okay ich mache
35:58wir mal ganz einfach um ihnen da 1 zu
36:01zeigen und zwar nehmen wir das
36:03kompliment des halte problems die frage
36:07ist einfach wird die gegebene tor
36:08maschine nicht anhalten
36:12warum ist dieses problem nicht semi
36:16entscheiden naja die grundidee ist ich
36:20hatte schon auf der feuerlöscher klassen
36:22lieber so die grundidee ist ganz einfach
36:24semi entscheid barkeit ist ja ein
36:27der begriff ist schon gut gewählt denn
36:29er sagt uns dass wir zumindest in der
36:32hälfte der fälle in der einen möglichen
36:35situation ein endergebnis nach endlich
36:38vielen schritten erhalten ja also nach
36:40etlicher zeit wird der algorithmus crew
36:43zurück liefern falls das die richtige
36:45antwort ist wir wissen natürlich nicht
36:48wie lange das dauert
36:49kurzer überlegung warum wissen wir das
36:52nicht können wir nicht sagen er wird
36:54zurück liefern in quadratischer zeit
36:57oder in exponentiell vielen schritten
36:59oder sowas und in anderen fällen
37:02vielleicht nie halten
37:03naja wenn es so wäre dann hätten wir ja
37:06an entscheider ja wenn wir wüssten wie
37:08lange das positive ergebnis höchstens
37:10auf sich warten lässt
37:11dann könnten wir in allen fällen in
37:13denen wir länger rechnen als diese zeit
37:15auch sicher sein dass das ergebnis
37:17negativ ist und dann hätten wir an
37:19entscheider gefunden dann wäre es nicht
37:21nur semi entscheidbar sondern auch
37:22entscheiden
37:23die situation beim halter problem ist so
37:27dass wir diesen entscheid barkeit haben
37:30und wie zeigen wir jetzt das nicht auch
37:32das kompliment des problems das nicht
37:36halte problem sozusagen zement scheinbar
37:38ist das machen wir ganz einfach wieder
37:40durch widerspruch in dem wir
37:41argumentieren wenn wir jetzt noch einen
37:44zweiten algorithmus hätten der das nicht
37:46halte probleme semir entscheidet dann
37:50könnten wir diesen algorithmus jahr
37:51laufen lassen und wenn die touring
37:52maschine nicht hält würde er irgendwann
37:56zurück liefern ja er würde irgendwann
37:58nach endlich vielen schritten das
38:00erkannt haben dass die touring maschinen
38:02nicht und würde uns fröhlich dieses
38:06ergebnis mitteilen ja
38:08das sehen die entscheidung nur etwas
38:10fürs alte problem hat aber die gleiche
38:12eigenschaft nur für den rest der fälle
38:14ja er wird uns immer nach etlicher zeit
38:16bescheid sagen wenn die maschine hält
38:20und wenn also beide algorithmen
38:21existieren würden dann müssten wir
38:23einfach nur beide algorithmen parallel
38:26ausführen auf zwei computern aber auch
38:29mit anatol maschine geht das ja sie
38:31können sich leicht vorstellen sie haben
38:32zum beispiel nehmen sie zwei bänder und
38:34auf dem einen rechnen sie als einer auf
38:36dem anderen das andere oder sie machen
38:38sagen die hintereinander schritt für
38:40schritt das ist egal
38:40dann wären wir könnten beide diese
38:42algorithmen jedenfalls gleichzeitig
38:44ausführen und wir wüssten dass das nicht
38:49unendlich lange ohne ergebnis bleibt
38:51einer der beiden fälle muss ja ein
38:52treten entweder der algorithmus die
38:54tormaschine hält oder sie hält nicht und
38:56in jedem der fälle muss einer der beiden
38:57algorithmen nach endlich vielen
38:58schritten erfolgreich sein und je
39:01nachdem welches ist geben wir dann das
39:03ergebnis zurück also entweder hält oder
39:05hält nicht das heißt dann hätten wir an
39:07entscheider und dass es keine
39:09entscheidung gibt haben wir ja schon
39:10bewiesen also sind wir sicher dass das
39:13kompliment des halde problems nicht
39:14erkennbar kommen ist ja hier steht es
39:17noch mal angenommen
39:18das problem wäre touring erkennbar dann
39:20könnten wir das alte problem
39:21entscheidend indem wir die semi
39:23entscheidungs algorithmen für heide
39:24probleme und kompliment parallel
39:27abarbeiten einer der beiden algorithmus
39:30halten und liefert dann das gesucht
39:32ergebnis widerspruch ok so kann man es
39:36übrigens allgemein machen sie mir
39:38entscheid barkeit und co semi entscheid
39:41barkeit ergibt entscheid barkeit das ist
39:44immer so und es gibt tatsächlich
39:46praktische probleme führt das für die
39:48wir keine besseren algorithmen kennen
39:51als so einen ansatz
39:53das ist natürlich der world's worst
39:56worst case ansatz ja also wenn sie so
40:00einen algorithmus haben der zwei semi
40:02entscheidungsprozessen gegeneinander
40:04antreten lässt und dann die erste den
40:06ergebnis liefert als grundlage für die
40:09für die entscheidung nimmt dann haben
40:12sie einen algorithmus der beliebig lang
40:14laufen kann
40:15für den sie keinerlei abschätzung geben
40:17können wie lange er läuft warum ist das
40:21so naja hab ich gerade erklärt ja wenn
40:22sie wüssten wie lange das höchstens
40:24dauert dann hätten sie ja schon mit
40:25einem der beiden in entscheidungs
40:27algorithmus wenn sie wirklich nur sehen
40:29die entscheidung hinbekommen dann müssen
40:31sie auch das problem haben dass sie bei
40:33beiden algorithmen nicht wissen wie lang
40:35die benötigen können und das heißt sie
40:37haben wirklich eine situation wo sie nur
40:38bewiesen haben dass es irgendwann nach
40:40endlich vielen schritten waren ergebnis
40:42gibt aber sie haben wirklich kein schirm
40:44aber anders sein wird exponentiellen
40:46viele schritte exponentielle
40:47exponentiell viele schritte oder noch
40:49etwas viel schlimmeres ackermann
40:50funktion viele schritte
40:51all das reicht nicht aus um abzuschätzen
40:53wie schlimm es am ende werden könnte
40:55denn all das sind berechenbare funktion
40:57die sie benutzen könnten um zu wissen ob
41:00es sich noch lohnt weiter zu rechnen
41:02okay gut das war ein bisschen kleiner
41:05exkurs in andere themen die wir noch mal
41:08im detail in zukünftigen video reihe zum
41:11thema eine theoretische informatik
41:13behandeln werden denke ich okay sie
41:16sehen viele interessante dinge die man
41:18hier machen kann und wir haben ein paar
41:20konkrete beispiele auch konkrete
41:22praktische beispiele gesehen für touring
41:26erkennbare und nicht touring erkennbare
41:29probleme und für entscheider und nicht
41:32entscheiden und da werden noch ein paar
41:34mehr dazu kommen aber jetzt wissen wir
41:36ja konkret was dahinter steht wenn ich
41:37sowas sagen wenn ich sage ein problem
41:39ist unentschuldbar
41:40wir werden das nicht mehr in diesem
41:41großen detail machen die man als
41:44abschluss noch ein kleiner kommentar zu
41:46einem begriff der gerne und oft
41:48auftaucht nämlich der begriff der
41:50touring mächtigkeit wir sagen dass ein
41:52bestimmter formalismus irgendeine art
41:54von berechnung ansatz touring mächtig
41:57ist wenn er stark genug ist um das ein-
42:01und ausgabeverhalten einer tormaschine
42:03zu simulieren ich könnte auch äquivalent
42:06sagen wenn er eine universelle touring
42:08maschine kodieren kann also es reicht
42:10schon aus dieser eine tui maschine
42:11simuliert offensichtlich denn sie ist so
42:14stark dass sie alle anderen auch
42:16simulieren kann
42:17ok das nennt man tor ii mächtig und das
42:21ist etwas was wir in der informatik sehr
42:22hofft antreffen mal gewöhnen
42:26mal nicht gewünscht ja es ist natürlich
42:29ein vorteil für viele dinge wenn sie
42:31touring mächtig sind insbesondere bei
42:33programmiersprachen wir wünschen uns in
42:35der regel dass unsere
42:35programmiersprachen touring mächtig sind
42:37sonst würden sie vielleicht nicht einmal
42:39programmiersprache nennt weil damit
42:42garantieren wir ein maximum an
42:45berechnungs stärke ja gibt immer noch
42:48vielleicht praktische dinge die
42:49programmiersprache aus dem einen oder
42:50anderen grund nicht kann aber was die
42:53berechnung angeht kann sie alles
42:55nachteil ist aber dass in manchen fällen
42:59touring mächtigkeit auch viel zu viel
43:02ist und viel mehr als das was man sich
43:03gewünscht hat weil es im prinzip
43:06bedeutet dass alle interessanten fragen
43:09alle interessanten analysen die man in
43:11bezug auf die berechnete funktion
43:13anstellen könnte unscheinbar sind zb die
43:16äquivalenz zwei darstellungen also ist
43:18das eine programm genau gleichwertig mit
43:20dem anderen
43:21der touring maschinen und ohnmächtiger
43:24darstellungen immer ohne entscheid bar
43:26wird die berechnung irgendwann mal
43:28halten und ein scheinbar wird sie nicht
43:30halt nur den scheinbar ist der wert
43:35garantiert in den bestimmten bereich
43:37oder ist das ergebnis garantiert
43:38von dieser oder jener vor alles sind das
43:42sind dinge die typischerweise
43:43unentschuldbar werden können für solche
43:46beliebigen programmen
43:47man kann natürlich fälle finden wo man
43:49das leicht zieht aber in der rede kann
43:51man es nicht automatisch bestimmen und
43:55das ist eigentlich immer dann
43:56unerwünscht wenn wir nicht gerade
43:58programmieren ja also wenn wir nicht
44:00darauf vertrauen dass vor dem bildschirm
44:02eine programmiererin sitzt die ihr
44:05handwerk versteht und die sicherstellen
44:07kann dass das programm in der regel in
44:10den fällen für dieses gemacht ist auch
44:12wirklich terminiert und das passiert in
44:14vielen fällen ich habe in dem problem
44:16satz den sie unten in den links findet
44:17noch ein paar mehr oder weniger amüsante
44:21beispiele zusammengetragen die es dazu
44:25gibt sachen die sql oder microsoft
44:29powerpoint ist auch schon mächtig oder
44:31magic the gathering
44:34das kartenspiel also man kann touring
44:37maschinen in vielen interessanten
44:39formalismen und regelwerken formulieren
44:41selbst in zwei spieler karten spielen
44:47okay das war's für diesen teil gewesen
44:52sein
44:53damit endet dieses video wir haben
44:58einiges über das alte problem gelernt
45:00und ein bisschen uns die theorie
45:02angeschaut und vielleicht auch ein paar
45:03ganz interessante argumente kennen
45:06gelernt wie man sowas zeigt als nächstes
45:09sollten wir mal wieder ein bisschen
45:11stärker zurückkommen zu den sprachen ich
45:13habe immer noch offen gelassen wie man
45:14jetzt zu den typen sprachen kommt und
45:16was ist eigentlich mit den typ 1
45:18sprachen über die spricht irgendwie
45:19keiner mehr
45:20wir sind mit dem touring maschinen glatt
45:22darüber hinweg gesprungen
45:24kann man das dann irgendwie auch wieder
45:26beschränken um nicht gleich typ 0
45:29komplett zu erhalten sondern eben nur
45:31typ 1 das wäre mal auch in kürze sehen
45:34bis dahin tschüss und auf wiedersehen

About this transcript

This page contains the full transcript of Unentscheidbarkeit und das Halteproblem by Prof. Markus, generated from the public captions YouTube serves with the video. The transcript has 6,817 words across 1,156 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to choose a caption track available on the video.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.