WEBVTT 00:10.370 --> 00:17.830 Wir hatten uns beim letzten Mal mit dem in gewisser Weise vielleicht 00:17.830 --> 00:25.190 spannendsten Thema der ganzen Vorlesung beschäftigt, mit dem man sogar 00:25.190 --> 00:28.290 Unterhaltungsmathematik machen kann und das meiner Meinung nach auch 00:28.290 --> 00:33.430 zu recht tiefen Einsichten führt, nämlich Unentscheidbarkeit und 00:33.430 --> 00:35.830 allem, was da drumherum ist. 00:40.310 --> 00:45.330 Also wir hatten angefangen mit so sprachlichen Paradoxien, dann immer 00:45.330 --> 00:48.910 darauf hinaus, dass sobald man irgendwie Selbstbezüglichkeiten und 00:48.910 --> 00:52.310 Negationen drin hat, dann gehen Sachen einfach schief. 00:52.410 --> 00:54.030 Dann kommt man zu paradoxen Aussagen. 00:54.110 --> 00:59.510 Das war hier der Barbier von XY rasiert genau die Männer im Dorf, die 00:59.510 --> 01:00.810 sich nicht selbst rasieren. 01:00.890 --> 01:03.910 Da haben sie gesagt, der Barbier ist eine Frau, aber dann wäre der 01:03.910 --> 01:05.650 Genust von der Barbier falsch. 01:05.650 --> 01:10.650 Dann hätte man gesagt, die Barbierin oder die Friseuse oder so. 01:15.570 --> 01:21.490 Und was ich noch cooler fand, war diese Sache mit der allwissenden 01:21.490 --> 01:25.690 Maschine, wo man dann beweisen kann, dass es die nicht geben kann, mit 01:25.690 --> 01:27.810 so einem Selbstbezüglichkeitstrick. 01:29.190 --> 01:32.170 Dann bin ich wieder ein bisschen formaler angefangen, habe so Begriffe 01:32.170 --> 01:37.470 wie Entscheidbarkeit einer Sprache, Semientscheidbarkeit eingeführt. 01:38.350 --> 01:41.610 Eine Variante davon ist die Reklusive Aufzählbarkeit. 01:42.850 --> 01:44.990 Wesentlichen das Gleiche wie Semientscheidbar. 01:47.810 --> 01:52.690 Und dann hatten wir damit geendet, dass eine ganze Reihe dieser Sachen 01:52.690 --> 01:55.210 äquivalent sind, nämlich Reklusive Aufzählbarkeit, 01:55.590 --> 02:01.630 Semientscheidbarkeit, ob eine Sprache Chomsky-Typ 0 ist, ob eine 02:01.630 --> 02:11.250 Sprache, die von einer Turing-Maschine akzeptierte Sprache ist, ob die 02:11.250 --> 02:15.710 halbe charakteristische Funktion berechenbar ist durch irgendein 02:15.710 --> 02:19.650 beliebiges Turing-vollständiges Modell, also Turing-Maschine, Weil 02:19.650 --> 02:25.530 -Maschine, Register-Maschine, RAM, Zellularautomat 110 oder was Sie 02:25.530 --> 02:25.810 wollen. 02:26.810 --> 02:33.170 Oder, dass die Sprache Definitionsbereich oder Wertebereich einer 02:33.170 --> 02:34.850 berechenbaren Funktion ist. 02:36.650 --> 02:41.350 Dann wollen wir uns heute endlich konkrete und nicht entscheidbare 02:41.350 --> 02:42.810 Probleme anschauen. 02:47.510 --> 02:51.750 Und dafür werden wir wieder die Selbstbezüglichkeit nutzen. 02:51.750 --> 02:55.390 Und da es um Turing-Maschinen geht, muss also jetzt eine Turing 02:55.390 --> 03:00.510 -Maschine Turing-Maschinen-Beschreibungen als Eingaben kriegen. 03:00.590 --> 03:01.550 Das wird der Trick sein. 03:02.710 --> 03:07.050 Und dafür ist es nützlich, Turing-Maschinen zu normieren. 03:08.590 --> 03:12.990 Wir hatten ja einen recht hohen Freiheitsgrad, was Zustandsmenge, 03:14.290 --> 03:16.230 Bandsymbole usw. 03:16.490 --> 03:16.850 angeht. 03:17.590 --> 03:21.630 Und es ist relativ klar, dass man das ein bisschen reduzieren kann. 03:22.030 --> 03:25.030 Zunächst mal, ohne Beschränkung der Allgemeinheit, können die Zustände 03:25.030 --> 03:28.550 die natürlichen Zahlen 1 bis N sein, für eine konstante N. 03:30.670 --> 03:33.770 Wir nehmen 0 und 1 als Eingabe-Alphabet. 03:35.430 --> 03:39.110 Und das Band-Alphabet ist auch 0 und 1, außerdem, dass wir ein 03:39.110 --> 03:41.870 zusätzliches Blank-Symbol noch brauchen, das ist dann die 2. 03:44.070 --> 03:47.930 Der Startzustand ist ohne Beschränkung der Allgemeinheit der erste 03:47.930 --> 03:55.330 Zustand und der Endzustand der Zustand 2, der einzige Endzustand. 03:56.610 --> 03:57.970 Fragen dazu? 04:01.130 --> 04:04.550 Natürlich können wir damit nicht beliebige Turing-Maschinen nachbauen, 04:04.670 --> 04:09.430 weil das Turing-Maschinen sind, die auf Verarbeitung von Bit-Strings 04:09.430 --> 04:13.350 beschränkt sind. 04:13.650 --> 04:19.050 Aber es ist auch relativ klar, dass man beliebige Alphabete wieder 04:19.050 --> 04:20.650 kodieren kann durch Bit-Strings. 04:21.330 --> 04:26.500 So, und jetzt führen wir den Begriff der Gödel-Nummer in der Turing 04:26.500 --> 04:29.100 -Maschine ein und den schreiben wir als... 04:32.880 --> 04:34.200 Wie nennt man das eigentlich? 04:36.480 --> 04:38.380 Eckige Klammer kann man nicht sagen, ne? 04:39.760 --> 04:41.520 Spitze-Klammer, Spitze-Klammer-M. 04:45.480 --> 04:51.900 Und wir kodieren jetzt im Wesentlichen Einträge in der 04:51.900 --> 04:52.520 Übergangsfunktion. 04:53.540 --> 04:55.920 Da ist es jetzt nützlich, davon auszugehen, dass wir da eine partielle 04:55.920 --> 04:56.710 Funktion haben. 05:00.270 --> 05:06.790 Und zwar haben wir ja so Sachen wie Delta Q, A, also Übergang von 05:06.790 --> 05:13.590 Zustand Q, Eingabe A ist ein Trippel, nämlich neuer Zustand R, neues 05:13.590 --> 05:16.030 Bandsymbol B und Bewegungsrichtung D. 05:17.530 --> 05:24.010 Die kodieren wir jetzt im Wesentlichen unnäher durch Ketten von 05:24.010 --> 05:24.370 Nullen. 05:25.350 --> 05:34.250 Also Q wird durch Q Nullen kodiert, A wird durch A plus 1 Nullen 05:34.250 --> 05:47.210 kodiert, R wird durch R Nullen kodiert, B wird durch B plus 1 Nullen 05:47.210 --> 05:52.770 kodiert und D wird durch D Nullen kodiert. 05:52.770 --> 05:55.050 Und dazwischen schreibe ich immer eine 1 als Markierung. 05:55.770 --> 05:59.130 Und jetzt können Sie sich höchstens fragen, wieso ist das mal Variable 05:59.130 --> 06:00.550 mal Variable plus 1? 06:01.170 --> 06:10.810 Das hängt damit zusammen, dass unsere Bandsymbole Zahlen sind, die bei 06:10.810 --> 06:11.530 0 anfangen. 06:12.370 --> 06:17.330 Und ich kann nicht 0 Nullen nehmen, weil die Ketten von wiederholenden 06:17.330 --> 06:19.890 Einsen haben eine andere Bedeutung, was wir gleich sehen werden. 06:23.490 --> 06:30.050 Während die Zustände bei 1 anfangen, glaube ich. 06:32.450 --> 06:35.570 Also die Zustände fangen bei 1 an, das heißt da habe ich sowieso nicht 06:35.570 --> 06:38.950 0 Nullen und ich kann dann immer das voneinander unterscheiden. 06:41.030 --> 06:45.370 Also ich habe hier im Endeffekt, das ist diese relationale Notation 06:45.370 --> 06:47.430 für die Übergangsfunktion, wenn Sie wollen. 06:47.430 --> 06:52.610 Ich habe einfach so 5 Tupel und die einzelnen Komponenten werden 06:52.610 --> 06:56.230 unnäher kodiert, getrennt durch Einsen. 07:01.470 --> 07:06.790 Also die Bewegungsrichtung kodiere ich durch 1, 2 und 3 für nicht 07:06.790 --> 07:08.150 bewegen, links und rechts. 07:09.230 --> 07:13.390 Die ganze Turing-Maschine wird dann ganz einfach kodiert durch 3 07:13.390 --> 07:14.090 Einsen. 07:16.570 --> 07:23.670 Dann eine beliebige Anzahl von diesen 5 Tupeln, getrennt durch jeweils 07:23.670 --> 07:28.610 2 Einsen und ganz am Ende wieder 3 Einsen als Markierung, dass ich 07:28.610 --> 07:29.250 fertig bin. 07:33.530 --> 07:39.050 Und diese Tupel können in beliebiger Reihenfolge auf dem Band stehen. 07:39.670 --> 07:43.530 Aber wenn Sie jetzt wollen, dass diese Gödelnummer eine eindeutige 07:43.530 --> 07:48.070 Funktion ist, können Sie sich auch eine Konvention überlegen, in 07:48.070 --> 07:50.530 welcher Reihenfolge die auf dem Band stehen, zum Beispiel in 07:50.530 --> 07:52.070 lexikografischer Reihenfolge. 07:55.770 --> 08:01.590 Und jetzt ist es noch so, unsere Kodierung für Turing-Maschinen hat so 08:01.590 --> 08:02.570 etwas wie eine Syntax. 08:02.570 --> 08:09.970 Also es gibt Folgen von Nullen und Einsen, die keine Turing-Maschine 08:09.970 --> 08:10.610 beschreiben. 08:11.710 --> 08:13.670 Sie können sich als Übung überlegen, ein Beispiel dafür. 08:16.810 --> 08:20.230 Und dann machen wir einfach eine Konvention, wenn das der Fall ist, 08:20.290 --> 08:23.970 also wenn das ein Syntaxfehler ist, dann sagen wir einfach, diese Zahl 08:23.970 --> 08:26.870 beschreibt eine Turing-Maschine, die die leere Sprache akzeptiert. 08:31.370 --> 08:36.830 Und damit ist das so, dass jede beliebige Zahl eine Turing-Maschine 08:36.830 --> 08:37.870 beschreibt. 08:39.110 --> 08:42.670 Es ist auch umgekehrt so, dass jede Turing-Maschine durch mindestens 08:42.670 --> 08:44.050 eine Zahl beschrieben wird. 08:44.450 --> 08:47.390 Aber es kann natürlich sein, dadurch, dass ich diese Tupel in 08:47.390 --> 08:51.790 beliebiger Reihenfolge schreiben kann, dass mehrere solche Zahlen die 08:51.790 --> 08:54.910 gleiche Turing-Maschine im Endeffekt beschreiben. 08:56.250 --> 08:57.910 Fragen zu dieser Definition? 09:04.520 --> 09:08.140 Also, was ich gerade schon gesagt habe, diese Gödelnummerierung 09:08.140 --> 09:11.620 beschreibt eine injektive Abbildung von normierten Turing-Maschinen 09:11.620 --> 09:20.300 auf natürliche Zahlen, zumindest wenn man das als eine Funktion 09:20.300 --> 09:25.580 definiert, also dass man dafür sorgt, dass eine feste Reihenfolge 09:25.580 --> 09:26.240 gewählt wird. 09:26.240 --> 09:31.340 Dann ist es tatsächlich injektiv, weil verschiedene Turing-Maschinen 09:31.340 --> 09:38.140 verschiedene Übergangsfunktionen haben und damit auch verschiedene 09:38.140 --> 09:41.300 natürliche Zahlen studiert werden. 09:42.980 --> 09:44.560 Nehmen wir mal ein Beispiel. 09:45.540 --> 09:49.500 Eine Turing-Maschine mit drei Zuständen und eben unserem normierten 09:49.500 --> 09:53.400 Eingabe - und Bandalphabeten. 09:57.010 --> 10:00.050 Und die wird dann eindeutig beschrieben, muss man wirklich nur die 10:00.050 --> 10:02.270 Zustandsübergänge angeben, dann haben wir vier Stück. 10:03.590 --> 10:05.910 Und die sind dann halt hier reinkodiert. 10:06.130 --> 10:10.970 Also hier Anfangsmarker drei Einsen, Endmarker drei Einsen und dann 10:10.970 --> 10:17.890 eins, zwei, dreimal diese Trennmarker zwei Einsen und dazwischen eins, 10:18.210 --> 10:20.730 zwei, drei, vier solche Tuppel. 10:22.030 --> 10:23.170 Fragen dazu? 10:27.830 --> 10:32.510 Und jetzt definieren wir unsere erste unentscheidbare Sprache, die 10:32.510 --> 10:34.010 Diagonalsprache LD. 10:34.750 --> 10:38.750 Die tauchte schon am Ende des letzten Kapitels auf als ein Beispiel 10:38.750 --> 10:43.110 für eine Typ-0-Sprache, die keine Typ-1-Sprache ist. 10:44.510 --> 10:46.070 Das müssen wir noch beweisen. 10:47.070 --> 10:49.090 Und das ist jetzt gerade diese Unentscheidbarkeit. 10:49.210 --> 10:54.150 Wir wissen ja, dass Typ-1-Sprachen entscheidbar sind. 10:54.750 --> 10:57.870 Wir haben ja das Wortproblem, den Algorithmus angegeben. 10:58.150 --> 11:01.690 Und jetzt zeigen wir, dass das LD nicht entscheidbar ist und damit 11:01.690 --> 11:04.250 haben wir dann auch bewiesen, dass das keine Typ-1-Sprache ist. 11:06.490 --> 11:08.730 Diese Diagonalsprache hat jetzt gerade wieder diese 11:08.730 --> 11:12.710 Selbstbezüglichkeit drin und verwendet eigentlich diesen 11:12.710 --> 11:16.870 Diagonalisierungstrick, den Cantor auch schon verwendet hat, um zu 11:16.870 --> 11:21.830 zeigen, dass die reellen Zahlen nicht abzählbar sind, eng miteinander 11:21.830 --> 11:22.250 verwandt. 11:24.510 --> 11:30.250 Das ist also Mi, die Turing-Maschine mit der Gödel-Nummer i. 11:32.150 --> 11:41.250 Sei jetzt der Binärstring Wi die Binärrepräsentation dieser Zahl und 11:41.250 --> 11:46.490 jetzt definieren wir LD einfach als die Menge aller Wi, für die gilt 11:46.490 --> 11:48.870 Mi akzeptiert Wi nicht. 11:50.810 --> 11:57.130 Also eine Maschine, die auf ihre eigene Beschreibung angesetzt wird, 11:57.350 --> 11:58.290 akzeptiert die nicht. 11:59.010 --> 11:59.870 Das ist die Diagonalsprache. 12:01.550 --> 12:02.630 Fragen dazu. 12:03.670 --> 12:08.130 Das ist jetzt wieder dieses Papier-von-hinter-Tupfingen-Ding, nur eben 12:08.130 --> 12:10.290 jetzt in Maschinenterminologie. 12:11.890 --> 12:14.930 Und wir zeigen jetzt formal, LD ist unentscheidbar. 12:15.930 --> 12:21.030 Beweis, durch Widerspruch, Annahme, LD sei entscheidbar. 12:23.070 --> 12:27.390 Also nach der Definition von entscheidbar heißt das, es gibt eine 12:27.390 --> 12:33.830 Turing -Maschine Mi, die LD akzeptiert und immer hält. 12:37.870 --> 12:43.070 Jetzt kann man sich fragen, was macht Mi bei Eingabe von Wi? 12:43.860 --> 12:47.350 Also was macht diese Turing-Maschine, wenn man ihre eigene 12:47.350 --> 12:51.230 Beschreibung als Eingabe gibt? 13:01.090 --> 13:03.550 Also jetzt machen wir einfach eine Fallunterscheidung. 13:04.170 --> 13:10.650 Wenn Wi in der Diagonalsprache ist, dann sagt uns die Definition von 13:10.650 --> 13:16.090 Mi, was sie tun soll, weil Mi akzeptiert ja LD, das heißt Wi wird 13:16.090 --> 13:16.810 akzeptiert. 13:22.220 --> 13:28.800 Das ist aber blöd, weil wenn Wi akzeptiert wird, dann sagt uns ja die 13:28.800 --> 13:37.600 Definition von LD, LD ist ja gerade die Sprache a la Wi, die Mi nicht 13:37.600 --> 13:38.300 akzeptiert. 13:39.840 --> 13:44.420 Das heißt nach der Definition von LD ist Wi nicht in LD. 13:45.300 --> 13:49.560 Wir haben aber eben als Prämisse verwendet, dass Wi in LD ist. 13:50.120 --> 13:52.660 Also das kann schon mal nicht sein, das wäre ein Widerspruch. 13:53.120 --> 13:55.080 Also nehmen wir mal an, Wi ist nicht in LD. 13:59.180 --> 14:06.140 Dann sagt uns die Definition von Mi genauso, dass Wi dann halt nicht 14:06.140 --> 14:07.060 akzeptiert wird. 14:12.880 --> 14:16.480 Aber dann wenden wir wieder die Definition von LD an und die sagt uns 14:16.480 --> 14:18.320 eben gerade, dass Wi in LD ist. 14:18.440 --> 14:19.560 Das kann also auch nicht sein. 14:20.060 --> 14:21.520 Beides führt zu einem Widerspruch. 14:22.660 --> 14:25.200 Und das kann nur sein, weil wir ursprünglich eine falsche Annahme 14:25.200 --> 14:28.680 gemacht haben, nämlich die Annahme war, dass LD entscheidbar ist. 14:29.040 --> 14:30.660 Folglich ist LD unentscheidbar. 14:31.660 --> 14:32.940 Fragen dazu? 14:34.060 --> 14:36.260 Also ein klassischer Widerspruchsbeweis. 14:37.080 --> 14:43.540 Wir wenden nur ganz naiv relativ simple Definitionen an. 14:47.640 --> 14:51.840 Also es ist nicht viel schwieriger als der Unentscheidbarkeitsbeweis 14:51.840 --> 14:57.120 oder Nichtberechenbarkeitsbeweis für diese Funktionen von der 14:57.120 --> 14:59.040 Dezimalentwicklung von reellen Zahlen. 15:00.040 --> 15:04.100 Nur, dass wir das Ganze jetzt rein formalsprachlich aufgezogen haben. 15:15.990 --> 15:21.730 Aber was wir jetzt immer noch nicht haben, ist eine unentscheidbare 15:21.730 --> 15:26.350 Sprache, die irgendwie was Nützliches tut. 15:27.950 --> 15:31.210 Da wollen wir jetzt noch hin, weil das ist jetzt irgendwie so eine 15:31.210 --> 15:35.830 Konstruktion, die gerade für diese Dialogonalisierung gedacht war. 15:36.250 --> 15:38.570 Aber wen interessiert LD, könnte man sagen. 15:39.270 --> 15:41.530 Man könnte immer sagen, alles Interessante ist berechenbar. 15:43.390 --> 15:44.530 Dann gehen wir jetzt mal weiter. 15:44.670 --> 15:49.750 Erstmal, das Kompliment von LD ist auch unentscheidbar. 15:50.590 --> 15:55.190 Der Beweis ist ziemlich einfach, weil wenn das Kompliment entscheidbar 15:55.190 --> 16:00.590 wäre, dann gäbe es ja eine Maschine, die LD-Kompliment akzeptiert. 16:01.070 --> 16:06.530 Und die kann ich leicht so akzeptieren, so modifizieren, dass sie LD 16:06.530 --> 16:10.190 akzeptiert, indem ich akzeptierende und nicht akzeptierende 16:10.190 --> 16:11.750 Haltezustände austausche. 16:14.310 --> 16:25.130 Aber um jetzt die Querverbindung zu ziehen von dieser 16:25.130 --> 16:30.110 Taschenspielertrick -Sprache LD zu wirklich naheliegenden 16:30.110 --> 16:34.430 Fragestellungen, die man eigentlich gerne mit Computern verarbeiten 16:34.430 --> 16:37.250 möchte, brauchen wir jetzt universelle Turing-Maschinen. 16:37.250 --> 16:41.130 Das heißt, wir machen nicht nur so eine trockene und eigentlich 16:41.130 --> 16:45.750 triviale Kodierung von Turing-Maschinen als Zahlen. 16:46.510 --> 16:49.770 Das habe ich gebraucht, damit ich Turing-Maschinen auf sich selbst 16:49.770 --> 16:52.490 ansetzen kann und überhaupt die Selbstbezüglichkeit hinkriege. 16:53.110 --> 16:55.250 Sondern ich muss das Ganze sozusagen operationalisieren. 16:56.210 --> 17:01.410 Ich muss wirklich sagen, aha, man kann auch mit etwas Nützliches tun, 17:01.510 --> 17:05.450 wenn man eine Eingabe kriegt, die eine Gödel-Nummer ist. 17:06.930 --> 17:12.270 Insbesondere, wir können eine Turing-Maschine angeben, die eine andere 17:12.270 --> 17:17.750 Turing -Maschine simuliert und zwar in der Form, dass diese andere 17:17.750 --> 17:20.610 Turing -Maschine Teil der Eingabe ist. 17:22.750 --> 17:26.610 Genauer gesagt, eine universelle Turing-Maschine U ist jetzt wieder so 17:26.610 --> 17:28.230 eine nummierte Turing-Maschine. 17:29.090 --> 17:33.390 Die besteht aus QU, das ist 1 bis N, für ein N, das wir noch festlegen 17:33.390 --> 17:33.690 müssen. 17:34.590 --> 17:37.510 Ich glaube, das kleinste ist 13 oder sowas. 17:40.870 --> 17:45.430 Wir haben ja hier die nummierten, das heißt, Bandalphabet ist 0,1 und 17:45.430 --> 17:46.210 dann brauchen wir... 17:51.360 --> 17:52.260 Ach so, darum haben wir das. 17:52.360 --> 17:53.960 Wir wollen es jetzt gerade andersrum haben. 17:53.960 --> 17:55.300 Da müssen wir mal nachgucken. 17:56.800 --> 17:58.220 Ja, da müssen wir mal nachgucken. 17:58.340 --> 18:00.140 Aber irgendwie so ein Dutzend rum. 18:06.710 --> 18:09.490 Aber das entspricht ja nicht unserer Definition von nummierten 18:09.490 --> 18:10.050 Maschinen. 18:13.310 --> 18:16.190 Eine universelle Turing-Maschine macht jetzt Folgendes, die kriegt als 18:16.190 --> 18:21.370 Eingabe eine Gödel-Nummer, gefolgt von einem Binärstrang W. 18:24.410 --> 18:27.750 Genau, also das Ende dieser Gödel-Nummer ist ja klar identifizierbar. 18:27.890 --> 18:31.230 Das sind das zweite Mal drei Einsen hintereinander und dann weiß man, 18:31.370 --> 18:32.810 jetzt folgt die eigentliche Eingabe. 18:36.190 --> 18:40.590 Und die Turing-Maschine, die die Gödel-Nummer kodiert, ist die zu 18:40.590 --> 18:45.370 simulierende Turing-Maschine und W ist die Eingabe, die diese Maschine 18:45.370 --> 18:49.310 M bearbeiten soll. 18:50.290 --> 18:55.910 Also die universelle Maschine simuliert die eingegebene Maschine auf 18:55.910 --> 18:56.790 der Eingabe W. 18:58.550 --> 19:04.310 Das heißt, die universelle Maschine U akzeptiert die Eingabe Gödel 19:04.310 --> 19:09.230 -Nummer von M, W, genau dann, wenn M die Eingabe W akzeptiert. 19:10.150 --> 19:11.210 Fragen dazu? 19:13.980 --> 19:16.880 Und ich finde, das ist jetzt eigentlich auch programmiertechnisch 19:16.880 --> 19:18.420 schon fast interessant. 19:18.600 --> 19:23.220 Also das ist sozusagen die maximal reduzierte Form dessen, was ein 19:23.220 --> 19:24.160 Interpreter macht. 19:25.380 --> 19:27.620 Und sowas muss man ja vielleicht auch mal in seiner Karriere 19:27.620 --> 19:28.000 schreiben. 19:30.620 --> 19:33.840 Wir bauen jetzt eine ganz einfache universelle Turing-Maschine. 19:35.120 --> 19:36.680 Dafür verwenden wir drei Bänder. 19:37.760 --> 19:40.640 Also die hat ein paar Mehrzustände, kann man dazu sagen. 19:41.560 --> 19:45.800 Das eine Band speichert die zu simulierende Maschine. 19:47.260 --> 19:52.720 Das zweite Band speichert den Zustand der zu simulierenden Maschine, 19:53.280 --> 19:54.780 und zwar einfach unärkodiert. 19:54.980 --> 19:59.240 Also wenn sie im Zustand K ist, sind auf dem zweiten Band K Einsen und 19:59.240 --> 19:59.960 sonst nur Blanksymbole. 20:01.640 --> 20:05.740 Und auf dem dritten Band wird der Bandinhalt der zu simulierenden 20:05.740 --> 20:08.840 Maschine gespeichert. 20:10.680 --> 20:16.980 Und dann brauchen wir vermutlich noch sowas wie eine Vorverarbeitung, 20:17.060 --> 20:20.360 weil unsere Konvention ist ja eigentlich, dass auf dem Eingabeband 20:20.360 --> 20:26.900 erst die Gürtelnummer von M und dann die Eingabe steht. 20:27.000 --> 20:29.280 Das wird halt dann umkopiert auf die geeigneten Bänder. 20:31.520 --> 20:36.840 Also genau am Anfang wird die Eins auf das Band Zwei geschrieben, wird 20:36.840 --> 20:43.180 die Maschinenbeschreibung auf das Band Eins kopiert und wird das W auf 20:43.180 --> 20:44.540 Band Drei kopiert. 20:44.920 --> 20:47.920 Das sind aber relativ einfache Turing-Maschinen-Unterprogramme, die 20:47.920 --> 20:52.120 man relativ simpel hinkriegt. 20:54.690 --> 20:58.570 Jetzt habe ich hier so einen Pseudocode, der aber auch relativ leicht 20:58.570 --> 21:00.410 in Turing-Maschinen umzusetzen ist. 21:01.710 --> 21:07.970 Hier habe ich jetzt auch erstmal so eine Syntax-Überprüfung gemacht. 21:08.150 --> 21:12.590 Also man guckt sich an, gibt es überhaupt einen Präfix von W, der eine 21:12.590 --> 21:13.530 Turing -Maschine repräsentiert. 21:14.050 --> 21:18.110 Der muss halt die Form haben, drei Einsen, dann eine Folge von diesen 21:18.110 --> 21:20.670 fünf Tupeln und dann wieder drei Einsen. 21:21.590 --> 21:24.350 Und wenn das nicht der Fall ist, wenn das zum Beispiel mit 101 21:24.350 --> 21:31.650 anfängt, dann geht man einfach in einen nicht akzeptierenden Zustand, 21:32.490 --> 21:35.690 weil die simulierende Maschine ja dann gerade die ist, die die leere 21:35.690 --> 21:37.410 Sprache spricht. 21:38.390 --> 21:41.570 Aber jetzt nehmen wir mal an, dieser Syntax-Check hat funktioniert. 21:41.570 --> 21:48.950 Jetzt verschiebt man diesen Präfix V, der die Maschine kodiert, auf 21:48.950 --> 21:50.730 das Maschinenband. 21:52.210 --> 21:55.350 Setzt den Startzustand auf 1, das habe ich eben schon gesagt. 21:56.090 --> 21:59.030 Und jetzt hat man im Prinzip so eine Weilschleife. 22:00.030 --> 22:04.890 Solange der Zustand der simulierten Maschine nicht 2 ist, das war ja 22:04.890 --> 22:07.930 der Endzustand einer simulierten Maschine, also da muss man nur 22:07.930 --> 22:12.850 gucken, besteht dieses Band aus zwei Einsen, ganz einfach, hält man 22:12.850 --> 22:19.630 halt nicht, sondern läuft weiter und zwar man läuft zum Anfang der 22:19.630 --> 22:25.570 Maschinenbeschreibung, zum Band 1, und dann scannt man über die Tupel, 22:25.630 --> 22:31.910 die da drin stehen, und schaut, ist da eins dabei? 22:34.050 --> 22:39.270 Also für jedes Tupel Q, A, R, B, D, guckt man, ist Q gleich dem 22:39.270 --> 22:41.390 Zustand auf dem Zustandsband? 22:42.310 --> 22:45.050 Da muss ich im Prinzip durch die beiden Bänder laufen und gucken, sind 22:45.050 --> 22:48.570 da gleich viele Einsen und wenn nicht, dann muss ich halt zum nächsten 22:48.570 --> 22:49.670 Tupel gehen. 22:50.430 --> 22:55.750 Wenn das gilt, dann gucke ich, ob das Eingabezeichen, das auf Band 3 22:55.750 --> 23:01.450 steht, gleich dem zweiten Element in dem Tupel ist. 23:02.030 --> 23:07.010 Das kann ich auch wieder mit einem einfachen Vergleich machen, bzw. 23:07.230 --> 23:12.150 das Eingabesymbol sind ja sowieso nur drei verschiedene Werte. 23:15.090 --> 23:18.730 Wenn das so ist, also ich habe den richtigen Zustand und das richtige 23:18.730 --> 23:21.910 Symbol, dann weiß ich, das ist ein Tupel, das jetzt den nächsten 23:21.910 --> 23:23.090 Übergang definiert. 23:26.590 --> 23:32.490 Dann kopiere ich das dritte Element des Tupels auf das Zustandsband. 23:33.730 --> 23:34.830 Nee, Quatsch. 23:37.350 --> 23:39.090 Genau, auf das Zustandsband. 23:39.390 --> 23:46.630 Dann kopiere ich das vierte Element auf das Band 3, das war ja das 23:46.630 --> 23:47.730 simulierte Band. 23:49.330 --> 23:53.710 Und dann das fünfte Ding, das D, sagt mir dann die Bewegungsrichtung 23:53.710 --> 23:56.890 und entsprechend muss ich Band 3 verschieben. 23:56.890 --> 24:02.090 Also alles sehr simple Unterprogramme, die man jedes davon leicht als 24:02.090 --> 24:05.430 Übungsaufgabe oder sogar als Klausuraufgabe stellen kann. 24:06.630 --> 24:09.250 Fragen zu dieser universellen Turing-Maschine. 24:13.910 --> 24:16.570 Jetzt kann man sich auch noch fragen, ist das eine schnelle Emulation 24:16.570 --> 24:17.450 oder nicht? 24:18.590 --> 24:22.310 In gewisser Weise, aus Theoretikersicht, ist das schnell. 24:25.890 --> 24:29.210 Sie müssen zwar jedes Mal über die ganze Maschinenbeschreibung 24:29.210 --> 24:31.790 iterieren, aber die ist ja konstant lang. 24:33.290 --> 24:36.450 Also wenn Sie sich die Laufzeit in Abhängigkeit von der Eingabegröße 24:36.450 --> 24:40.590 angucken, ist das eine Echtzeitsimulation. 24:43.670 --> 24:47.530 Der konstante Faktor kann groß sein bei komplexen Maschinen, aber das 24:47.530 --> 24:48.110 stört uns nicht. 24:48.790 --> 24:51.350 Allerdings, wir haben ja hier auch eine Dreiband-Turing-Maschine. 24:52.730 --> 24:55.930 Was wir eigentlich wollen, damit das Ganze simpel bleibt, ist eine 24:55.930 --> 24:57.010 Einband -Turing-Maschine. 24:57.550 --> 24:59.930 Also wir wollen eine universelle Einband-Turing-Maschine. 25:00.590 --> 25:01.590 Wie mache ich das? 25:02.570 --> 25:04.070 Und eigentlich wissen wir das schon. 25:04.150 --> 25:07.870 Wir haben ja bei den Turing-Maschinen-Programmiertechniken uns bereits 25:07.870 --> 25:11.290 angeguckt, wie man Mehrband-Turing-Maschinen auf eine Einband-Turing 25:11.290 --> 25:13.370 -Maschine simulieren kann. 25:14.090 --> 25:21.570 Das Problem dabei ist, dass das funktionierte über einen Aufblasen des 25:21.570 --> 25:22.490 Bandalphabets. 25:23.490 --> 25:31.310 Ich klebe ja die drei Bänder hintereinander und brauche dann aber so 25:31.310 --> 25:41.350 eine Kontrollspur, die mir die momentanen Eingaben der Schreibt 25:41.350 --> 25:43.210 -Leseköpfe kodieren. 25:44.830 --> 25:50.090 Damit ist mein Bandalphabet aber sicherlich nicht mehr 0, 1, blank. 25:54.790 --> 25:59.970 Was wir dafür machen, ist, dass wir das Bandalphabet durch konstant 25:59.970 --> 26:02.130 viele Nullen und Einsen kodieren. 26:07.790 --> 26:11.450 Dann müssen wir unsere Maschine so bauen, dass sie auf diesem 26:11.450 --> 26:12.810 kodierten Ding arbeitet. 26:13.590 --> 26:18.330 Aber das ist nicht schwierig, weil man dann im Zustand genug 26:18.330 --> 26:25.790 Informationen speichern kann, um aus mehreren Nullen und Einsen ein 3 26:25.790 --> 26:31.590 -Band -Turing-Maschinen-simulierendes Bandalphabet-Symbol zu 26:31.590 --> 26:31.910 speichern. 26:35.170 --> 26:40.810 Das Problem, das wir dadurch kriegen, ist, dass die Eingabe in so 26:40.810 --> 26:47.410 einer nummierten Turing-Maschine trotzdem in diesem nicht-kodierten 26:47.410 --> 26:48.050 Format ist. 26:48.270 --> 26:51.330 Dann müssen wir eine Vorverarbeitung bauen, die als erstes mal über 26:51.330 --> 26:55.090 diese nicht-kodierte Eingabe geht und die dann kodiert. 26:55.090 --> 27:00.610 Das heißt, die nimmt dann die Nullen und Einsen und bläst die dann auf 27:00.610 --> 27:04.770 in die komplexeren Zustände, die auch diese Kontrollspuren noch mit 27:04.770 --> 27:05.210 erlauben. 27:06.090 --> 27:07.710 Das ist also alles ein bisschen technisch. 27:08.410 --> 27:11.530 Nehmen wir auch mal an, diese universellen Turing-Maschinen, die mit 27:11.530 --> 27:15.930 weniger Zuständen arbeiten, machen das in viel stärker gehackter Art 27:15.930 --> 27:16.490 und Weise. 27:17.390 --> 27:19.090 Aber das muss uns hier nicht ändern. 27:20.070 --> 27:24.290 Gibt es Fragen zur Konstruktion universeller Turing-Maschinen? 27:25.090 --> 27:28.810 Also vielleicht, um das nochmal zu rekapitulieren. 27:30.550 --> 27:34.070 Wir benutzen eine Dreiband-Turing-Maschine, die eigentlich relativ 27:34.070 --> 27:38.950 intuitiv ist, die ich ab Pseudocode direkt hinschreiben kann und sehr 27:38.950 --> 27:39.890 einfache Dinge tut. 27:40.250 --> 27:45.750 Und dann brauche ich so ein paar technische Händewedeleien, um das 27:45.750 --> 27:48.890 wieder auf eine Einband-Maschine runterzudrücken, die tatsächlich auch 27:48.890 --> 27:50.510 nur Nullen und Einsen verarbeitet. 27:51.490 --> 27:55.990 Aber das sind so technische Details, die eigentlich für das 27:55.990 --> 27:58.110 Verständnis der ganzen Sache nicht so wichtig sind. 28:06.490 --> 28:12.810 Dann kommen wir jetzt schließlich zu dem vielleicht zentralen, nicht 28:12.810 --> 28:17.330 berechenbaren Problem, wenn es darum geht, über nützliche Dinge zu 28:17.330 --> 28:17.550 reden. 28:20.550 --> 28:25.330 Das klingt jetzt auch noch ein bisschen technisch, aber eigentlich ist 28:25.330 --> 28:27.550 es schon ziemlich klar, dass das etwas ist, was ich wissen will. 28:28.110 --> 28:34.210 Ich möchte gerne eine andere Turing-Maschine Beschreibung als Eingabe 28:34.210 --> 28:39.870 geben und dann die Frage haben, hält die? 28:40.530 --> 28:43.270 Und dann vielleicht noch zusätzlich die Eingabe mitgeben oder sowas. 28:46.640 --> 28:53.100 Und das wäre schon cool, weil wenn ich sowas hätte, könnte ich das 28:53.100 --> 28:54.200 auch ansetzen auf... 28:55.300 --> 28:59.400 Also dann würde im Wesentlichen wegen der Church & These wäre es zum 28:59.400 --> 29:02.280 Beispiel auch möglich, zu gucken, ob ein Java-Programm hält. 29:04.240 --> 29:09.580 Und damit könnte ich ganz mächtige Werkzeuge bauen, die mir helfen, 29:09.920 --> 29:11.760 Bugs automatisch zu finden. 29:15.020 --> 29:21.020 Das will man eigentlich haben, das probieren auch Wissenschaftler 29:21.020 --> 29:23.660 immer wieder, gerade unsere Arbeitsgruppen, die mit formalen Methoden 29:23.660 --> 29:24.100 arbeiten. 29:24.840 --> 29:28.380 Aber die sind halt ständig dadurch behindert, dass sie genau wissen, 29:28.460 --> 29:30.580 dass sie das nie komplett erreichen werden. 29:31.140 --> 29:35.860 Sondern die müssen dann immer so Winkelzüge finden, damit das manchmal 29:35.860 --> 29:37.840 funktioniert, sage ich mal. 29:38.140 --> 29:41.300 Aber sie werden nie ein Werkzeug bauen können, das immer funktioniert. 29:41.300 --> 29:45.280 Und das ist schon eine wichtige Einsicht, auch für die Software 29:45.280 --> 29:45.740 -Technik. 29:47.100 --> 29:49.400 Aber jetzt zurück zum Formalen. 29:54.660 --> 29:56.400 Das Halteproblem ist das folgende. 29:56.480 --> 29:59.260 Wir definieren eine formale Sprache H. 30:00.120 --> 30:08.320 Sie besteht aus Wörtern der Form W-I-V, wobei W-I eine Gödelnummer 30:08.320 --> 30:09.820 einer Turing-Maschine ist. 30:10.820 --> 30:17.340 Und zwar sind das alle die W-I-V, für die gilt M-I, also die durch W-I 30:17.340 --> 30:21.500 beschriebene Turing-Maschine, angesetzt auf V-Held. 30:23.140 --> 30:26.120 Das ist die Halteproblem-Sprache. 30:27.440 --> 30:29.880 Und wir behaupten, dass H nicht entscheidbar ist. 30:30.940 --> 30:31.720 Warum ist das so? 30:34.420 --> 30:37.840 Wir stellen jetzt einfach eine Verbindung zu dieser Diagonalsprache 30:37.840 --> 30:38.160 her. 30:38.980 --> 30:42.100 Wieder durch einen Widerspruchsbeweis, also angenommen H sei 30:42.100 --> 30:42.860 entscheidbar. 30:44.220 --> 30:51.040 Wir konstruieren, angenommen das gilt, werden wir eine Turing-Maschine 30:51.040 --> 30:55.500 angeben, die das Komplement der Diagonalsprache akzeptiert. 30:58.660 --> 31:01.300 Und damit dann auch die Diagonalsprache selber. 31:04.620 --> 31:09.540 Also wir wollen eine Turing-Maschine haben, die entscheidet, ob W-I im 31:09.540 --> 31:11.600 Komplement der Diagonalsprache ist. 31:11.680 --> 31:14.640 Nach Definition von L-D ist das Äquivalent dazu. 31:16.740 --> 31:24.900 Wir wollen eine Turing-Maschine haben, die entscheidet, ob M-I W-I 31:24.900 --> 31:25.220 akzeptiert. 31:33.350 --> 31:36.450 Das können wir aber, wenn wir eine Turing-Maschine für das 31:36.450 --> 31:40.430 Halteproblem hätten, relativ leicht machen. 31:42.550 --> 31:47.190 Was wir nämlich tun ist, wir setzen erstmal diese Halteproblem-Turing 31:47.190 --> 31:49.810 -Maschine auf die Eingabe W-I W-I an. 31:54.210 --> 32:07.650 Und wenn uns das dann sagt, die hält nicht, dann weiß ich, dass die 32:07.650 --> 32:09.210 nicht ein L-D-Komplement ist. 32:09.670 --> 32:13.930 Das W-I nicht ein L-D-Komplement ist und ich sage, nein. 32:15.850 --> 32:19.410 Wenn die Halteproblem-Turing-Maschine aber sagt, jawohl, das hält, 32:21.050 --> 32:25.610 dann nehme ich einfach eine universelle Turing-Maschine und lasse die 32:25.610 --> 32:26.470 halt loslaufen. 32:28.330 --> 32:32.670 Simuliere das M-I und ich weiß ja, dass die irgendwann terminieren 32:32.670 --> 32:32.990 wird. 32:33.650 --> 32:35.830 Und die gibt mir dann das Ergebnis, das ich haben will. 32:39.050 --> 32:42.410 Das könnte ich ohne diese Halteproblem-Turing-Maschine nicht machen, 32:42.550 --> 32:47.030 weil dann könnte es ja sein, dass diese universelle Turing-Maschine 32:47.030 --> 32:49.330 auch nicht hält auf dieser Eingabe. 32:50.110 --> 32:52.910 Ich weiß aber nie, ob die lange genug gerechnet hat. 32:56.550 --> 32:57.610 Und das gibt dann Widerspruch. 32:57.610 --> 32:58.550 Frage dazu. 33:00.390 --> 33:05.390 Wir haben jetzt das Halteproblem formuliert, dass sich eine 33:10.020 --> 33:16.540 Frage anschaut, die wir eigentlich tatsächlich gerne beantwortet 33:16.540 --> 33:16.780 hätten. 33:17.820 --> 33:20.160 Und dann gezeigt, dass das zu einem Widerspruch führt. 33:20.220 --> 33:23.300 Weil wenn wir das Halteproblem lesen könnten, dann könnten wir das 33:23.300 --> 33:28.920 insbesondere auch für sehr spezielle Eingaben nutzen, wo man die 33:28.920 --> 33:30.480 Maschine auf sich selber loslässt. 33:30.480 --> 33:33.440 Und damit könnten wir dann die Diagonalsprache akzeptieren oder ihr 33:33.440 --> 33:33.680 Kompliment. 33:34.760 --> 33:35.660 Und das führt zu einem Widerspruch. 33:36.600 --> 33:39.820 Weil wir von dem ja schon wissen, dass es nicht entscheidbar ist. 33:39.900 --> 33:41.200 Also ein ganz netter Kunstgriff. 33:46.820 --> 33:50.580 Durch diese universelle Turing-Maschine können wir sozusagen dieses 33:50.580 --> 33:59.840 akademische Problem, Diagonalsprache, in Verbindung bringen mit dem 33:59.840 --> 34:01.840 eigentlich nützlichen Problem, dem Halteproblem. 34:05.460 --> 34:08.580 Jetzt gibt es eine Variante, das beschränkte Halteproblem. 34:11.300 --> 34:15.660 Da kriege ich eine zusätzliche Eingabe, nicht nur eine Maschine und 34:15.660 --> 34:20.000 eine Eingabe, sondern über so einen Trennmarker auch noch eine 34:20.000 --> 34:20.680 Schrittzahl. 34:22.400 --> 34:28.720 Und das ist dann die Menge aller Maschine, Eingabe, Schrittzahlpaare, 34:28.820 --> 34:32.680 für die gilt, die Maschine angesetzt auf V hält nach höchstens J 34:32.680 --> 34:33.020 Schritten. 34:33.020 --> 34:38.700 Und das Problem ist entscheidbar, weil ich da einfach eine universelle 34:38.700 --> 34:41.800 Turing -Maschine nehmen kann und die lasse ich für J Schritte laufen. 34:44.000 --> 34:47.980 Und ich akzeptiere, wenn die nach J simulierten Schritten akzeptiert. 34:49.060 --> 34:50.160 Frage dazu? 34:51.140 --> 34:52.420 Also das ist relativ simpel. 34:54.160 --> 34:57.300 Ja und jetzt gibt es eine ganze Reihe anderer unentscheidbarer 34:57.300 --> 34:57.700 Probleme. 34:59.520 --> 35:02.700 Und die Beweise dafür sind eigentlich erstaunlich simpel. 35:04.620 --> 35:07.720 Das kann man jeweils durch einen kleinen Kunstgriff, durch ein simples 35:07.720 --> 35:10.240 Programm zurückführen auf das Halteproblem. 35:11.320 --> 35:14.600 Und dieses Spiel werden wir dann auch in den Übungen und in der 35:14.600 --> 35:16.640 Klausur zu Genüge treiben. 35:16.640 --> 35:21.460 Sie kriegen irgendwie eine formale Sprache angegeben und dann ist die 35:21.460 --> 35:24.180 Frage, ist das Ding entscheidbar, ist das semi-entscheidbar, ist das 35:24.180 --> 35:25.020 unentscheidbar. 35:26.040 --> 35:29.880 Und dann müssen sie sich halt irgendwie was cleveres ausdenken. 35:30.340 --> 35:33.280 Also wenn es entscheidbar ist, müssen sie halt irgendwie sagen, wie. 35:34.420 --> 35:39.100 Beispiel durch so geschickte Tricks wie zwei Maschinen parallel laufen 35:39.100 --> 35:40.400 lassen, das hatten wir schon gesehen. 35:40.400 --> 35:44.940 Und wenn es unentscheidbar ist, wird es in der Regel so sein, dass sie 35:44.940 --> 35:49.360 es zurückführen auf ein Problem, wo die Unentscheidbarkeit bereits 35:49.360 --> 35:50.180 bewiesen ist. 35:50.740 --> 35:52.280 Meistens auf das Halteproblem. 35:53.220 --> 35:55.220 Oder vielleicht auf eines von denen hier. 35:56.980 --> 36:00.040 Leerheit, Unendlichkeit, Vollständigkeit oder Äquivalenz. 36:00.440 --> 36:01.980 Das sind alles unentscheidbare Probleme. 36:02.500 --> 36:05.280 Also gegen eine Turing-Maschine akzeptiert die gar nichts. 36:05.440 --> 36:07.320 Selbst das kann man nicht entscheiden. 36:07.320 --> 36:12.340 Auf den ersten Blick klingt das nach einem einfacheren Problem als das 36:12.340 --> 36:12.960 Halteproblem. 36:13.060 --> 36:15.820 Wir werden aber sehen, dass das das gleiche ist. 36:15.960 --> 36:20.080 Und genauso akzeptiert die unendlich viele Wörter. 36:22.180 --> 36:24.120 Akzeptiert die alles, was ich eingebe. 36:24.480 --> 36:26.520 Oder sind zwei Turing-Maschinen äquivalent? 36:26.760 --> 36:28.980 Akzeptieren die die gleichen Sprachen? 36:29.260 --> 36:30.640 Das ist alles unentscheidbar. 36:31.760 --> 36:34.800 Da werde ich Ihnen jetzt ein Beispiel mal vorführen, die Leerheit. 36:35.640 --> 36:37.240 Oder werdet ihr jetzt nervös? 36:37.320 --> 36:37.800 Wollt ihr das? 36:42.080 --> 36:49.140 Nehmen wir mal an, es gäbe eine Turing-Maschine M, die das 36:49.140 --> 36:50.200 Leerheitsproblem löst. 36:52.520 --> 36:58.280 Die die Menge aller Binärzahlen I akzeptiert. 36:58.280 --> 37:03.840 Für die gilt, dass die Sprache, die die Maschine mit der Gödel-Nummer 37:03.840 --> 37:07.200 I akzeptiert, gleich die leere Menge ist. 37:09.640 --> 37:15.280 Wir zeigen, das ist jetzt direkt eine Reduktion auf Diagonalsprache. 37:19.690 --> 37:21.890 Also hier nochmal die Definition der Diagonalsprache. 37:23.530 --> 37:27.330 Oder ihres Komplements ist die Menge aller Bi, für die gilt Mi 37:27.330 --> 37:28.210 akzeptiert Wi. 37:29.410 --> 37:31.830 Jetzt konstruieren wir einfach eine Turing-Maschine. 37:32.350 --> 37:34.770 Insofern sind Sie da in Ihrem Element, Sie wissen, wie man 37:34.770 --> 37:35.390 programmiert. 37:35.730 --> 37:38.810 Und diese Beweise sind immer ganz simple Programme eigentlich. 37:40.970 --> 37:43.530 Diese Turing-Maschine löscht die Eingabe, 37:46.570 --> 37:49.190 lässt dann Mi auf Wi laufen. 37:50.510 --> 37:52.330 Unabhängig davon, was Sie eingegeben haben. 37:54.510 --> 37:55.520 Das ist aber... 38:19.950 --> 38:21.850 Jetzt sind wir wieder zu schnell. 38:27.860 --> 38:32.320 Also ich lasse die Maschine Mi auf Wi laufen. 38:35.280 --> 38:38.020 Da kann es natürlich sein, dass die nicht terminiert. 38:42.670 --> 38:44.550 Dann terminiert das Ding halt nicht. 38:45.830 --> 38:46.910 Okay, genau. 38:50.090 --> 38:53.590 Wenn sie aber terminiert, dann könnte sie im Endzustand terminieren 38:53.590 --> 38:54.330 oder irgendwo anders. 38:54.570 --> 38:55.610 Sie könnte so auch halten. 38:57.630 --> 39:04.150 Wenn der Zustand, den sie hat, nachdem sie terminiert hat, nicht der 39:04.150 --> 39:06.770 Endzustand ist, dann geht man einfach in eine Endlosschleife. 39:07.510 --> 39:16.010 Das heißt, diese Maschine terminiert genau dann, wenn Mi auf Wi 39:16.010 --> 39:19.770 angesetzt, terminiert und das auch akzeptiert. 39:20.770 --> 39:24.090 Das ist aber gerade die Definition von LD-Quer. 39:29.390 --> 39:36.770 Das heißt, ich hätte jetzt eine Turing-Maschine, die LD-Quer 39:36.770 --> 39:42.070 akzeptiert, aber nicht immer hält. 39:42.210 --> 39:43.180 Das muss man jetzt beachten. 39:44.790 --> 39:47.390 Ja, wir hatten gerade universelle Turing-Maschinen gesehen. 39:48.310 --> 39:53.670 Das kann man natürlich auch beliebig stapeln, aber die sind eigentlich 39:53.670 --> 39:57.670 häufiger, als man es zuerst mal vermutet, wenn man nur diese abstrakte 39:57.670 --> 40:02.250 Definition sieht und dann die Beschreibung, was diese Maschine auf 40:02.250 --> 40:04.930 normierten Turing-Maschinen tun könnte. 40:07.370 --> 40:09.670 Dabei benutzt ihr die eigentlich jeden Tag. 40:10.790 --> 40:13.870 Im Browser, die JavaScript-Engine ist ja im Grunde auch nichts 40:13.870 --> 40:17.450 anderes, nur hat die eine etwas fancierere Gödelnummer, nämlich 40:17.450 --> 40:18.370 JavaScript -Code. 40:19.750 --> 40:22.510 Also generell Interpreter für Skriptsprachen sind im Grunde 40:22.510 --> 40:26.290 universelle Turing-Maschinen oder euer Lieblings-Super-Nintendo 40:26.290 --> 40:27.210 -Emulator auch. 40:30.710 --> 40:36.450 Es gibt aber auch noch andere, seltsamere Beispiele, zum Beispiel 40:36.450 --> 40:39.810 Turing -Maschinen-Simulatoren oder Game of Life in Game of Life. 40:39.910 --> 40:41.810 Ich glaube, jetzt habe ich vergessen, das Video zu kopieren. 40:53.330 --> 40:56.770 Schade, ich habe vergessen, das Video zu kopieren, aber hier ist die 40:56.770 --> 40:57.150 URL. 40:57.530 --> 40:59.770 Man kann Game of Life in Game of Life implementieren. 41:01.190 --> 41:02.410 Läuft dann ein bisschen langsamer. 41:03.210 --> 41:05.810 Aber natürlich, wir haben ja letztes Mal gesehen, dass es Turing 41:05.810 --> 41:08.070 -vollständig ist, also wieso sollte es das nicht können. 41:09.610 --> 41:10.450 Sieht lustig aus. 41:14.720 --> 41:17.980 Aber eigentlich fast noch lustiger als universelle Turing-Maschinen 41:17.980 --> 41:22.100 ist ja die Frage, ob wir ein Programm schreiben können, das seinen 41:22.100 --> 41:23.800 eigenen Quellcode wieder ausgibt. 41:24.880 --> 41:29.480 Oder eine Turing-Maschine, die ihre eigene Gödelnummer aufs Band 41:29.480 --> 41:29.880 schreibt. 41:30.600 --> 41:31.880 Und natürlich geht das. 41:33.200 --> 41:36.040 Hier ist ein Beispiel, wie man sowas in Python machen könnte. 41:38.080 --> 41:42.260 Das funktioniert so, dass dieser String hier, das hier ist der String, 41:42.780 --> 41:46.100 da wird dann hier die Repräsentation von irgendwas eingesetzt, durch 41:46.100 --> 41:46.980 String -Substitution. 41:47.560 --> 41:49.460 Und das hier ist nur ein Escapedes-Prozent-Zeichen. 41:50.140 --> 41:52.720 Das hier ist ein Teilenumbruch, backslash n. 41:53.620 --> 41:55.900 Und jetzt wird dieser String in sich selber eingesetzt. 41:56.580 --> 41:59.840 Und diese Repräsentation des Strings ist wieder in Leerzeichen 41:59.840 --> 42:00.100 gequotet. 42:00.740 --> 42:03.500 Und dann kommt wieder genau das gleiche raus, wenn man das einmal 42:03.500 --> 42:05.100 durch den Python-Interpreter jagt. 42:09.110 --> 42:14.190 Der Rekursionssatz besagt jetzt, dass es unter anderem Turing 42:14.190 --> 42:16.450 -Maschinen gibt, die ihre eigene Gödelnummer aufs Band schreiben. 42:18.470 --> 42:21.610 Daraus folgt dann aber auch ein bisschen Überumwege, dass es in jedem 42:21.610 --> 42:23.870 Turing -mächtigen System Quines geben muss. 42:26.110 --> 42:31.450 Und der Rekursionssatz besagt außerdem, dass sich jede Turing-Maschine 42:31.450 --> 42:35.710 in eine andere Turing-Maschine umbauen lässt, die die gleiche Funktion 42:35.710 --> 42:38.710 erfüllt und zusätzlich noch ihre Gödelnummer aufs Band schreiben kann. 42:39.890 --> 42:43.530 Das heißt aber auch, dass eine Turing-Maschine ihre eigene 42:43.530 --> 42:44.810 Beschreibung verwenden kann. 42:46.090 --> 42:50.530 Die Java-Coder im Raum werden jetzt an Reflections denken vermutlich. 42:51.170 --> 42:55.490 Denn da kann man ja auch zur Laufzeit auf die Programmbeschreibung 42:55.490 --> 42:56.090 zugreifen. 42:56.090 --> 42:58.650 Also was ist in dieser Klasse jetzt alles drin und so. 43:00.810 --> 43:04.510 Und das kann man auch mit Turing-Maschinen machen. 43:09.780 --> 43:13.320 Als letztes noch, wenn wir letztes Mal Game of Life gemacht haben. 43:14.160 --> 43:19.440 Es ist natürlich dann auch unentscheidbar, ob sich zwei gegebene 43:19.440 --> 43:22.760 Konfigurationen von Game of Life anhand der Spielregeln ineinander 43:22.760 --> 43:23.640 überführen lassen. 43:23.640 --> 43:28.360 Denn sonst könnten wir ja einfach die Turing-Maschine so präparieren, 43:28.640 --> 43:32.000 dass sie in dem Zustand ist, in dem sie jetzt loslaufen würde. 43:32.360 --> 43:36.400 Und uns dann überlegen, in welchem Zustand das System wäre, wenn sie 43:36.400 --> 43:39.040 jetzt auf dem leeren Band irgendwie akzeptierend hält. 43:39.580 --> 43:41.660 Und dann fragen, lassen die sich ineinander überführen. 43:46.000 --> 43:50.420 Die Reduktion ist, glaube ich, einfach zu sehen auf das Halteproblem. 43:52.200 --> 44:00.380 Das heißt, so komplett seltsame oder banal klingende Fragen, wie kann 44:00.380 --> 44:03.200 ich in Game of Life von hier nach da kommen, sind leider auch 44:03.200 --> 44:03.840 unentscheidbar. 44:05.240 --> 44:08.100 Und das wird sich durch einiges noch fortziehen. 44:09.560 --> 44:11.580 Und damit übergebe ich jetzt an Tobias. 44:18.350 --> 44:24.590 Also, wir haben ja gerade eben schon überlegt, dass ganz, ganz viele 44:24.590 --> 44:27.910 Beweise der Form kommen würden, dass wir das Halteproblem verwenden, 44:28.330 --> 44:31.030 um zu zeigen, dass irgendwas anderes unentscheidbar ist. 44:31.770 --> 44:34.350 Wir haben gerade eben schon ganz kurz in der Vorlesung so einen Ansatz 44:34.350 --> 44:34.950 davon gesehen. 44:35.310 --> 44:36.950 Der Beweis war allerdings noch nicht fertig. 44:37.650 --> 44:41.370 Und ich möchte euch jetzt im Endeffekt einfach zeigen, wie man fast 44:41.370 --> 44:46.470 jegliche Aussagen über Sprachen, über Turing-Maschinen zeigen kann, 44:46.530 --> 44:47.690 dass sie nicht entscheidbar sind. 44:47.690 --> 44:52.050 Also, wann immer jemand fragt, können wir entscheiden, ob eine Turing 44:52.050 --> 44:55.770 -Maschine das und das macht, könnt ihr eigentlich fast immer sagen, es 44:55.770 --> 44:56.470 geht nicht. 44:57.390 --> 44:59.890 Fast immer sind die Sprachen unentscheidbar. 45:01.090 --> 45:03.670 Es gibt sogar einen Satz, der ist ein bisschen... 45:03.670 --> 45:04.970 wenn man den googelt... 45:04.970 --> 45:08.470 die Version ist fast eins zu eins von Wikipedia geklaut. 45:09.070 --> 45:13.050 Klingt ja ein bisschen komisch, weil der Satz sagt, es ist unmöglich, 45:13.210 --> 45:17.550 eine beliebige nicht-triviale Eigenschaft der erzeugten Funktion einer 45:17.550 --> 45:21.650 Turing -Maschine oder eines Algorithmus in einem anderen Berechnungs 45:21.650 --> 45:23.810 -Modell algorithmisch zu entscheiden. 45:24.330 --> 45:26.730 Klingt erstmal ein bisschen doof, vor allem weil wir so Sachen haben 45:26.730 --> 45:28.910 wie nicht-triviale Eigenschaften und alles mögliche. 45:29.550 --> 45:31.090 Erstmal die Klammer kann man weglassen. 45:31.610 --> 45:34.550 Wir wissen schon mal, dass alle Berechnungsmodelle, also alle 45:34.550 --> 45:36.830 hinreichend mächtigen Berechnungsmodelle gleich sind. 45:38.250 --> 45:40.870 Deswegen lassen wir die mal weg und analysieren den Satz. 45:43.510 --> 45:48.530 Diese drei Worte hier sagen mir im Endeffekt, es ist unmöglich, Turing 45:48.530 --> 45:49.510 -Maschinen zu entscheiden. 45:49.790 --> 45:54.690 Es geht um Sprachen, die aus Turing-Maschinen bestehen und die sind 45:54.690 --> 45:56.090 anscheinend schwer zu entscheiden. 45:56.770 --> 45:59.970 Also es geht um eine Klasse unentscheidbarer Sprachen, die mit Turing 45:59.970 --> 46:00.930 -Maschinen zu tun haben. 46:05.550 --> 46:08.710 Die Funktion von einer Turing-Maschine scheint in dem Zusammenhang 46:08.710 --> 46:09.370 wichtig zu sein. 46:09.370 --> 46:12.970 Es funktionieren auch viele Sachen, die nichts über die Funktion von 46:12.970 --> 46:14.030 Turing -Maschinen aussagen. 46:14.470 --> 46:19.610 Aber der Satz von Rice selber geht nur um die Funktion, die von Turing 46:19.610 --> 46:20.690 -Maschinen berechnet wird. 46:24.630 --> 46:27.850 Wir sehen auch, dass der Satz ziemlich vage formuliert ist. 46:28.810 --> 46:33.690 Ich sage schon, der heißt ungefähr so und dann geht es noch um nicht 46:33.690 --> 46:34.530 -triviale Eigenschaften. 46:35.010 --> 46:37.750 Jetzt muss man sich überlegen, was sind nicht-triviale Eigenschaften? 46:39.350 --> 46:43.110 Von der Funktion von einer Turing-Maschine, ihr sollt den Satz nicht 46:43.110 --> 46:43.790 so verwenden. 46:44.290 --> 46:48.410 Ihr solltet nie auf ein Übungsblatt schreiben, funktioniert nicht laut 46:48.410 --> 46:49.270 Satz von Rice. 46:51.310 --> 46:53.790 Es wäre mir ganz recht, wenn ihr das nicht tut, weil wir haben unseren 46:53.790 --> 46:56.010 Tutoren schon gesagt, sie sollen euch dafür null Punkte geben. 46:57.530 --> 47:01.110 Gut, was ihr stattdessen macht, ist ich werde euch zwei Beweismuster 47:01.110 --> 47:03.990 vorstellen, die für jedes dieser Probleme einfach genauso 47:03.990 --> 47:04.630 funktionieren. 47:04.730 --> 47:07.950 Ihr könnt euch eins davon aussuchen und dann habt ihr eine 47:07.950 --> 47:08.710 Beweismuster. 47:08.950 --> 47:10.170 Die funktionieren immer. 47:11.950 --> 47:12.790 Fast immer. 47:14.730 --> 47:17.650 Wir wollen jetzt mal eine Sprache entscheiden, und das ist auch eine 47:17.650 --> 47:18.590 interessante Sprache. 47:19.310 --> 47:22.410 Das ist die Sprache, die alle Virenscanner entscheiden wollen. 47:22.930 --> 47:27.650 Und zwar wollen wir für ein Programm wissen, ob das auf dem leeren 47:27.650 --> 47:29.190 Band Virus aufs Band schreibt. 47:29.890 --> 47:32.930 Weil diese Turing-Maschinen betrachten wir als Viren und ein 47:32.930 --> 47:37.330 Virenscanner würde die unglaublich gern rausfinden und genau diese 47:37.330 --> 47:38.470 Programme nicht erlauben. 47:38.550 --> 47:40.910 Und alle Programme, die nicht Virus aufs Band schreiben, würden wir 47:40.910 --> 47:41.890 gerne erlauben. 47:43.290 --> 47:45.810 Okay, also es ist schon mal sehr interessant, diese Sprache zu 47:45.810 --> 47:46.210 entscheiden. 47:48.310 --> 47:53.410 Der Satz von Rice sagt uns jetzt aber im Endeffekt, Virus aufs Band zu 47:53.410 --> 47:55.490 schreiben, das ist eine Funktion, die berechnet wird. 47:56.130 --> 47:58.470 Das ist eine nicht triviale Eigenschaft von der Funktion. 47:59.130 --> 48:01.150 Wahrscheinlich, also zumindest nehmen wir das an, dass sie nicht 48:01.150 --> 48:01.650 trivial ist. 48:03.210 --> 48:06.010 Der Satz von Rice sagt uns jetzt, das ist unentscheidbar. 48:07.630 --> 48:13.890 Der Satz von Rice funktioniert genau über Beweisformen wie diese hier 48:13.890 --> 48:14.250 jetzt. 48:14.950 --> 48:17.990 Okay, die erste Beweisform, die ich euch zeigen will, funktioniert 48:17.990 --> 48:18.970 über das Halteproblem. 48:20.990 --> 48:24.750 Wir nehmen an, die Sprache L-Virus, also die Sprache aller Turing 48:24.750 --> 48:27.550 -Maschinen, die Virus aufs leere Band schreiben, sei entscheidbar. 48:28.630 --> 48:31.890 Und müssen jetzt diese Annahme darauf zurückführen, dass wenn sie 48:31.890 --> 48:35.150 entscheidbar sind, dann können wir auch das Halteproblem lösen. 48:35.850 --> 48:38.390 Wir haben aber gerade eben gehört, wir können das Halteproblem nicht 48:38.390 --> 48:40.390 lösen, deswegen muss diese Annahme falsch sein. 48:41.590 --> 48:41.810 Gut. 48:44.370 --> 48:49.050 Wir nehmen uns mal eine ganz allgemeine Instanz vom Halteproblem her. 48:49.730 --> 48:52.190 Mithilfe dieser Instanz wollen wir jetzt eine Turing-Maschine 48:52.190 --> 48:52.910 konstruieren. 48:53.630 --> 48:57.570 Also wir haben eine Instanz und wollen eine Turing-Maschine daraus 48:57.570 --> 48:57.830 machen. 48:58.450 --> 49:02.450 Diese Turing-Maschine, die schreibt als erstes mal diese Instanz aufs 49:02.450 --> 49:02.650 Band. 49:04.030 --> 49:06.590 Das ist einfach genug, das funktioniert irgendwie. 49:07.310 --> 49:14.270 Man kann jede Ausgabe mit einer Turing-Maschine irgendwie erzeugen. 49:15.390 --> 49:17.550 Gut, die Turing-Maschine könnte größer werden, aber das ist jetzt noch 49:17.550 --> 49:18.110 nicht das Problem. 49:20.690 --> 49:23.490 Außerdem haben wir gelernt, es gibt universelle Turing-Maschinen. 49:24.430 --> 49:28.350 Also simulieren wir einfach erst mal diese Turing-Maschine Mn auf der 49:28.350 --> 49:29.110 Eingabe W. 49:30.630 --> 49:33.890 Gut, jetzt machen wir genau dasselbe, wie das Halteproblem denkt. 49:35.510 --> 49:37.990 Wir wissen nicht, ob diese Turing-Maschine hält. 49:38.750 --> 49:42.770 Wenn sie hält, dann gehört sie offensichtlich zur Haltesprache. 49:42.890 --> 49:45.770 Wenn sie nicht hält, gehört sie offensichtlich nicht zu den haltenden 49:45.770 --> 49:46.450 Turing -Maschinen. 49:47.310 --> 49:48.150 Auf dieser Eingabe. 49:49.950 --> 49:53.830 Nachdem sie gehalten hat, löschen wir das ganze Band und schreiben 49:53.830 --> 49:54.730 Virus auf das Band. 49:55.830 --> 49:58.850 Wir wissen allerdings nie, ob diese Funktion irgendwann mal ausgeführt 49:58.850 --> 49:59.110 wird. 49:59.690 --> 50:01.750 Es kann ja sein, dass dieses hier unendlich lang läuft. 50:02.430 --> 50:05.590 Wenn es unendlich lang läuft, schreiben wir nicht Virus aufs Band und 50:05.590 --> 50:06.830 wir sind ein legales Programm. 50:07.630 --> 50:11.490 Wenn diese Instanz hier hält, dann schreiben wir Virus aufs Programm 50:11.490 --> 50:12.450 und wir sind ein Virus. 50:15.400 --> 50:19.500 Genau, also die Turing-Maschine ist genau dann ein Virus, wenn diese 50:19.500 --> 50:21.300 Instanz vom Halteproblem hält. 50:22.820 --> 50:25.140 Jetzt kann man sich ganz einfach überlegen, wenn es eine Turing 50:25.140 --> 50:29.820 -Maschine im Virenscanner gäbe, die die Sprache L-Virus entscheidet, 50:30.760 --> 50:35.380 dann kann sie entscheiden, ob diese Turing-Maschine TIN ein Virus ist 50:35.380 --> 50:35.860 oder nicht. 50:37.840 --> 50:42.820 Und das ist genau gleichbedeutend mit der Aussage, dass diese 50:42.820 --> 50:46.300 Halteproblem -Instanz hält oder nicht, haben wir uns gerade überlegt. 50:47.480 --> 50:51.320 Das heißt, dieser virenscanner, dieser hypothetische virenscanner, den 50:51.320 --> 50:54.420 es nie geben kann, der könnte auch das Halteproblem entscheiden. 50:55.420 --> 50:57.760 Und deswegen kann es ihn nicht geben, weil das Halteproblem ist 50:57.760 --> 50:57.990 unentscheidbar. 50:59.490 --> 51:04.990 Genau, das ist einer von den zwei ganz einfachen Ansätzen, wie man 51:04.990 --> 51:12.050 jegliche Sprachen von Turing-Maschinen beweisen kann, dass sie 51:12.050 --> 51:12.850 unentscheidbar sind. 51:13.410 --> 51:17.630 Also man nimmt sich eine Instanz vom Halteproblem her, generiert damit 51:17.630 --> 51:22.650 eine Turing-Maschine, die die verwendet, simuliert und danach 51:22.650 --> 51:23.550 irgendwas tut. 51:23.550 --> 51:28.030 Also diese ganzen ersten paar Schritte kann man sich auswendig merken. 51:28.810 --> 51:31.690 Die Sätze hier sind einigermaßen kurz gefasst, wenn ihr das irgendwie 51:31.690 --> 51:35.310 als Lösung aufschreiben wolltet, solltet ihr vielleicht noch die Sätze 51:35.310 --> 51:37.490 irgendwie ausführlicher machen, sodass sie nicht mehr auf eine Folie 51:37.490 --> 51:37.830 passen. 51:39.410 --> 51:47.350 Aber im Endeffekt, diesen Teil könnt ihr euch auswendig merken und nur 51:47.350 --> 51:50.370 diese dritte Zeile von der Turing-Maschine müsst ihr immer anpassen. 51:50.370 --> 51:56.630 Die Zeile, die sagt, nachdem das Halteproblem gehalten hat oder nicht 51:56.630 --> 52:01.030 gehalten hat, da mache ich was, was der Sprache entspricht oder nicht. 52:02.130 --> 52:04.550 Also dieses System funktioniert immer. 52:05.690 --> 52:09.410 Ein weiteres System baut auf dem auf, was Lorenz euch gerade eben 52:09.410 --> 52:10.110 vorgestellt hat. 52:10.110 --> 52:16.570 Man kann Turing-Maschinen bauen, die ihre eigene Beschreibung aufs 52:16.570 --> 52:17.050 Band schreiben. 52:17.510 --> 52:20.050 Also Turing-Maschinen, die ihre eigene Gödelnummer aufs Band 52:20.050 --> 52:20.370 schreiben. 52:21.510 --> 52:28.110 Und was noch interessanter ist, man kann für jede Funktion eine Turing 52:28.110 --> 52:31.250 -Maschine bauen, die zuerst ihre eigene Beschreibung aufs Band 52:31.250 --> 52:33.790 schreibt und dann immer noch diese Funktion berechnet. 52:34.690 --> 52:38.290 Mit der eigenen Gödelnummer als Eingabe. 52:38.870 --> 52:41.770 Also das geht auch, es geht nicht nur, dass man eine Turing-Maschine 52:41.770 --> 52:45.090 baut, die sich selber aufs Band schreibt, sondern die kann danach noch 52:45.090 --> 52:46.630 eine beliebige Funktion ausführen. 52:47.790 --> 52:50.210 Also eine beliebig partiell berechenbare Funktion. 52:50.330 --> 53:00.410 Partiell berechenbar ist genau das, dass man eine Turing berechenbare 53:00.410 --> 53:00.850 Funktion. 53:02.370 --> 53:04.810 Gut, also für jede Funktion können wir das machen. 53:08.410 --> 53:12.490 Also schreibt zuerst ihre eigene Beschreibung aufs Band und wendet 53:12.490 --> 53:15.710 dann die Funktion F auf dieser Beschreibung an. 53:19.250 --> 53:25.090 Und jetzt kommt ein ganz ganz cooler Beweisansatz eigentlich, weil der 53:25.090 --> 53:31.710 was über Turing-Maschinen aussagt, was so erstmal absolut nicht 53:31.710 --> 53:32.490 trivial ist. 53:32.490 --> 53:37.610 Also das Halteproblem, das war irgendwie was Greifbares und jetzt der 53:37.610 --> 53:41.550 Beweisansatz, ich hoffe, dass ihr alle mitkommt, der ist abgefahren. 53:43.970 --> 53:48.310 Also wir nehmen wieder an, wir haben dasselbe unentscheidbare Problem, 53:49.110 --> 53:50.930 ist eine Turing-Maschine ein Virus? 53:52.270 --> 53:56.370 Und wir nehmen an, sie wäre entscheidbar, dann gibt es natürlich eine 53:56.370 --> 53:59.590 Turing -Maschine T-Scan, die die Sprache entscheidet. 54:01.630 --> 54:07.050 Und wir konstruieren jetzt für diesen einzelnen Virenscanner ein 54:07.050 --> 54:08.510 Virus, der nicht erkannt wird. 54:09.530 --> 54:13.670 Oder ein Programm, das falsch erkannt wird, also ein Programm, das als 54:13.670 --> 54:15.410 Virus erkannt wird, obwohl es keiner war. 54:18.170 --> 54:24.750 Dazu konstruieren wir die Turing-Maschine T-Hidden, diese konstruieren 54:24.750 --> 54:30.450 wir aber erst, nachdem wir uns den Scanner gewählt haben. 54:30.830 --> 54:34.470 Also wir sagen, für jeden Scanner gibt es so eine Turing-Maschine T 54:34.470 --> 54:38.170 -Hidden, das heißt, in der Beschreibung von T-Hidden können wir auf 54:38.170 --> 54:40.950 diesen einen Scanner eingehen, das wird ganz wichtig sein. 54:44.830 --> 54:48.210 Das erste, was die Turing-Maschine macht, ist die eigene Beschreibung 54:48.210 --> 54:50.390 auf das Band schreiben, weil wir haben gesagt, das funktioniert auf 54:50.390 --> 54:50.810 jeden Fall. 54:51.670 --> 54:53.210 Das sagt uns der Rekursionssatz. 54:54.290 --> 54:58.490 Das zweite, was die Turing-Maschine macht, ist, sie schreibt den 54:58.490 --> 55:00.470 Scanner, der sie erkennen soll, auf das Band. 55:04.990 --> 55:08.030 Also wir haben schon gesagt, wir wählen uns den Scanner aus und 55:08.030 --> 55:12.390 konstruieren dann ein Virus, der genau für diesen Scanner funktioniert 55:12.390 --> 55:14.230 und genau das machen wir hier. 55:14.370 --> 55:18.770 Also wir schreiben zuerst die eigene Beschreibung aufs Band und dann 55:18.770 --> 55:19.270 den Scanner. 55:25.470 --> 55:29.830 Dann simulieren wir den Scanner auf unserer eigenen Beschreibung. 55:31.050 --> 55:33.630 Das funktioniert wiederum, weil es universelle Turing-Maschinen gibt 55:33.630 --> 55:34.650 und das ist relativ klar. 55:37.170 --> 55:40.290 Dieser Scanner spuckt jetzt eine von zwei Antworten aus. 55:40.290 --> 55:44.750 Er entscheidet ja die Sprache, das heißt er hält auf jeden Fall und er 55:44.750 --> 55:49.010 sagt uns dann, entweder er akzeptiert, heißt es war ein Virus oder er 55:49.010 --> 55:51.390 akzeptiert nicht, heißt es war kein Virus. 55:52.710 --> 55:55.070 Und genau diese Aussage führen wir ad absurdum. 55:55.750 --> 56:00.570 Wenn der Scanner sagt, wir waren ein Virus, dann halten wir einfach 56:00.570 --> 56:01.930 und schreiben nicht Virus aufs Band. 56:03.330 --> 56:07.250 Wir waren überhaupt kein Virus, tut uns echt leid. 56:07.710 --> 56:08.830 Das ist also ein false positive. 56:10.790 --> 56:14.490 Der Virenscanner sagt, wir waren ein Virus, dabei waren wir ganz brav. 56:16.130 --> 56:20.570 Und der andere Fall, der Scanner akzeptiert nicht, der Scanner sagt, 56:20.650 --> 56:22.630 wir sind kein Virus, wir sind ein legales Programm. 56:23.810 --> 56:27.190 Okay, dann können wir ja machen, was wir wollen und unter anderem 56:27.190 --> 56:29.690 können wir auch einfach das ganze Band löschen und Virus aufs Band 56:29.690 --> 56:30.010 schreiben. 56:31.630 --> 56:34.630 Wir waren also der super fiese Virus, der von dem Virenscanner nicht 56:34.630 --> 56:35.170 erkannt wurde. 56:39.450 --> 56:44.430 Und wir haben jetzt also bewiesen, dass es keinen perfekten 56:44.430 --> 56:45.690 Virenscanner geben kann. 56:46.990 --> 56:49.250 Auf zwei unterschiedliche Varianten. 56:50.110 --> 56:53.430 Ich finde, beide Varianten sind sehr interessant und sagen auch etwas 56:53.430 --> 56:58.130 über Turing-Maschinen, über Turing-Berechenbarkeit aus. 56:58.130 --> 57:01.110 Also die Halte-Problem-Variante sagt natürlich etwas sehr, sehr 57:01.110 --> 57:01.870 Wichtiges aus. 57:01.990 --> 57:07.830 Und zwar, wie vorhin schon gesagt, das ist ein sehr interessantes 57:07.830 --> 57:11.230 Problem, das wir gerne lösen wollen würden, von dem wir aber wissen, 57:11.290 --> 57:12.590 wir werden es nie lösen können. 57:14.290 --> 57:18.990 Und diese Variante von dem Beweis ist ein bisschen mehr Matrix-mäßig. 57:18.990 --> 57:27.230 Also wir haben ein System, das uns überprüfen soll, das wir aber 57:27.230 --> 57:29.690 selber kennen und Ad absurdum führen können. 57:30.870 --> 57:34.050 Und das ist ein bisschen mehr an dem Beweis mit dem Barbier, der 57:34.050 --> 57:38.170 einfach ein Absurditätsmerkmal herstellt. 57:38.710 --> 57:42.290 Also wir kennen eine Aussage und führen die Ad absurdum. 57:43.810 --> 57:47.230 Und deswegen finde ich beide Beweise eigentlich ganz schön. 57:49.190 --> 57:52.430 Ihr könnt euch aussuchen, welches Beweismuster ihr schöner findet. 57:53.230 --> 57:58.470 Die funktionieren normalerweise beide für alle möglichen Probleme 57:58.470 --> 57:59.350 dieser Form. 58:00.350 --> 58:07.210 Also die Form ist, beweisen Sie, dass nicht Turing entscheidbar ist 58:07.210 --> 58:13.390 und dann irgendeine Sprachklasse, die über Turing-Maschinen läuft. 58:15.530 --> 58:20.190 Passt allerdings ein bisschen damit auf, man kann so ein paar Tricks 58:20.190 --> 58:22.890 machen, wo es nicht mehr funktioniert. 58:22.890 --> 58:28.650 Also so zum Beispiel ganz einfach, beweisen Sie, die Sprache aller 58:28.650 --> 58:33.230 Turing -Maschinen, deren Gödelnummer an der vierten Stelle eine 0 hat, 58:34.290 --> 58:35.850 ist nicht entscheidbar. 58:36.070 --> 58:38.870 Das funktioniert halt nicht, weil eine Gödelnummer, die an der vierten 58:38.870 --> 58:41.470 Stelle eine 0 hat, ist eine reguläre Sprache. 58:41.610 --> 58:43.310 Das ist jetzt nicht so kompliziert. 58:44.470 --> 58:48.050 Also passt ein bisschen auf, es gibt Sprachen, die entscheidbar sind, 58:48.550 --> 58:50.870 aber ganz, ganz viele Sprachen, die mit Turing-Maschinen 58:50.870 --> 58:53.330 zusammenhängen, sind nicht entscheidbar. 58:54.110 --> 58:58.290 Und fast alle davon lassen sich mit genau diesen zwei Beweisformen 58:58.290 --> 58:59.130 immer beweisen. 59:00.390 --> 59:03.290 Sie sind einfach Mittel für alles. 59:04.250 --> 59:06.890 Gut, das war es für mich heute eigentlich.