WEBVTT 00:01.080 --> 00:05.100 Ja, was haben wir am Montag gemacht? 00:05.220 --> 00:09.260 Da haben wir im Wesentlichen über Turing-Maschinen geredet. 00:10.480 --> 00:15.340 Das bisher komplexeste Maschinenmodell, das wir betrachtet haben, hier 00:15.340 --> 00:20.800 ist zur Erinnerung nochmal die Übersicht aufgelegt. 00:21.480 --> 00:26.300 Wir haben also, wie beim endlichen Automaten, eine Kontrolleinheit mit 00:26.300 --> 00:28.520 einer endlichen Menge interner Zustände. 00:31.780 --> 00:37.140 Wir haben aber diesmal, anders als beim endlichen Automaten, nicht nur 00:37.140 --> 00:40.460 die Möglichkeit zu lesen, sondern auch zu schreiben auf das 00:40.460 --> 00:40.680 Eingabeband. 00:41.460 --> 00:44.580 Das heißt, wir haben nicht eine reine Eingabe, sondern ein Eingabe- 00:44.580 --> 00:45.440 und Arbeitsband. 00:46.320 --> 00:49.460 Und das kann sich auch nicht nur in eine Richtung bewegen, sondern es 00:49.460 --> 00:51.220 kann sich vor- und zurückbewegen. 00:57.460 --> 01:01.920 Wir haben gesehen, es gibt verschiedene Varianten von dieser Maschine, 01:02.020 --> 01:08.620 die aber im Wesentlichen alle gleich mächtig sind, bis auf die lineare 01:08.620 --> 01:09.000 Beschränkung. 01:09.920 --> 01:13.340 Wenn ich also sage, mein Eingabeband ist auf beiden Seiten beschränkt, 01:13.880 --> 01:16.740 dann ist die Maschine nur eingeschränkt. 01:22.810 --> 01:25.790 Hier auch nochmal zur Erinnerung, kurz die Definition. 01:27.390 --> 01:31.330 Wir haben also zusätzlich zum Eingabe-Alphabet das Band-Alphabet. 01:31.530 --> 01:36.050 Das heißt, die Turing-Maschine kann noch andere Zeichen, außer den 01:36.050 --> 01:37.910 Eingabezeichen, auf diesem Band ablegen. 01:38.810 --> 01:42.630 Insbesondere dieses Sternzeichen, was uns sagt, hier ist undefiniert, 01:42.710 --> 01:44.430 hier ist Ende, da steht nichts drin. 01:47.690 --> 01:53.950 Und die Übergangsfunktion ist eben eine Funktion Delta, die zu jedem 01:53.950 --> 02:00.910 Zustand und Band-Alphabet Paar jeweils in einen neuen Zustand übergeht 02:00.910 --> 02:04.770 und ein neues Symbol auf das Band schreibt. 02:05.190 --> 02:08.570 Und dann definiert, in welche Richtung sich der Schreibbläsekopf 02:08.570 --> 02:09.010 bewegt. 02:09.110 --> 02:12.370 Bewegt er sich nach links, bewegt er sich nach rechts oder bewegt er 02:12.370 --> 02:13.210 sich überhaupt nicht? 02:16.180 --> 02:19.580 Gut, ich denke, das können wir alles überspringen. 02:20.320 --> 02:23.640 Wir haben gesehen, dass die Turing-Maschinen unter anderem A hoch N, B 02:23.640 --> 02:33.780 hoch N, C hoch N erzeugen können oder erkennen können. 02:37.170 --> 02:39.390 Ja, und hier eben nochmal der Überblick. 02:40.770 --> 02:42.410 Soweit waren wir im Wesentlichen gekommen. 02:42.410 --> 02:46.890 Wir haben also jetzt die verschiedenen Sprachklassen betrachtet, die 02:46.890 --> 02:49.870 regulären Sprachen, die kontextfreien Sprachen, die kontextsensitiven 02:49.870 --> 02:52.170 Sprachen und die allgemeinen Sprachen. 02:53.810 --> 02:58.890 Und wir haben im Prinzip zu jeder Sprachklasse bestimmte Grammatiken 02:58.890 --> 03:01.970 und bestimmte Automaten, die diese erkennen. 03:05.950 --> 03:07.990 Womit wir uns heute beschäftigen, 03:11.210 --> 03:14.470 ist Berechenbarkeit und Komplexität. 03:14.670 --> 03:18.810 Das heißt, wir schauen uns an, gibt es eventuell noch 03:18.810 --> 03:22.190 leistungsfähigere Automaten als die Turing-Maschinen? 03:23.030 --> 03:27.250 Gibt es Probleme, die man unter Umständen überhaupt nicht berechnen 03:27.250 --> 03:29.470 kann mit überhaupt gar keiner Maschine? 03:30.550 --> 03:35.850 Kann man die Probleme irgendwie einteilen in einfachere Probleme und 03:35.850 --> 03:37.010 komplexere Probleme? 03:38.850 --> 03:42.390 Wir stoßen also so ein bisschen auch an die Grenzen der Informatik 03:42.390 --> 03:42.630 vor. 03:42.770 --> 03:45.490 Was ist überhaupt machbar mit einem Computer und was ist nicht mehr 03:45.490 --> 03:45.970 machbar? 03:47.310 --> 03:52.230 Das ist teilweise ein bisschen theoretisch und ein bisschen trocken. 03:52.230 --> 03:58.490 Ich bin nicht so 100% glücklich mit dem Kapitel, weil man eben da 03:58.490 --> 04:02.750 irgendwo eine Gratwanderung machen muss zwischen auf der einen Seite 04:02.750 --> 04:07.130 sehr wichtigen, grundlegenden Resultaten aus der Informatik, auf der 04:07.130 --> 04:11.770 anderen Seite der Frage, lohnt es sich dafür, irgendwie seitenweise 04:11.770 --> 04:15.790 Beweise zu machen, um dann letztendlich irgendwie einen Satz zu 04:15.790 --> 04:16.270 beweisen. 04:17.630 --> 04:23.270 Das heißt, wir werden hier teilweise ein bisschen nur ungenau auf 04:23.270 --> 04:24.490 einige Dinge eingehen. 04:26.670 --> 04:29.910 Und Sie werden auch feststellen, ich habe in der vergangenen Nacht da 04:29.910 --> 04:31.350 noch einige Dinge verändert. 04:31.550 --> 04:34.630 Also es wird nicht ganz identisch sein mit dem, was Sie eventuell 04:34.630 --> 04:36.230 ausgedruckt haben, was im Netz steht. 04:38.830 --> 04:41.850 Okay, wir hatten das letzte Mal schon ganz kurz darüber geredet, was 04:41.850 --> 04:44.430 sind eigentlich wesentliche Eigenschaften eines Algorithmus. 04:44.430 --> 04:48.570 Das müssen wir uns ja anschauen, wenn wir uns überlegen, kann es oder 04:48.570 --> 04:51.590 was für Probleme lassen sich durch Algorithmen lösen. 04:53.410 --> 04:55.850 Und wichtige Punkte war eben da die Endlichkeit. 04:57.050 --> 04:59.610 Endlichkeit einmal auf der Seite der Beschreibung. 05:11.040 --> 05:15.800 Das heißt, wir möchten das Verfahren, den Algorithmus in endlicher 05:15.800 --> 05:18.880 Länge beschreiben können. 05:18.880 --> 05:21.580 Und auf der anderen Seite soll das Verfahren auch nur endliche Zeit 05:21.580 --> 05:21.980 laufen. 05:22.480 --> 05:25.620 Das waren so grundlegende Bedingungen an den Algorithmus neben 05:25.620 --> 05:28.320 Allgemeinheit und Determiniertheit. 05:29.820 --> 05:31.400 Das waren ein paar Beispiele. 05:33.880 --> 05:38.840 Und so haben wir versucht, den Algorithmus intuitiv zu definieren. 05:39.600 --> 05:42.300 Wir haben eine Menge von konkreten Problemausprägungen. 05:42.980 --> 05:48.760 Das heißt Daten, die das Problem beschreiben, beispielsweise eine 05:48.760 --> 05:55.200 Menge von Städten oder eine Folge von Zahlen, die wir sortieren 05:55.200 --> 05:55.540 wollen. 05:56.380 --> 06:01.860 Und wir haben eine Menge von Lösungen, beispielsweise die Reihenfolge 06:01.860 --> 06:02.540 dieser Zahlen. 06:03.560 --> 06:06.780 Und ein Algorithmus zu einer bestimmten Problemklasse ist ein 06:06.780 --> 06:08.640 allgemeines, determiniertes Verfahren. 06:08.640 --> 06:13.920 Das, wenn man es auf die richtigen Anfangsdaten anwendet, nach endlich 06:13.920 --> 06:18.640 vielen elementaren Schritten anhält und die entsprechende Lösung 06:18.640 --> 06:19.080 liefert. 06:20.540 --> 06:29.260 Man kann das eben auch so schreiben, als Funktion, dass der 06:29.260 --> 06:32.540 Algorithmus mir für jede Eingabe die entsprechende Lösung liefert. 06:33.780 --> 06:37.860 Auch wenn das hier nicht ganz eine mathematisch exakte Definition ist. 06:39.180 --> 06:40.060 Gut. 06:42.320 --> 06:45.960 Wann ist so eine Funktion überhaupt berechenbar? 06:47.500 --> 06:52.860 Na ja, genau dann, wenn es einen Algorithmus gibt, der mir für das 06:52.860 --> 07:01.820 entsprechende Problem, also für ein Wort W aus der Definitionsmenge im 07:01.820 --> 07:04.340 Prinzip, die entsprechende Lösung liefert. 07:06.140 --> 07:11.060 Beispiele für berechenbare Funktionen wären hier die Funktion f von n 07:11.060 --> 07:12.140 gleich n plus 1. 07:12.600 --> 07:14.320 Es ist trivial, dass ich das berechnen kann. 07:14.520 --> 07:17.100 Ich nehme diese Zahl, ich addiere 1 drauf und gebe das Ergebnis 07:17.100 --> 07:17.560 zurück. 07:17.860 --> 07:19.440 Das kann ich in endlicher Zeit machen. 07:21.200 --> 07:27.960 Auch die Funktion, die für jede Primzahl ein Ja ausgibt und für jede 07:27.960 --> 07:29.280 Nichtprimzahl ein Nein. 07:30.620 --> 07:36.880 Denn was ich machen muss, ist im Prinzip nur alle Zahlen, die kleiner 07:36.880 --> 07:41.240 sind als n, ausprobieren, ob ich n durch diese Zahl teilen kann, wenn 07:41.240 --> 07:42.020 ich keine finde. 07:44.800 --> 07:46.900 Ich weiß, dass ich irgendwann fertig bin. 07:47.120 --> 07:48.740 Der Algorithmus ist also endlich. 07:49.700 --> 07:53.540 Und wenn ich eine Zahl finde, durch die sich n teilen lässt, dann ist 07:53.540 --> 07:54.720 es natürlich keine Primzahl. 07:54.720 --> 07:55.960 Dann kann ich sofort abrechnen. 07:56.120 --> 08:00.020 Wenn ich keine finde, muss ich im schlechtesten Fall bis n halbe. 08:00.640 --> 08:01.380 Das reicht ja. 08:02.080 --> 08:02.840 Durchprobieren. 08:03.380 --> 08:06.180 Hier ist ein effizienter Algorithmus angehbar. 08:07.300 --> 08:10.660 Ein anderes Beispiel wäre größer gemeinsamer Teiler berechnen. 08:10.760 --> 08:15.880 Auch das ist natürlich trivial und durch einen Algorithmus berechnbar. 08:18.140 --> 08:18.900 Gut. 08:21.120 --> 08:22.980 Eine Sache hatte ich noch vergessen. 08:24.740 --> 08:33.580 Diese Definition von berechenbar sagt nichts darüber, was das Ergebnis 08:33.580 --> 08:38.500 dieser Funktion ist, wenn das w nicht Element m1 ist. 08:43.350 --> 08:45.890 Und es sagt auch nichts darüber aus, dass ich den entsprechenden 08:45.890 --> 08:48.210 Algorithmus angeben können muss. 08:49.130 --> 08:54.070 Ich muss nur nachweisen, dass es einen Algorithmus gibt, der diese 08:54.070 --> 08:54.890 Funktion berechnet. 08:55.970 --> 08:59.470 Wie der genau aussieht, ist für diese Definition zumindest nicht 08:59.470 --> 08:59.930 interessant. 09:02.190 --> 09:02.870 Okay. 09:04.030 --> 09:09.830 Die Frage wäre jetzt, ist jede Funktion, die ich angeben kann, von n 09:09.830 --> 09:11.230 nach n berechenbar? 09:13.090 --> 09:19.550 Und da beschäftigen wir uns erstmal mit der Abzählbarkeit, die ist 09:19.550 --> 09:20.830 folgendermaßen definiert. 09:20.830 --> 09:29.410 Eine Menge m heißt abzählbar, wenn m-Injektiv in n abbildbar ist. 09:30.530 --> 09:35.830 Injektiv, vielleicht nochmal zur Erinnerung, bedeutet, dass wenn a 09:35.830 --> 09:43.650 ungleich b ist, daraus folgt f von a ist ungleich f von b. 09:45.230 --> 09:52.630 Das heißt, unterschiedliche Elemente in m bekommen auch 09:52.630 --> 09:54.590 unterschiedliche Zahlen zugeordnet. 09:54.990 --> 10:00.110 Deswegen abzählbar, ich kann die Elemente in m durchnummerieren, jedes 10:00.110 --> 10:02.970 Element in m kann eine andere Nummer bekommen. 10:05.170 --> 10:08.750 Im Prinzip bedeutet das auch, oder ist das äquivalent damit zu sagen, 10:08.910 --> 10:14.650 dass es maximal so viele Elemente in m gibt, wie es natürliche Zahlen 10:14.650 --> 10:14.970 gibt. 10:17.330 --> 10:21.190 Es gibt natürlich unendlich viele natürliche Zahlen, das ist ja nicht 10:21.190 --> 10:26.830 begrenzt, aber es gibt eben abzählbar unendlich viele natürliche 10:26.830 --> 10:27.170 Zahlen. 10:27.170 --> 10:32.670 Und es kann auch überabzählbar viele, also Mengen mit überabzählbar 10:32.670 --> 10:33.910 vielen Elementen geben. 10:36.250 --> 10:40.130 Beispiele für abzählbare Mengen wären also jede endliche Menge, das 10:40.130 --> 10:40.590 ist klar. 10:41.430 --> 10:43.330 Jede endliche Menge kann ich durchzählen. 10:44.650 --> 10:50.350 Aber auch beispielsweise die Menge aller Wörter, also a hoch Stern, 10:50.650 --> 10:52.350 über einem endlichen Alphabet a. 10:54.730 --> 10:58.850 Weil ich auch die in eine bestimmte, wenn ich sie alle gegeben habe, 10:59.030 --> 11:03.850 beispielsweise in eine lexikografische Ordnung bringen kann und dann 11:03.850 --> 11:05.130 einfach durchnummerieren kann. 11:05.670 --> 11:09.890 Also ich könnte anfangen mit Lambda, wenn wir in das Alphabet 0 und 1 11:09.890 --> 11:17.710 wären, dann könnte ich anfangen mit Lambda 0 1 0 0 0 1 1 1, dann eben 11:17.710 --> 11:19.190 alle Wörter der Länge 3 usw. 11:19.350 --> 11:20.350 Ich kann sie abzählen. 11:23.930 --> 11:28.310 Es gibt auch überabzählbare Mengen, d.h. 11:28.610 --> 11:33.650 Mengen, die mehr Elemente enthalten als die Menge der natürlichen 11:33.650 --> 11:34.030 Zahlen. 11:35.210 --> 11:39.570 Ein Beispiel wäre die Menge der reellen Zahlen, und da reicht es sogar 11:39.570 --> 11:43.730 schon zu betrachten, die reelle Zahlen im Intervall von 0 bis 1. 11:44.950 --> 11:48.870 Beweisen kann man das durch Diagonalisierung, das ist ein Verfahren, 11:48.930 --> 11:50.170 das werde ich gleich noch vorstellen. 11:50.170 --> 11:53.150 Anhand eines anderen Problems, und das werden wir noch häufiger im 11:53.150 --> 11:54.610 Laufe der Vorlesung kennenlernen. 11:55.170 --> 11:58.130 Das ist so eines der wesentlichen Verfahren in dem Bereich. 12:01.310 --> 12:06.450 Okay, jetzt behaupte ich, die Menge aller Funktionen ist 12:06.450 --> 12:12.730 überabzählbar, während die Menge aller berechenbaren Funktionen 12:12.730 --> 12:13.950 abzählbar ist. 12:14.690 --> 12:19.370 Und die logische Folgerung aus diesen Behauptungen wäre, dass nicht 12:19.370 --> 12:22.150 jede Funktion berechenbar ist, weil es ganz offensichtlich mehr 12:22.150 --> 12:25.290 Funktionen gibt, als es berechenbare Funktionen gibt. 12:26.550 --> 12:28.130 Und das wollen wir jetzt beweisen. 12:36.130 --> 12:40.370 Nehmen wir an, die Menge aller Funktionen wäre abzählbar. 12:41.930 --> 12:46.690 Das bedeutet das nach der Definition, dass ich sie in eine Reihenfolge 12:46.690 --> 12:48.410 bringen kann und durchnummerieren kann. 12:48.930 --> 12:52.130 Also ich kann, wenn ich so eine Reihenfolge festgelegt habe, kann ich 12:52.130 --> 12:55.610 sagen, das ist meine Funktion 1, das ist meine Funktion 2, das ist 12:55.610 --> 12:56.830 Funktion 3 und so weiter. 13:00.110 --> 13:03.930 Und außerdem kann ich natürlich die möglichen Eingabeworte 13:03.930 --> 13:05.370 durchnummerieren. 13:06.750 --> 13:09.790 Wort 1, Wort 2, Wort 3, wie man das macht, das habe ich gerade 13:09.790 --> 13:12.230 vorgestellt, da kann ich einfach lexikografische Ordnung 13:12.230 --> 13:13.330 beispielsweise verwenden. 13:15.770 --> 13:19.590 Und das bedeutet natürlich, ich kann da auch eine Tabelle aufstellen 13:19.590 --> 13:25.650 im Prinzip, wo ich auf der einen Seite hier meine ganzen Funktionen 13:25.650 --> 13:26.310 aufschreibe. 13:27.750 --> 13:33.510 Und in jeder Spalte mir aufschreibe, was ist das Ergebnis der Funktion 13:33.510 --> 13:34.530 auf ein bestimmtes Wort. 13:35.370 --> 13:39.350 Also hier in diesem Feld steht dann das Ergebnis der Funktion 1 auf 13:39.350 --> 13:40.610 das Wort b1. 13:41.290 --> 13:46.390 Das Ergebnis der Funktion 2 auf das Wort b1, das Ergebnis der Funktion 13:46.390 --> 13:48.670 2 auf das Wort b2 und so weiter und so fort. 13:50.510 --> 13:53.370 Gut, jetzt schauen wir uns mal eine spezielle Funktion an. 13:56.690 --> 14:02.670 Die nennen wir g. Und wir wählen dieses g mit folgender Eigenschaft. 14:06.460 --> 14:17.560 Das g von wi soll genau u sein, falls die Funktion fi angewandt auf wi 14:17.560 --> 14:19.180 nicht u liefert. 14:20.640 --> 14:27.680 Und das Ergebnis soll v sein, falls fi von wi gleich u ist. 14:33.700 --> 14:44.220 Das heißt, unsere Funktion g ist zum Beispiel nicht gleich f1, weil 14:44.220 --> 14:54.400 angenommen f1 von b1 wäre u, das wäre also f1 von b1 wäre u, das wäre 14:54.400 --> 14:59.140 dieser Fall, dann ist g von b1 v nach der Definition. 15:00.920 --> 15:06.520 Und im anderen Fall, wenn f1 von b1 ungleich u wäre, dann wäre g von 15:06.520 --> 15:07.840 b1 gleich u. 15:09.180 --> 15:17.780 Das heißt, aufgrund dieses Eintrags ist g ungleich f1. 15:19.440 --> 15:22.740 Aufgrund dieses Eintrags nach entsprechend genau gleicher 15:22.740 --> 15:24.760 Argumentation ist g ungleich f2. 15:25.360 --> 15:28.060 Aufgrund dieses Eintrags ist g ungleich f3. 15:29.900 --> 15:31.840 Und das kann ich eben beliebig fortsetzen. 15:31.980 --> 15:33.600 Ich schaue mir immer die Diagonale an. 15:38.520 --> 15:44.580 Das heißt, ich kann hier im Prinzip schließen, dass g kommt in dieser 15:44.580 --> 15:46.500 Auflistung in meiner Tabelle nicht vor. 15:47.780 --> 15:53.840 Das ist aber ein Widerspruch, denn wir haben angenommen, dass die 15:53.840 --> 15:58.860 Menge f abzählbar ist, dass ich also alle möglichen Funktionen 15:58.860 --> 16:01.900 irgendwo auflisten kann. 16:02.400 --> 16:06.900 Und dass an irgendeiner Stelle deswegen auch für irgendein k das g 16:06.900 --> 16:08.090 gleich fk ist. 16:09.280 --> 16:14.500 Also irgendeines der fk muss ja für jede mögliche Funktion ein fk 16:14.500 --> 16:14.860 geben. 16:16.820 --> 16:20.520 Und das heißt, es muss auch ein fk geben, das genau identisch mit dem 16:20.520 --> 16:21.060 g ist. 16:23.680 --> 16:30.140 Und da haben wir eben einen Widerspruch, weil auf der einen Seite wir 16:30.140 --> 16:35.160 fordern, dass g von wk genau gleich fk von wk ist, auf der anderen 16:35.160 --> 16:38.660 Seite das nach Definition aber genau nicht sein darf, so wie die 16:38.660 --> 16:39.780 Funktion definiert ist. 16:39.780 --> 16:44.660 Das ist eben dieses Diagonalisierungsverfahren, das an mehreren 16:44.660 --> 16:49.200 Stellen im Laufe der Vorlesung noch vorkommen wird und mit dem ich 16:49.200 --> 16:52.080 beispielsweise auch zeigen kann, dass die Menge der reellen Zahlen 16:52.080 --> 16:53.300 überabzählbar ist. 16:56.240 --> 17:00.440 Okay, wir haben also gezeigt, dass es überabzählbar viele Funktionen 17:00.440 --> 17:00.760 gibt. 17:01.720 --> 17:04.480 Jetzt müssen wir noch begründen, dass f berechenbar ist. 17:05.500 --> 17:09.800 Das ist viel einfacher, da muss ich einfach nur sagen, wenn es 17:09.800 --> 17:11.900 berechenbar ist, muss es einen Algorithmus geben. 17:12.540 --> 17:16.200 Algorithmus bedeutet, es gibt einen Text endlicher Länge zur 17:16.200 --> 17:17.640 Beschreibung des Algorithmus. 17:20.100 --> 17:29.380 Die Menge aller Worte endlicher Länge ist aber abzählbar und damit ist 17:29.380 --> 17:31.840 auch die Menge aller berechenbaren Funktionen abzählbar. 17:32.980 --> 17:38.060 Wir haben also nachgewiesen, es gibt definitiv Funktionen, die wir 17:38.060 --> 17:39.040 nicht berechnen können. 17:40.720 --> 17:45.200 Egal wie toll unser Algorithmus und egal wie toll unsere Maschine, auf 17:45.200 --> 17:46.300 der wir das berechnen wollen. 17:49.360 --> 17:51.340 Gut, noch ein paar andere Definitionen. 17:53.040 --> 17:57.740 Eine Menge heißt entscheidbar, relativ zu einer anderen Menge. 17:58.740 --> 18:10.440 Wenn es einen Algorithmus gibt, der jedem Element aus M2 wahr oder 18:10.440 --> 18:11.600 falsch zuordnet. 18:11.820 --> 18:20.740 Und zwar genau dann wahr zuordnen, wenn diese Eingabe W aus M1 ist. 18:21.460 --> 18:26.160 Und die Ausgabe soll falsch sein, wenn das W nicht aus M1 ist. 18:32.540 --> 18:42.020 Und eine Menge heißt absolut entscheidbar, wenn das M relativ zu E 18:42.020 --> 18:43.280 -Stern entscheidbar ist. 18:44.360 --> 18:50.700 Also wenn ich für jedes Wort Element E-Stern angeben kann, entscheiden 18:50.700 --> 18:54.580 kann, gehört dieses Wort zu M oder gehört es nicht zu M. 18:58.690 --> 19:01.570 Andere Bezeichnung dafür ist auch rekursiv. 19:05.720 --> 19:07.520 Okay, da haben wir noch eine Definition. 19:09.760 --> 19:17.240 Die Funktion, die im Prinzip genau das macht, die einem Wort wahr 19:17.240 --> 19:18.720 zuordnet bzw. 19:18.800 --> 19:24.940 falsch, je nachdem ob es in M1 ist oder in M2 ohne M1, nennt man auch 19:24.940 --> 19:28.000 die charakteristische Funktion von M1 bezüglich M2. 19:29.420 --> 19:34.780 Und ganz offensichtlich, M1 ist genau dann entscheidbar relativ zu M2, 19:35.260 --> 19:38.860 wenn die charakteristische Funktion M1 M2 berechenbar ist. 19:43.150 --> 19:43.350 Gut. 19:45.870 --> 19:49.010 Ein paar Beispiele für entscheidbare Mengen. 19:50.350 --> 19:56.270 Die Menge aller Primzahlen ist entscheidbar relativ zur Gesamtmenge 19:56.270 --> 19:57.390 der natürlichen Zahlen. 20:00.370 --> 20:03.790 Weil ich eben einen Algorithmus angeben kann, der mir in endlicher 20:03.790 --> 20:07.210 Zeit sagt, ob das eine Primzahl ist oder ob es keine Primzahl ist. 20:08.330 --> 20:09.830 Haben wir vorhin schon diskutiert. 20:12.010 --> 20:17.270 Jede endliche Menge ist entscheidbar, natürlich, weil ich ja nur die 20:17.270 --> 20:18.770 Menge komplett durchsuchen muss. 20:19.450 --> 20:23.610 Und am Ende, also entweder im Verlauf feststelle, das Element ist in 20:23.610 --> 20:26.830 dieser Menge drin, oder eben am Ende feststelle, ich bin am Ende der 20:26.830 --> 20:30.610 Menge, habe alle durchsucht und habe es nicht gefunden, also ist es 20:30.610 --> 20:31.090 nicht drin. 20:33.170 --> 20:42.390 Ein anderes entscheidbares Problem wäre, ob die Sprache einer 20:42.390 --> 20:45.990 kontextfreien Grammatik endlich ist oder nicht endlich ist, also 20:45.990 --> 20:46.630 unendlich. 20:50.630 --> 20:53.330 Das sind also Beispiele für entscheidbare Mengen. 20:53.330 --> 20:57.830 Was ist eine aufzählbare Menge? 21:05.610 --> 21:12.230 Eine Menge heißt aufzählbar oder auch rekursiv aufzählbar, wenn es 21:12.230 --> 21:16.570 eine surjektive berechenbare Funktion von N nach M gibt. 21:17.570 --> 21:25.810 Surjektiv heißt, dass es für alle Elemente im Bildbereich auch ein 21:25.810 --> 21:33.330 Element im Definitionsbereich gibt, dass das Element im Bildbereich 21:33.330 --> 21:34.190 abgebildet wird. 21:34.190 --> 21:43.450 Das heißt, für jedes M gibt es eine natürliche Zahl, sodass f von 21:43.450 --> 21:46.690 dieser natürlichen Zahl gleich M ist. 21:48.610 --> 21:53.990 Und dann kann ich f, M im Prinzip aufzählen. 21:56.710 --> 22:04.190 Ich kann M auch schreiben als f von 0, f von 1, f von 2, f von 3 usw. 22:05.590 --> 22:10.250 Wenn ich alle natürlichen Zahlen durchmache, dann weiß ich, ich habe 22:10.250 --> 22:12.830 auch alle Elemente von M erwischt. 22:15.030 --> 22:19.030 Wobei bei der Definition nicht ausgeschlossen ist, dass jetzt f von 0 22:19.030 --> 22:22.130 und f von 1 auch die gleichen Elemente von M sein können. 22:25.880 --> 22:32.720 Das Entscheidende bei der Aufzählbarkeit ist hier die Berechenbarkeit. 22:33.620 --> 22:36.280 Es muss also eine berechenbare Funktion geben. 22:43.040 --> 22:50.140 Man kann zeigen, dass wenn M aufzählbar ist, dann ist M auch 22:50.140 --> 22:51.460 abzählbar. 22:55.940 --> 23:03.320 Der Ansatz für eine Begründung wäre, wenn M aufzählbar ist, dann gibt 23:03.320 --> 23:06.360 es auch eine berechenbare Funktion für M. 23:06.360 --> 23:12.020 Und wir haben vorhin gezeigt, es gibt nur abzählbar viele berechenbare 23:12.020 --> 23:12.400 Funktionen. 23:13.880 --> 23:16.300 Also ist M auch abzählbar. 23:19.630 --> 23:22.550 Die Umkehrung gilt im Allgemeinen nicht. 23:23.450 --> 23:29.850 Man kann zeigen, dass es überabzählbar viele abzählbare Mengen über E 23:29.850 --> 23:30.410 -Sternen gibt. 23:30.650 --> 23:32.470 Und deswegen gilt die Umkehrung nicht. 23:33.690 --> 23:39.110 Das liegt einfach daran an der Berechenbarkeit. 23:40.450 --> 23:44.210 Also bei der Abzählbarkeit war es mir im Prinzip egal, was für eine 23:44.210 --> 23:45.030 Funktion das ist. 23:45.270 --> 23:48.230 Und jetzt sage ich, es muss berechenbar sein. 23:53.680 --> 23:58.840 Man kann außerdem sagen, dass M entscheidbar ist, genau dann, wenn M 23:58.840 --> 24:03.160 und das Komplement von M, also alle Worte, die nicht in M drin sind, 24:04.080 --> 24:04.980 aufzählbar sind. 24:06.800 --> 24:08.060 Wieso ist das so? 24:09.820 --> 24:21.500 Wenn ich M und das Komplement aufzählen kann, dann kann ich das erste 24:21.500 --> 24:26.540 Element aus M mehr angucken und dann das erste Element aus dem 24:26.540 --> 24:30.640 Komplement von M und dann das zweite Element von M und das zweite 24:30.640 --> 24:34.180 Element aus dem Komplement von M und so weiter immer abwechselnd mir 24:34.180 --> 24:35.720 diese ganzen Elemente anschauen. 24:36.860 --> 24:44.280 Und da ich ja M und das Komplement aufzähle, ist damit klar, dass ich 24:44.280 --> 24:48.220 an irgendeiner Stelle auf mein gesuchtes Wort kommen werde. 24:48.540 --> 24:53.560 Und dann muss ich nur entscheiden, war das jetzt ein Element von M 24:54.080 --> 24:59.720 oder war das ein Element aus dem Komplement von M und kann damit eben 24:59.720 --> 25:02.800 entscheiden, ob es zu M gehört oder nicht. 25:10.280 --> 25:12.940 Gut, das heißt, die Zusammenhänge sind so, wir haben die 25:12.940 --> 25:21.540 entscheidbaren Mengen, wir haben die Übermenge der aufzählbaren Mengen 25:21.920 --> 25:24.340 und dann noch mehr abzählbaren Mengen. 25:25.540 --> 25:30.780 Hier nochmal andere Begriffsbildungen, die Sie häufig in der Literatur 25:30.780 --> 25:39.000 finden, statt entscheidbar eben rekursiv und statt aufzählbar rekursiv 25:39.000 --> 25:41.720 aufzählbar oder semi-entscheidbar. 25:47.280 --> 25:56.180 Gut, bisher haben wir mit einem relativ intuitiven, abstrakten Begriff 25:56.180 --> 25:57.740 von Berechenbarkeit hantiert. 25:58.720 --> 26:02.720 Und auch von Algorithmus. 26:03.420 --> 26:06.760 Und die Frage ist jetzt, können wir das irgendwie genauer 26:06.760 --> 26:08.840 spezifizieren, wer berechnet denn da? 26:09.080 --> 26:12.880 Berechne ich das auf einem Windows-Computer oder auf einem Macintosh 26:12.880 --> 26:18.660 oder auf einem Unix-Rechner oder auf eine Turing-Maschine oder auf... 26:18.660 --> 26:20.800 was weiß ich, was mir da berechnet. 26:21.520 --> 26:24.060 Wir schauen uns jetzt mal speziell die Turing-Maschinen an. 26:25.140 --> 26:27.500 Mit denen haben wir uns ja schon intensiv auseinandergesetzt. 26:28.800 --> 26:32.060 Fragestellung also, welche Funktionen lassen sich mit Turing-Maschinen 26:32.060 --> 26:32.680 berechnen? 26:36.460 --> 26:41.420 Dazu müssen wir die Idee der Turing-Maschine ein bisschen umwandeln. 26:42.380 --> 26:46.140 Es geht nicht mehr nur darum, ob wir ein Wort akzeptieren oder nicht 26:46.140 --> 26:50.220 akzeptieren, sondern wir berechnen im Prinzip den Funktionswert von W. 26:51.240 --> 26:55.240 Das heißt, unsere Initialkonfiguration ist so, dass das W auf dem Band 26:55.240 --> 26:55.600 steht. 26:57.180 --> 27:01.960 Und am Ende sind wir in irgendeinem Endzustand und auf dem Band steht 27:01.960 --> 27:04.020 noch das Ergebnis von der Berechnung. 27:09.000 --> 27:09.740 Gut. 27:11.440 --> 27:17.900 Eine Turing-Maschine berechnet also eine Funktion f, wenn für alle w, 27:18.000 --> 27:29.120 v Elementen e Sternenfolgendes gilt, wenn das w Element m1 ist und das 27:29.120 --> 27:36.440 v gleich f von w, dann gibt es einen Konfigurationsübergang von der 27:36.440 --> 27:39.000 Initialkonfiguration, die wir uns gerade angeschaut haben. 27:39.140 --> 27:46.440 Das heißt, links vom Schreiblesekopf steht nichts, wir sind im Zustand 27:46.440 --> 27:53.100 S0 und rechts vom Schreiblesekopf steht genau das Eingabewort nach u, 27:53.100 --> 27:59.960 s, x, wobei u, x zusammen eben genau das Ergebnis der Berechnung 27:59.960 --> 28:00.280 geben. 28:01.200 --> 28:05.300 Also es ist mir im Prinzip egal, wo an welcher Stelle der 28:05.300 --> 28:09.420 Schreiblesekopf steht, aber die Bandinschrift zusammengenommen soll 28:09.420 --> 28:12.040 eben gerade das Ergebnis der Berechnung sein. 28:13.040 --> 28:18.100 Und u, s, x ist Endkonfiguration, also S ist ein Endzustand und es 28:18.100 --> 28:21.300 gibt keine weitere Regel mehr, die ich anwenden kann. 28:23.400 --> 28:33.580 Auch hier ist es so, dass für w Nicht-Element aus m1 das Verhalten der 28:33.580 --> 28:35.100 Maschine unbestimmt ist. 28:35.100 --> 28:38.640 Und wir haben schon diskutiert in der letzten Stunde, dass Turing 28:38.640 --> 28:42.440 -Maschinen unter Umständen nicht anhalten. 28:43.360 --> 28:45.620 Die können ewig laufen, immer vor und zurück. 28:50.740 --> 28:54.740 Und das kann im Prinzip genau passieren, wenn wir eben ein Wort 28:54.740 --> 28:57.040 eingeben, das nicht in m1 ist. 28:59.690 --> 29:04.370 Gut, und die Funktion heißt eben Turing-Berechenbar, wenn es eine 29:04.370 --> 29:06.470 Turing -Maschine gibt, die die Funktion berechnet. 29:08.510 --> 29:10.510 Okay, ganz einfaches Beispiel. 29:12.490 --> 29:18.730 Wir wollen das Einer-Komplement eines Wortes w Element e Sternen, e 29:18.730 --> 29:20.410 gleich 0,1 berechnen. 29:21.490 --> 29:24.830 Das heißt, jede 1 soll in eine 0 und jede 0 in eine 1 umgewandelt 29:24.830 --> 29:25.110 werden. 29:25.750 --> 29:26.970 Das ist trivial. 29:34.780 --> 29:38.060 Hier ist nochmal formal spezifiziert, wie ich das jetzt rekursiv 29:38.060 --> 29:38.940 herleiten könnte. 29:42.220 --> 29:46.940 Wenn w gleich Lambda ist, dann ist natürlich das Komplement auch 29:46.940 --> 29:47.620 gerade Lambda. 29:48.240 --> 29:51.900 Und wenn w mit 0 anfängt und danach irgendeinen w Strich hat, dann 29:51.900 --> 29:58.160 wandle ich das um in eine 1 und danach das Ergebnis der Funktion 29:58.160 --> 29:59.440 angewendet auf w Strich. 29:59.660 --> 30:04.040 Also ich kann das Buchstabe für Buchstabe natürlich abarbeiten. 30:05.360 --> 30:08.440 Und hier ist eine Turing-Maschine definiert, die genau das leistet. 30:09.940 --> 30:11.060 Ganz simpel. 30:11.840 --> 30:13.980 Wir brauchen im Prinzip nur den Zustand s0. 30:15.540 --> 30:17.480 Und in dem machen wir die gesamte Arbeit. 30:20.620 --> 30:24.240 Wenn wir eine 0 einlesen, dann schreiben wir eine 1 und bewegen uns 30:24.240 --> 30:26.100 den Schreiblesekopf von 1 nach rechts. 30:26.220 --> 30:29.740 Wenn wir eine 1 einlesen, dann schreiben wir eine 0 und bewegen den 30:29.740 --> 30:31.320 Schreiblesekopf von 1 nach rechts. 30:31.880 --> 30:34.300 Und wenn wir irgendwann am Ende angelangt sind, dann gehen wir in den 30:34.300 --> 30:38.880 Endzustand s1 und können machen, was wir wollen. 30:39.200 --> 30:41.000 Stehen bleiben oder nach links wieder gehen. 30:43.480 --> 30:44.460 Gut, das ist trivial. 30:47.480 --> 30:50.580 Entsprechende Berechenbarkeit können wir natürlich auch die Turing 30:50.580 --> 30:53.740 -Aufzählbarkeit und die Turing-Entscheidbarkeit definieren. 30:55.580 --> 31:00.220 In diesem Fall eben eine Maschine heißt Turing-Aufzählbar, wenn es 31:00.220 --> 31:06.240 eine sujektive, jetzt Turing-Berechenbare Funktion von N0 nach M gibt. 31:08.800 --> 31:13.100 Und M heißt Turing-Entscheidbar, wenn die charakteristische Funktion 31:13.100 --> 31:14.720 Turing -Berechenbar ist. 31:24.650 --> 31:29.950 Man kann zeigen, dass eine Menge M genau dann Turing-Aufzählbar ist, 31:30.450 --> 31:35.630 wenn es eine Turing-Maschine gibt, die genau die Eingaben B-Element M 31:35.630 --> 31:36.370 akzeptiert. 31:37.790 --> 31:43.110 Unter Umständen aber für B-Element, nicht Element M, nie stoppt. 31:45.090 --> 31:49.430 Deswegen heißt diese Turing-Aufzählbaren Mengen auch semi 31:49.430 --> 31:50.190 -entscheidbar. 31:50.650 --> 31:57.030 Weil ich entscheiden kann, wenn ein Element dazugehört, aber nicht 31:57.030 --> 31:59.430 entscheiden kann, wenn ein Element nicht dazugehört. 32:00.270 --> 32:04.090 Denn wenn ein Element nicht dazugehört, dann kann es eben sein, dass 32:04.090 --> 32:06.570 die Turing-Maschine überhaupt nie stoppt. 32:09.150 --> 32:13.010 Und ich kann nie abbrechen, weil ich nicht weiß, 32:16.250 --> 32:22.390 wenn die Maschine noch nicht abgebrochen hat, ob das daran liegt, dass 32:22.390 --> 32:24.310 sie einfach nicht mit der Berechnung fertig ist. 32:25.070 --> 32:27.530 Sie könnte ja beim nächsten Schritt jetzt abbrechen. 32:28.650 --> 32:33.370 Oder ob das daran liegt, dass mein Eingabewort nicht in M liegt und 32:33.370 --> 32:37.110 sie deswegen in einen unendlichen Loop geraten ist. 32:38.170 --> 32:39.600 Nachdem sie eben nie wieder rauskommt. 32:42.230 --> 32:43.480 Deswegen eben semi-entscheidbar. 32:52.090 --> 32:52.730 Okay. 32:57.170 --> 33:03.930 Letztendlich führt das heute darauf hin, dass wir versuchen zu 33:03.930 --> 33:08.830 begründen, dass Turing-Maschinen genauso viel können wie der Rechner, 33:08.930 --> 33:10.090 den sie zu Hause stehen haben. 33:11.930 --> 33:15.310 Und ein wesentlicher Unterschied oder ein wesentlicher Aspekt, der 33:15.310 --> 33:18.250 noch die Turing-Maschine unterscheidet von dem Rechner, den sie zu 33:18.250 --> 33:21.450 Hause haben, ist, dass sie ihren Rechner zu Hause programmieren 33:21.450 --> 33:21.790 können. 33:22.630 --> 33:26.390 Bei Turing-Maschinen sind wir bisher davon ausgegangen, die haben 33:26.390 --> 33:29.890 irgendwie eine Übergangsfunktion und die machen eine bestimmte Sache, 33:30.050 --> 33:31.750 aber sie machen eigentlich nur eine Sache. 33:33.430 --> 33:40.150 Und wir wollen uns jetzt anschauen, wie könnte man eventuell Turing 33:40.150 --> 33:43.230 -Maschinen programmieren, wie könnte das aussehen, wenn eine Turing 33:43.230 --> 33:46.750 -Maschine so tut, als wäre sie eine andere Turing-Maschine und 33:46.750 --> 33:47.350 ähnliche Dinge. 33:53.410 --> 34:00.990 Frage also, gibt es eine universelle Turing-Maschine, der ich eine 34:00.990 --> 34:08.810 Turing -Maschine eingebe und zusätzlich ein Wort, Element E-Stern, und 34:08.810 --> 34:13.670 die dann das Verhalten der Turing-Maschine, die ich eingegeben habe, 34:14.490 --> 34:15.110 simuliere. 34:15.750 --> 34:18.470 Also das Verhalten von T bei Eingabe von W. 34:21.930 --> 34:23.250 Okay, hier ist die Idee. 34:25.630 --> 34:29.810 Wir schreiben auf das Band dieser universellen Turing-Maschine zum 34:29.810 --> 34:34.710 einen eine Beschreibung der Turing-Maschine, die wir gerne simuliert 34:34.710 --> 34:37.170 haben wollen, also das ist im Prinzip unser Programm. 34:40.330 --> 34:43.410 Das muss man in einer geeigneten Weise kodieren, das ist klar. 34:43.970 --> 34:48.030 Wir nehmen jetzt mal einfach an, das können wir, wir schreiben da also 34:48.030 --> 34:54.990 ein Wort CT über einem geeigneten Alphabet drauf, das das Verhalten 34:54.990 --> 34:56.770 von einer Turing-Maschine T beschreibt. 35:03.170 --> 35:06.430 Und wir legen außerdem auf diesem Band noch ab eine 35:06.430 --> 35:13.070 Initialkonfiguration von T, die natürlich auch das entsprechende Wort 35:13.070 --> 35:13.340 beinhaltet. 35:14.320 --> 35:23.440 Und jetzt ist die Idee, dass diese universelle Turing-Maschine auf 35:23.440 --> 35:28.240 ihrem Arbeitsband Beschreibungen der Folgekonfigurationen von T 35:28.240 --> 35:31.780 entsprechend der definierten Arbeitsweise generiert. 35:32.560 --> 35:36.040 Also die guckt hier, okay, das ist meine Initialkonfiguration. 35:37.940 --> 35:41.360 Was kann ich denn auf dieser Initialkonfiguration machen? 35:41.540 --> 35:45.360 Das heißt, sie wandert dann rüber in diesen Bereich, guckt, wie dieses 35:45.360 --> 35:50.240 T, das wir mitgegeben haben, eigentlich funktioniert, was das T jetzt 35:50.240 --> 35:54.960 machen würde und macht dann die Arbeit von dem T auf der 35:54.960 --> 35:55.980 Initialkonfiguration. 35:55.980 --> 35:59.240 Dann sind wir in der neuen Konfiguration, dann kann sie wieder gucken, 35:59.340 --> 36:03.520 was würde in dieser neuen Konfiguration diese Maschine T machen und so 36:03.520 --> 36:03.800 weiter. 36:06.680 --> 36:10.360 Und sie simuliert damit quasi die Funktionsweise von T. 36:14.600 --> 36:19.720 Und die Idee ist, wenn U die Beschreibung einer Endkonfiguration von T 36:19.720 --> 36:21.840 erzeugt hat, 36:33.450 --> 36:37.930 dann geht auch U in die Endkonfiguration und wir sind fertig. 36:40.640 --> 36:43.540 Okay, einige Annahmen zur Vereinfachung. 36:47.820 --> 36:50.480 Ich hatte schon gesagt, wir müssen das natürlich irgendwie geeignet 36:50.480 --> 36:50.880 codieren. 36:51.020 --> 36:53.740 Wir müssen alle möglichen Turing-Maschinen dann in einer bestimmten 36:53.740 --> 36:57.440 Art und Weise aufschreiben können, sodass unsere universelle Turing 36:57.440 --> 36:59.000 -Maschine verstehen kann. 37:00.260 --> 37:03.240 Und das kann man beispielsweise machen, indem wir ein festes 37:03.240 --> 37:04.480 Bandalphabet annehmen. 37:04.880 --> 37:07.860 Das gibt in unserem Bandalphabet nur 0, 1 und Stern. 37:09.720 --> 37:16.180 Und es gibt eine feste potenzielle Zustandsmenge, die zwar unendlich 37:16.180 --> 37:17.360 ist, aber abzählbar. 37:19.140 --> 37:22.880 Und jede Zustandsmenge von einer konkreten Turing-Maschine ist 37:22.880 --> 37:23.420 endlich. 37:24.240 --> 37:26.080 Das war auch Teil der Definition. 37:28.120 --> 37:31.140 Außerdem nehmen wir an, dass der Anfangszustand einheitlich ist für 37:31.140 --> 37:32.040 alle Turing-Maschinen. 37:32.160 --> 37:33.520 Auch das ist keine Einschränkung. 37:36.160 --> 37:41.320 Und das ist eine einheitliche, abzählbare Menge potenzieller 37:41.320 --> 37:41.610 Endzuständigen. 37:42.560 --> 37:45.420 All das sind Vereinfachungen, aber keine Einschränkungen. 37:45.560 --> 37:48.260 Wir können dann nach wie vor alle möglichen Turing-Maschinen irgendwie 37:48.260 --> 37:49.340 damit beschreiben. 37:52.040 --> 37:55.460 Gut, dann können wir uns jetzt unter diesen Annahmen eine Codierung 37:55.460 --> 37:56.020 überlegen. 38:04.080 --> 38:07.900 Für diese Übergangsfunktion brauchen wir ja im Prinzip eine Codierung. 38:08.800 --> 38:13.600 Und diese Übergangsfunktion könnte heißen, wenn wir im Zustand SJ sind 38:13.600 --> 38:22.040 und ein BI einlesen, dann gehen wir über in den Zustand SK, schreiben 38:22.040 --> 38:26.420 ein BR auf das Band und bewegen unseren Schreiblesekopf nach links 38:26.420 --> 38:27.920 oder rechts oder überhaupt nicht. 38:27.920 --> 38:32.740 Das sind ja die Regeln, die diese Turing-Maschine charakterisieren. 38:34.520 --> 38:38.940 Und das können wir jetzt, auch wenn es ein bisschen abstrus erscheint, 38:39.580 --> 38:42.100 beschreiben durch ein Wort der folgenden Form. 38:46.560 --> 38:55.940 Wir benutzen die Null als Trennzeichen und jeder dieser Indizes, also 38:55.940 --> 39:01.460 das J, das I, das K, das R und das M, wird dargestellt durch die 39:01.460 --> 39:03.040 entsprechende Anzahl von Einsen. 39:04.320 --> 39:08.940 Wir haben hier eine Null, dann haben wir J Einsen, dann haben wir eine 39:08.940 --> 39:12.640 Null als Trennzeichen, dann haben wir I Einsen, dann haben wir eine 39:12.640 --> 39:14.780 Null als Trennzeichen, K Einsen und so weiter. 39:15.420 --> 39:18.780 Und die Turing-Maschine kann das dann genau interpretieren, die kann 39:18.780 --> 39:23.000 das lesen, kann die Einsen zählen und kann dann im Prinzip sagen, 39:23.160 --> 39:28.200 okay, ich weiß jetzt, wenn ich im Zustand SJ bin und das Eingabesymbol 39:28.200 --> 39:33.140 BI lese, dann gehe ich über in den neuen Zustand SK, schreibe auf das 39:33.140 --> 39:39.720 Band BR und bewege meinen Kopf entsprechend dem, was hier unter N 39:39.720 --> 39:40.460 kodiert ist. 39:43.400 --> 39:48.040 Das wird natürlich ziemlich lang, das ist klar, aber prinzipiell ist 39:48.040 --> 39:48.840 es eben machbar. 39:50.960 --> 40:00.180 Und mit der Konfiguration können wir das ganz analog machen, das 40:00.180 --> 40:03.920 heißt, wir müssen irgendwie die aktuelle Bandinschrift ablegen und den 40:03.920 --> 40:07.300 aktuellen Zustand können wir durch Nullen trennen. 40:07.300 --> 40:10.880 Und die Position des Schreib-Lese-Kopfes könnte man beispielsweise 40:10.880 --> 40:14.080 durch drei aufeinanderfolgende Nullen vor dem zu lesenden Zeichen 40:14.080 --> 40:18.780 beschreiben und dann hätten wir eine komplette Beschreibung von dem, 40:18.900 --> 40:20.200 was ich gerade vorgestellt hatte. 40:21.940 --> 40:24.920 Hier, wir haben eine Arbeitsweise beschrieben, wir haben die 40:24.920 --> 40:28.780 Initialkonfiguration beschrieben, alles mit Nullen und Einsen und wir 40:28.780 --> 40:34.640 können jetzt mit U das T simulieren. 40:42.170 --> 40:48.170 Also sei CTm von T die Kodierung der Überführungsfunktion der Turing 40:48.170 --> 40:52.170 -Maschine, also von der Turing-Maschine T, die wir simulieren wollen, 40:53.190 --> 40:59.290 und CTn von K die Kodierung der Konfiguration einer Turing-Maschine. 41:01.050 --> 41:06.050 Und diese universelle Turing-Maschine simuliert jetzt unsere spezielle 41:06.050 --> 41:11.710 Turing -Maschine T, wenn folgendes gilt, das U befindet sich am Anfang 41:11.710 --> 41:16.630 in der Anfangskonfiguration, das heißt, mein Schreib-Lese-Kopf steht 41:16.630 --> 41:23.330 ganz links, links steht Lambda, ich bin im Zustand S0 und rechts steht 41:23.330 --> 41:27.570 jetzt die Kodierung der Turing-Maschine als Eingabe und die Kodierung 41:27.570 --> 41:28.790 der Anfangskonfiguration. 41:31.760 --> 41:36.580 Und wenn jetzt T die Konfigurationen K0, K1 und so weiter bis KN 41:36.580 --> 41:43.460 durchläuft, dann muss unser U die Konfiguration folgendermaßen 41:43.460 --> 41:48.240 durchlaufen, und zwar von dieser Anfangskonfiguration muss es einen 41:48.240 --> 41:56.880 Übergang geben nach, im Prinzip, wie der Schreib-Lese-Kopf könnte ganz 41:56.880 --> 41:59.660 rechts stehen, wir gehen hier in einen Zustand S1'. 42:01.580 --> 42:08.300 Also irgendwie in einem beliebigen Zustand, sodass rechts dann nach 42:08.300 --> 42:11.900 wie vor die Turing-Maschine steht, die Beschreibung der Turing 42:11.900 --> 42:19.900 -Maschine und eben die kodierte Konfiguration von K1 und so weiter bis 42:19.900 --> 42:22.260 eben die kodierte Konfiguration von KN. 42:23.080 --> 42:31.580 Und U hält genau dann in einer Endkonfiguration oder nicht, wenn auch 42:31.580 --> 42:32.260 das T hält. 42:32.640 --> 42:36.120 Und dann haben wir eben eine universelle Turing-Maschine, die unsere 42:36.120 --> 42:38.140 spezielle Turing-Maschine simulieren kann. 42:46.950 --> 42:56.770 Okay, das heißt, durch diese Kodierung haben wir gezeigt, jede Turing 42:56.770 --> 43:02.370 -Maschine kann aufgrund der angegebenen Kodierung in eine Zeichenkette 43:02.370 --> 43:04.790 über dem Alphabet 01 spezifiziert werden. 43:06.070 --> 43:10.850 Damit können wir aber auch alle Turing-Maschinen in eine feste 43:10.850 --> 43:15.650 Reihenfolge bringen, beispielsweise indem wir eben die genauso wie 43:15.650 --> 43:19.770 gerade besprochen über diese Kodierung beschreiben und dann einfach 43:19.770 --> 43:21.670 diese Kodierung lexikografisch ordnen. 43:25.850 --> 43:26.770 Okay, 43:29.920 --> 43:34.280 wir haben gezeigt, es gibt eine universelle Turing-Maschine, die das 43:34.280 --> 43:39.240 Akzeptanzverhalten jeder anderen Turing-Maschine simulieren kann. 43:40.420 --> 43:47.040 Und wir werden jetzt zeigen, dass es keine Turing-Maschine gibt, die 43:47.040 --> 43:52.260 die nicht akzeptierten Worte jeder beliebigen Turing-Maschine 43:52.260 --> 43:53.020 akzeptiert. 43:57.460 --> 44:02.160 Also, es gibt keine Umkehrung hier. 44:03.680 --> 44:04.580 Das ist dieser Satz. 44:04.620 --> 44:08.260 Es gibt keine Turing-Maschine, die diese Sprache, ich nenne sie mal 44:08.260 --> 44:14.020 hier LNA, akzeptieren kann, in der alle Worte drin sind. 44:14.020 --> 44:24.080 Alle Worte WI, wobei WI nicht definiert wird, nicht akzeptiert wird 44:24.080 --> 44:26.060 von dieser Turing-Maschine TI. 44:27.120 --> 44:32.440 Wobei ich jetzt hier davon ausgehe, dass ich eben die entsprechend 44:32.440 --> 44:35.780 durchnummeriert habe, in irgendeine bestimmte Ordnung gebracht habe. 44:37.620 --> 44:43.180 Der Beweis ist analog zur Existenz einer nicht berechenbaren Funktion, 44:43.260 --> 44:44.600 nämlich durch Diagonalisierung. 44:46.360 --> 44:50.600 Das heißt, wir können annehmen, es gibt eine Turing-Maschine, die 44:50.600 --> 44:52.660 diese Sprache akzeptiert. 44:54.980 --> 44:58.840 Dann gibt es aufgrund der Abzählbarkeit, der Menge der Turing 44:58.840 --> 45:05.300 -Maschinen, auch ein J, sodass ich sagen kann, okay, diese Turing 45:05.300 --> 45:09.160 -Maschine, von der ich annehme, dass er akzeptiert, das ist genau die 45:09.160 --> 45:10.220 Turing -Maschine TJ. 45:11.360 --> 45:16.160 In meiner Durchnummerierung hatte ich genau den Nummer J bekommen. 45:19.070 --> 45:29.090 Das heißt, das WJ, wenn das WJ zur Sprache dieser Turing-Maschine 45:29.090 --> 45:49.920 gehört, wenn das WJ zu dieser Sprache gehört, die ich untersuchen 45:49.920 --> 45:53.600 will, dann gehört das WJ eben auch zur Sprache einer Turing-Maschine, 45:54.220 --> 45:56.340 nämlich genau der Turing-Maschine TJ. 45:57.400 --> 46:04.020 Aber nach Definition von dieser Sprache kann das genau wieder nicht 46:04.020 --> 46:04.680 existieren. 46:04.780 --> 46:12.900 Das WJ ist nämlich eben nach dieser Definition nicht Element einer der 46:12.900 --> 46:14.300 entsprechenden Turing-Maschinen TJ. 46:15.920 --> 46:21.320 Also genau dieselbe Idee, wir gucken uns die Diagonale an und stellen 46:21.320 --> 46:25.580 fest, es kann keine Turing-Maschine geben, die die entsprechende 46:25.580 --> 46:27.000 Sprache akzeptiert. 46:30.700 --> 46:41.620 Gut, das heißt, weil die Typ-0-Sprachen genau die Sprachen sind, die 46:41.620 --> 46:45.520 durch Turing-Maschinen erkannt werden können, gilt auch die Forderung, 46:45.700 --> 46:51.880 dass es Sprachen gibt, die nicht zu den Typ-0-Sprachen gehören. 46:55.900 --> 47:01.420 Wir können jetzt nicht genau diese Sprache beschreiben, aber wir haben 47:01.420 --> 47:06.020 einen Beweis, der zumindest die Existenz dieser Sprache nachweist. 47:13.000 --> 47:21.720 Man kann auch zeigen, dass sich Turing-Maschinen systematisch 47:21.720 --> 47:24.740 programmieren lassen oder erzeugen lassen. 47:24.740 --> 47:29.160 Wenn ich also bestimmte Aufgaben habe, dann kann ich Basismaschinen 47:29.160 --> 47:35.740 definieren für ganz elementare Funktionen wie Addition, Multiplikation 47:35.740 --> 47:36.380 oder Vergleich. 47:36.640 --> 47:38.300 Also Turing-Maschinen, die das erledigen. 47:39.040 --> 47:42.820 Und ich kann dann Turing-Maschinen verwenden zur Verknüpfung von 47:42.820 --> 47:43.600 Turing -Maschinen. 47:45.060 --> 47:48.200 Auch aufgrund dieser Eigenschaft, die wir gerade gezeigt haben, dass 47:48.200 --> 47:51.240 wir andere Turing-Maschinen mit einer Turing-Maschine simulieren 47:51.240 --> 47:51.620 können. 47:53.000 --> 47:57.040 Das heißt, wir können eine Folge von Anweisungen oder sowas relativ 47:57.040 --> 48:00.560 einfach aus diesen elementaren Turing-Maschinen zusammenbauen. 48:00.560 --> 48:03.740 Genauso auch Repeat-Schleifen oder Verzweigungen. 48:06.640 --> 48:13.520 Das heißt, die Konstruktion einer Turing-Maschine entspricht dem 48:13.520 --> 48:17.280 Schreiben eines höhersprachlichen Programms oder kann dem entsprechen. 48:19.600 --> 48:25.040 Was schon relativ nahe daran kommt oder was uns schon vermuten lässt, 48:25.320 --> 48:28.660 dass die Turing-Maschinen eben sehr mächtig sind und vielleicht 48:28.660 --> 48:31.500 genauso viel können wie ihr Rechner zu Hause. 48:34.450 --> 48:38.810 Ganz offensichtlich sind Turing-Maschinen intuitiv berechenbar. 48:40.990 --> 48:46.530 Die Frage wäre, ist jede intuitiv berechenbare Funktion auch Turing 48:46.530 --> 48:46.950 -berechenbar? 48:46.950 --> 48:55.310 Und das ist diese Church-These, eine ganz zentrale These in der 48:55.310 --> 48:59.730 Informatik, die eben besagt, jede im intuitiven Sinn berechenbare 48:59.730 --> 49:01.690 Funktion ist auch Turing-berechenbar. 49:04.670 --> 49:09.250 Das hat weitreichende Konsequenzen, weil eben diese These im Prinzip 49:09.250 --> 49:15.830 sagt, alles was ich irgendwie berechnen kann, kann ich durch Turing 49:15.830 --> 49:16.630 -Maschinen machen. 49:18.570 --> 49:21.790 Was natürlich auch bedeutet, es gibt keine leistungsfähigeren 49:21.790 --> 49:23.450 Automaten als die Turing-Maschinen. 49:24.750 --> 49:28.730 Das heißt, egal was für ein Java-Programm auf was für einem Rechner 49:28.730 --> 49:32.390 sie schreiben, egal welchem Rechner der in der Zukunft noch erfunden 49:32.390 --> 49:38.850 wird, er wird nicht leistungsfähiger sein, im Prinzip, als das was wir 49:38.850 --> 49:43.690 mit den Turing-Maschinen nachbilden können. 49:46.420 --> 49:51.460 Das ist nicht schlecht, vor allen Dingen wenn man sich bedenkt, dass 49:51.460 --> 49:55.120 die Turing-Maschine das erste formale Modell war, um intuitiv 49:55.120 --> 49:57.020 berechenbare Funktionen zu beschreiben. 49:57.580 --> 50:04.860 Also die Grundidee von dem Herrn Turing war, dass sie im Prinzip ein 50:04.860 --> 50:07.320 Blatt Papier haben, wenn sie Berechnungen ausführen. 50:07.720 --> 50:10.800 Sie können sich da Sachen merken, sie können den Stift eben dort 50:10.800 --> 50:13.860 ansetzen, sie können den Stift dort ansetzen, vor- und zurückbewegen, 50:13.980 --> 50:16.800 Sachen durchstreichen, irgendwas ausradieren. 50:18.580 --> 50:21.400 Und er hat das in einer vereinfachten Art und Weise in der Turing 50:21.400 --> 50:23.360 -Maschine nachgebildet. 50:23.800 --> 50:26.840 Indem er eben gesagt hat, okay wir haben jetzt ein Eingabeband, aber 50:26.840 --> 50:29.640 ich kann eben da was schreiben, ich kann was ausradieren, ich kann 50:29.640 --> 50:33.180 mich rechts und links bewegen mit meinem Stift oder Schreib-Lesekopf. 50:36.900 --> 50:39.720 Insofern kommt das so der Berechnung mit einem Blatt Papier relativ 50:39.720 --> 50:40.080 nahe. 50:42.640 --> 50:47.120 Und heute geht man sogar noch einen Schritt weiter und man sagt, 50:47.760 --> 50:51.880 Turing -Maschinen können nicht nur alles das berechnen, was im 50:51.880 --> 50:55.760 intuitiven Sinne berechenbar ist, sondern sie können bis auf 50:55.760 --> 51:00.500 polynomielle Faktoren auch die Rechenzeit erfassen. 51:03.060 --> 51:06.760 Das heißt, was wir jetzt hier gemacht haben mit diesen Turing 51:06.760 --> 51:10.180 -Maschinen war ja teilweise extrem umständlich, oder es schien 51:10.180 --> 51:10.960 zumindest so. 51:11.880 --> 51:18.360 Das heißt, wir haben ewig lange Bandbeschriftungen und wir müssen da 51:18.360 --> 51:21.520 dick mal vor und zurück und immer wieder hier was ändern und dort was 51:21.520 --> 51:22.660 ändern und was weiß ich. 51:24.360 --> 51:31.440 Und die Aussage ist eben jetzt, dass trotzdem diese Turing-Maschinen 51:31.440 --> 51:37.900 vielleicht relativ umständlich erscheinen, sie nicht viel schlechter, 51:38.320 --> 51:43.340 also in Bezug auf Effizienz, genauso effizient sind wie beliebige 51:43.340 --> 51:45.260 andere Maschinen, die man erfinden könnte. 51:50.380 --> 51:53.900 Also abgesehen von polynomiellen Faktoren. 51:55.000 --> 51:58.900 Und das bedeutet eben, dass ein Problem genau dann effizient oder in 51:58.900 --> 52:03.600 polynomieller Zeit lösbar ist, wenn es von Turing-Maschinen in 52:03.600 --> 52:05.400 polynomieller Zeit gelöst werden kann. 52:09.970 --> 52:13.930 Das ist alles nur eine These, aber es gibt viele Belege dafür. 52:14.090 --> 52:17.850 Man kann für viele Maschinenmodelle zeigen, dass sie eben genau 52:17.850 --> 52:22.150 äquivalent sind zu Turing-Maschinen, wie beispielsweise für Register 52:22.150 --> 52:26.490 -Maschinen, die sehr viel näher an dem dran sind, was wir heutzutage 52:26.490 --> 52:27.510 als Computer haben. 52:29.770 --> 52:33.550 Und insofern kann man davon ausgehen, dass diese Church-These eben 52:33.550 --> 52:34.590 auch korrekt ist. 52:37.200 --> 52:41.160 Das bedeutet für uns natürlich, dass wir in Fragen der Berechenbarkeit 52:41.160 --> 52:45.920 einfach nur Turing-Maschinen anschauen müssen, uns auf dieses Modell 52:45.920 --> 52:49.980 beschränken können und alles, was wir da zeigen, gilt für alle anderen 52:49.980 --> 52:51.780 Rechnermodelle ebenso. 52:53.720 --> 52:56.600 Beispielsweise müssen wir eben nicht mehr unterscheiden zwischen 52:56.600 --> 53:01.200 Turing -aufzählbar und aufzählbar oder Turing-entscheidbar und 53:01.200 --> 53:06.660 entscheidbar, sondern diese Begriffe sind eben dann äquivalent. 53:07.060 --> 53:10.780 Alles, was ich im intuitiven Sinne berechnen kann, kann ich auch 53:10.780 --> 53:12.000 Turing berechnen. 53:12.200 --> 53:15.360 Alles, was ich im intuitiven Sinne entscheiden kann, oder nach dieser 53:15.360 --> 53:18.020 Definition kann ich eben auch Turing entscheiden und umgekehrt. 53:21.390 --> 53:24.130 Gut, das war schon mal ein ganz wesentlicher Punkt. 53:30.520 --> 53:37.520 Jetzt sind wir aber, glaube ich, haben wir noch kein Beispiel gefunden 53:37.520 --> 53:42.520 für ein Problem, das wir nicht entscheiden können, eine Funktion, die 53:42.520 --> 53:44.380 nicht entscheidbar ist. 53:45.860 --> 53:52.920 Und das Halte-Problem ist so das ganz typische, grundlegende Beispiel 53:52.920 --> 53:55.560 für ein nicht entscheidbares Problem. 53:56.980 --> 54:01.060 Die Frage ist hier, gibt es einen Algorithmus, der für jedes Programm 54:01.060 --> 54:06.440 P entscheidet, ob das Programm bei einer bestimmten Eingabe W hält 54:06.440 --> 54:07.840 oder nicht hält. 54:11.090 --> 54:13.810 Anders ausgedrückt, weil wir ja jetzt wissen, Turing-Maschinen sind 54:13.810 --> 54:17.630 genau äquivalent, können wir fragen, gibt es eine Turing-Maschine, die 54:17.630 --> 54:23.530 für jede Turing-Maschine T entscheidet, ob T bei der Eingabe von W 54:23.530 --> 54:25.230 hält oder nicht hält. 54:26.690 --> 54:30.750 Die Behauptung ist eben jetzt, dass dieses Halte-Problem für Turing 54:30.750 --> 54:37.610 -Maschinen unentscheidbar ist und wir beweisen das durch Widerspruch. 54:38.870 --> 54:43.870 Und zwar nehmen wir an, es gäbe eine Turing-Maschine H, die 54:43.870 --> 54:48.350 entscheidet, ob eine beliebige Turing-Maschine T angesetzt auf eine 54:48.350 --> 54:50.330 beliebige Eingabe W hält. 54:52.130 --> 55:01.810 Und wir zeigen, dass wenn es diese Maschine H gibt, dass wir dann auch 55:01.810 --> 55:05.730 eine Turing-Maschine konstruieren können, sodass die Sprache dieser 55:05.730 --> 55:11.730 Turing -Maschine T genau diese Sprache LNA ist, die wir vorhin 55:11.730 --> 55:12.730 ausgeschlossen haben. 55:12.730 --> 55:14.430 Also ich gehe nochmal kurz zurück. 55:15.910 --> 55:16.970 Diese Sprache hier. 55:18.610 --> 55:25.370 Alle Worte WI, bei denen WI nicht zur Sprache vom TI gehört. 55:30.080 --> 55:30.640 Gut. 55:32.800 --> 55:33.640 Okay. 55:34.360 --> 55:38.080 Wir müssen also jetzt einen Algorithmus angeben für diese Turing 55:38.080 --> 55:45.660 -Maschine, die diese Sprache erkennt. 55:47.040 --> 55:55.960 Und wir dürfen verwenden, dass wir entscheiden können, ob die Maschine 55:55.960 --> 55:57.700 hält oder nicht hält. 55:58.720 --> 56:00.420 Und das sieht dann so aus. 56:01.940 --> 56:04.340 Wir haben als Eingabe eben unser Wort. 56:08.400 --> 56:15.820 Und wir sollen ausgeben WAR, falls das Wort in dieser Sprache drin 56:15.820 --> 56:16.140 ist. 56:17.180 --> 56:21.840 Und im anderen Fall eben FALSCH. 56:23.900 --> 56:28.980 Das Erste, was wir machen, ist, dass wir das zugehörige I zu diesem 56:28.980 --> 56:29.680 Wort bestimmen. 56:30.600 --> 56:34.440 Wir hatten ja gesagt, wir können all diese Worte durchnummerieren, 56:34.900 --> 56:36.800 auch alle Turing-Maschinen durchnummerieren. 56:36.800 --> 56:40.820 Und wir schauen jetzt einfach, wir gehen alle Worte durch, bis wir auf 56:40.820 --> 56:47.520 unser Wort W stoßen und sagen dann, okay, das ist das zugehörige I in 56:47.520 --> 56:51.440 unserer Durchnummerierung, in unserer Ordnung. 56:54.300 --> 56:58.360 Dann können wir natürlich auch die dazugehörige Turing-Maschine TI 56:58.360 --> 57:00.980 bestimmen, wenn wir dieses I haben. 57:03.400 --> 57:12.200 Und dann nehmen wir an, wir haben diese Turing-Maschine H, die uns 57:12.200 --> 57:18.140 eben sagt, ob die Turing-Maschine TI auf dem Wort BI hält. 57:19.980 --> 57:33.660 Wenn das TI auf dem BI hält, dann, wunderbar, dann können wir die 57:33.660 --> 57:34.360 simulieren. 57:36.480 --> 57:41.200 Irgendwann bricht dann diese Maschine ja ab und wir wissen dann, okay, 57:41.300 --> 57:49.420 das BI ist Element von TI, dann geben wir FALSE aus, weil das ja genau 57:49.420 --> 57:53.240 die Bedingung war von dieser Sprache, und ansonsten geben wir TRUE 57:53.240 --> 57:53.600 aus. 57:56.960 --> 58:02.820 Und wenn es nicht hält, dann geben wir eben auch TRUE aus, weil dann 58:02.820 --> 58:07.800 das Wort nicht zur Sprache TI gehört. 58:08.800 --> 58:13.180 Ja, und das erledigt genau das Gewünschte. 58:14.480 --> 58:21.580 Wir haben dann einen Automaten, der diese Sprache LFNA akzeptiert, 58:23.940 --> 58:28.100 wovon wir aber gezeigt haben, dass das nicht sein kann. 58:32.790 --> 58:37.410 Und da wir alles, was wir hier gemacht haben in diesem Algorithmus 58:37.410 --> 58:41.510 auch tatsächlich machen können, bis auf diesen entscheidenden Punkt 58:41.510 --> 58:49.110 hier, diese IF-Entscheidung, diese Bedingung, ob TI angesetzt auf BI 58:49.110 --> 58:54.170 hält oder nicht, da wissen wir nicht, ob wir das tatsächlich machen 58:54.170 --> 58:58.530 können oder nicht, können wir folgern, okay, wir können das nicht, das 58:58.530 --> 58:59.450 ist ein Widerspruch. 59:04.850 --> 59:10.250 Und unsere Annahme, dass wir eine solche Maschine haben, die uns 59:10.250 --> 59:14.790 angeben kann, ob eine Turing-Maschine auf einem beliebigen Wort stoppt 59:14.790 --> 59:16.070 oder nicht, ist also falsch. 59:19.510 --> 59:21.910 Das ist schon mal eine wichtige Erkenntnis. 59:23.610 --> 59:28.370 Das heißt, wir haben ein Problem, das ganz klar nicht entscheidbar 59:28.370 --> 59:28.630 ist. 59:31.370 --> 59:34.410 Und das ist auch interessant, sich zu überlegen. 59:35.870 --> 59:37.430 Also das ist eine interessante Anwendung. 59:37.430 --> 59:43.590 Aber noch wichtiger ist im Prinzip, dass man aufgrund dieses Problems, 59:43.590 --> 59:45.830 wo man jetzt hier mal gezeigt hat, dieses Problem ist nicht 59:45.830 --> 59:49.370 entscheidbar, dass man dann anfangen konnte, das zu erweitern. 59:49.630 --> 59:53.590 Man konnte für andere Probleme nachweisen, indem man zeigt, dass sie 59:53.590 --> 59:57.870 genauso kompliziert sind wie dieses Problem, dass sie eben auch nicht 59:57.870 --> 59:58.750 entscheidbar sind. 01:00:03.880 --> 01:00:07.540 Man kann also für viele praktische Fragen nachweisen, dass es nicht 01:00:07.540 --> 01:00:08.340 entscheidbar ist. 01:00:08.980 --> 01:00:14.000 Das eine ist eben, hält ein Programm für eine bestimmte Eingabe an? 01:00:15.700 --> 01:00:19.560 Das gilt eben einfach nur, weil wir jetzt von Turing-Maschine auf 01:00:19.560 --> 01:00:21.400 beliebige Programme umsteigen können. 01:00:22.680 --> 01:00:26.280 Andere nicht entscheidbare Fragen sind, ist ein Programm korrekt? 01:00:31.310 --> 01:00:35.810 Das ist natürlich auch eine ganz wichtige Erkenntnis, wenn man gar nie 01:00:35.810 --> 01:00:39.290 nachweisen kann, dass ein Programm tatsächlich korrekt ist. 01:00:40.150 --> 01:00:45.770 Es kann keinen Algorithmus geben, dem man ein Programm gibt und sagt, 01:00:45.890 --> 01:00:47.910 hier überprüft dieses Programm auf Korrektheit. 01:00:51.990 --> 01:00:56.430 Das heißt, auch in Zukunft wird das nicht möglich sein. 01:00:58.450 --> 01:01:02.870 Sie können immer auf syntaktische Korrektheit überprüfen, aber sie 01:01:02.870 --> 01:01:06.470 können nie überprüfen, ob das Programm auch tatsächlich das macht, was 01:01:06.470 --> 01:01:07.610 es eigentlich machen soll. 01:01:09.510 --> 01:01:13.730 Was wiederum bedeutet, dass Sie eben beim Entwurf von Programmen schon 01:01:13.730 --> 01:01:15.250 stark auf Korrektheit achten müssen. 01:01:15.350 --> 01:01:20.010 Wenn Sie das Programm mal geschrieben haben, können Sie es nicht mehr 01:01:20.010 --> 01:01:21.650 ohne weiteres überprüfen. 01:01:23.210 --> 01:01:26.630 Eine andere Frage, die nicht entscheidbar ist, sind zwei Programme P 01:01:26.630 --> 01:01:27.790 und Q-Äquivalent. 01:01:28.070 --> 01:01:29.850 Tun die das Gleiche? 01:01:33.330 --> 01:01:36.950 Und das gilt nicht nur für beliebig komplizierte Programme, sondern 01:01:36.950 --> 01:01:42.190 sogar schon bei zwei kontextfreien Grammatiken, G oder G', kann ich 01:01:42.190 --> 01:01:43.610 nicht mehr die Äquivalenz zeigen. 01:01:44.350 --> 01:01:51.370 Wir erinnern uns, dass für Typ-3-Grammatiken man die Äquivalenz noch 01:01:51.370 --> 01:01:52.030 zeigen konnte. 01:01:53.090 --> 01:01:56.950 Wir hatten ja ein Verfahren kennengelernt, wie man Automaten minimiert 01:01:56.950 --> 01:02:01.550 und wir können einen minimalen Automaten bestimmen und wenn sich eben 01:02:01.550 --> 01:02:06.630 verschiedene Automaten auf den gleichen minimalen Automaten reduzieren 01:02:06.630 --> 01:02:09.310 lassen, der ist eindeutig bestimmt, dann wissen wir auch diesen 01:02:09.310 --> 01:02:09.930 Äquivalent. 01:02:10.630 --> 01:02:15.270 Schon bei kontextfreien, also den Typ-3-Sprachen, kann ich das nicht 01:02:15.270 --> 01:02:15.890 mehr einlegen. 01:02:18.550 --> 01:02:22.290 Gut, eine Bemerkung hatte ich jetzt hier noch übergangen. 01:02:22.870 --> 01:02:27.730 Dieses Halteproblem kann man zeigen, dass es zur Sprache L0 gehört. 01:02:32.820 --> 01:02:37.980 Das heißt, das ist einfach nur interessant zu sehen, wir haben jetzt 01:02:37.980 --> 01:02:40.480 hier eine weitere Unterscheidung. 01:02:43.840 --> 01:02:47.900 Wir können die L0-Sprachen jetzt noch weiter untergliedern in 01:02:47.900 --> 01:02:51.520 entscheidbare Sprachen und in nicht entscheidbare Sprachen. 01:02:51.520 --> 01:02:57.400 Und das Halteproblem ist eben gerade hier, gehört zwar zur L0, aber 01:02:57.400 --> 01:03:00.600 ist nicht mehr entscheidbar und es gibt natürlich andere, die 01:03:00.600 --> 01:03:01.520 entscheidbar sind. 01:03:04.130 --> 01:03:07.250 Gut, also hier nochmal so die Übersicht, wie sich die gliedern. 01:03:08.070 --> 01:03:11.810 Die Typ-3-Sprachen ist die kleinste Menge, dann gibt es welche, die 01:03:11.810 --> 01:03:14.790 sind tatsächlich immer echte Untermengen. 01:03:15.470 --> 01:03:18.210 Die sind nicht gleich, sondern es gibt welche, die sind in L2 und 01:03:18.210 --> 01:03:22.930 nicht in L3, es gibt Sprachen, die sind in L1 und nicht in L2, es gibt 01:03:22.930 --> 01:03:24.050 und so weiter. 01:03:27.830 --> 01:03:31.690 Es gibt natürlich auch noch, und das möchte ich jetzt nur der 01:03:31.690 --> 01:03:37.110 Vollständigkeit halber erwähnen, Definitionen von Grammatiken, mit 01:03:37.110 --> 01:03:41.250 denen man Sprachklassen definiert, die quer zur Komms-Hierarchie 01:03:41.250 --> 01:03:45.050 liegen, also die einfach eine andere Unterteilung machen. 01:03:46.930 --> 01:03:50.390 Beispielsweise gibt es, das ist mir in der Biologie wichtig, 01:03:50.490 --> 01:03:56.010 Lindenmayr -Systeme, im Wesentlichen zur Beschreibung vom Wachstum von 01:03:56.010 --> 01:03:56.710 Organismen. 01:03:57.550 --> 01:04:00.810 Da haben sie, grob gesagt, zumindest in der einfachen Form, 01:04:01.170 --> 01:04:03.950 kontextfreie Regeln und parallele Ableitungen, d.h. 01:04:04.030 --> 01:04:08.210 sie führen nicht einen Ableitungsschritt nach dem anderen aus, sondern 01:04:08.210 --> 01:04:11.470 sie führen alle Ableitungsschritte, die möglich sind, eben 01:04:11.470 --> 01:04:13.310 gleichzeitig aus, parallel aus. 01:04:15.150 --> 01:04:21.950 Sie können stochastische Automaten betrachten, d.h. 01:04:22.150 --> 01:04:26.550 endliche Automaten mit stochastischen Zustandsübergängen und ein Wort 01:04:26.550 --> 01:04:30.950 wird dann akzeptiert, wenn nach Einlesen des Wortes mit ausreichend 01:04:30.950 --> 01:04:33.350 großer Wahrscheinlichkeit der Endzustand erreicht ist. 01:04:34.010 --> 01:04:37.050 Das wären so mögliche Alternativen. 01:04:38.190 --> 01:04:42.090 Aber für die Informatik hat sich die Wilkomsky-Hierarchie als sehr 01:04:42.090 --> 01:04:46.510 hilfreich erwiesen und deswegen ist das auch die, die wir hier 01:04:46.510 --> 01:04:47.270 betrachtet haben. 01:04:50.020 --> 01:04:54.980 Okay, wir können unsere zusammenfassende Tabelle jetzt ein bisschen 01:04:54.980 --> 01:04:55.640 erweitern. 01:04:56.800 --> 01:05:02.660 Wir haben zusätzlich eben festgestellt, dass die Menge der allgemeinen 01:05:02.660 --> 01:05:06.900 L0 -Sprachen unterteilt werden kann in einmal die entscheidbaren 01:05:06.900 --> 01:05:09.960 Sprachen und in die aufzählbaren Sprachen. 01:05:12.140 --> 01:05:16.420 Wir haben ein Beispiel kennengelernt für diese aufzählbaren Sprachen. 01:05:16.960 --> 01:05:18.480 Das war eben das Halteproblem. 01:05:20.200 --> 01:05:23.500 Hält eine bestimmte Turing-Maschine auf einem beliebigen Wort B oder 01:05:23.500 --> 01:05:23.880 nicht? 01:05:25.660 --> 01:05:29.140 Nicht entscheidbar, aber noch Element L0. 01:05:31.220 --> 01:05:40.280 Und wir haben eine Sprache kennengelernt, die zu keiner dieser Typen 01:05:40.280 --> 01:05:43.800 gehört, also die noch außerhalb von L0 liegt. 01:05:46.860 --> 01:05:53.180 Und das war eben diese Sprache LNA, die wir zwar nicht angeben können, 01:05:53.280 --> 01:05:55.240 aber von der wir eben nachweisen können, mithilfe des 01:05:55.240 --> 01:05:58.260 Diagonalisierungsverfahrens, dass es die tatsächlich geben muss. 01:06:07.300 --> 01:06:07.940 Gut. 01:06:07.940 --> 01:06:11.980 Kommen wir zu einer ganz anderen Fragestellung noch. 01:06:18.170 --> 01:06:23.310 Und zwar wollen wir jetzt ein bisschen genauer quantifizieren, nicht 01:06:23.310 --> 01:06:27.850 nur ist ein bestimmtes Problem berechenbar oder ist es nicht 01:06:27.850 --> 01:06:32.490 berechenbar, sondern was kostet mich denn die Berechnung von so einer 01:06:32.490 --> 01:06:35.030 Funktion oder was kostet mich die Lösung eines Problems? 01:06:37.050 --> 01:06:39.610 In verschiedenen Dimensionen. 01:06:39.690 --> 01:06:41.290 Das heißt einmal in der Zeit. 01:06:41.790 --> 01:06:43.090 Wie viel Zeit brauche ich? 01:06:43.590 --> 01:06:44.710 Wie viel Platz brauche ich? 01:06:44.730 --> 01:06:46.210 Wie viel Speicherplatz brauche ich? 01:06:48.930 --> 01:06:52.730 Und die Antwort ist natürlich abhängig vom zugrunde liegenden 01:06:52.730 --> 01:06:53.810 Berechnungsmodell. 01:06:55.130 --> 01:06:58.910 Das heißt berechne ich jetzt das auf eine Turing-Maschine oder auf 01:06:58.910 --> 01:07:01.790 eine Register-Maschine, auf eine einbandigen oder auf einer 01:07:01.790 --> 01:07:03.710 zweibandigen Turing-Maschine und so weiter. 01:07:03.710 --> 01:07:08.910 Und es ist natürlich auch abhängig vom verwendeten Algorithmus. 01:07:09.830 --> 01:07:13.110 Habe ich das effizient programmiert oder habe ich das eher weniger 01:07:13.110 --> 01:07:14.170 effizient programmiert? 01:07:14.290 --> 01:07:16.770 Entsprechend werde ich natürlich mehr oder weniger Zeit brauchen. 01:07:21.270 --> 01:07:24.290 Und das hilft uns nicht sonderlich weiter. 01:07:27.090 --> 01:07:33.070 Also die Zeit zu messen, wie viel das in Java in der und der Art und 01:07:33.070 --> 01:07:39.170 Weise programmiert auf einem Intel 500 MHz Prozessor braucht, das sind 01:07:39.170 --> 01:07:42.730 so spezielle Aussagen, dass man damit relativ wenig anfangen kann. 01:07:43.450 --> 01:07:50.050 Was wir suchen sind Antworten, die uns für eine Klasse von Problemen 01:07:50.050 --> 01:07:57.890 grob sagen, wie viele elementare Operationen so größenordnungsmäßig 01:07:57.890 --> 01:07:58.470 braucht man. 01:07:59.030 --> 01:08:02.310 Kann man die Probleme unterscheiden in vielleicht einfache Probleme 01:08:02.310 --> 01:08:03.510 und schwierige Probleme? 01:08:07.230 --> 01:08:12.470 Und man kann das eben mit verschiedenen Berechnungsmodellen machen, 01:08:12.570 --> 01:08:18.050 Turing -Maschinen, Register-Maschinen, parallele Register-Maschinen. 01:08:20.290 --> 01:08:24.570 Wir haben ja mithilfe der Churchill-These schon gezeigt, dass im 01:08:24.570 --> 01:08:25.970 Prinzip alle äquivalent sind. 01:08:26.650 --> 01:08:30.250 Und eben mit der Erweiterung auch gesagt, dass wahrscheinlich die alle 01:08:30.250 --> 01:08:36.710 gleich viel vom Berechnungsaufwand her sich nur polynomiell 01:08:36.710 --> 01:08:37.350 unterscheiden. 01:08:50.410 --> 01:08:58.970 Wenn ich ein festes Problem habe, dann kann ich obere Schranken für 01:08:58.970 --> 01:09:06.370 den Berechnungsaufwand durch die Analyse eines Algorithmus angeben. 01:09:06.370 --> 01:09:09.230 Das haben sie in Informatik 1 gemacht. 01:09:09.550 --> 01:09:12.770 Das war diese Groß-O-Notation. 01:09:13.470 --> 01:09:17.550 Sie können sich ein Algorithmus anschauen und können sagen, der 01:09:17.550 --> 01:09:22.250 braucht O von N² Berechnungszeit. 01:09:25.480 --> 01:09:29.320 Da muss ich aber natürlich den Algorithmus irgendwie spezifizieren. 01:09:29.480 --> 01:09:33.940 Frage ist, könnte es nicht vielleicht einen effizienteren Algorithmus 01:09:33.940 --> 01:09:34.300 geben? 01:09:34.300 --> 01:09:39.240 Kann ich zeigen, dass es für bestimmte Probleme polynomielle 01:09:39.240 --> 01:09:42.600 Algorithmen gibt und für andere Probleme aber keine polynomiellen 01:09:42.600 --> 01:09:43.760 Algorithmen gibt? 01:09:48.270 --> 01:09:52.150 Ich kann eben auch versuchen, dass ich untere Schranken definiere. 01:09:53.350 --> 01:09:56.770 Das heißt, egal was für ein Algorithmus ich entwickle und wie viel 01:09:56.770 --> 01:10:00.370 Entwicklungszeit ich da rein stelle und welcher schlauer Kopf sich da 01:10:00.370 --> 01:10:05.790 ransetzt, der Algorithmus wird immer mindestens so viel Zeit brauchen. 01:10:05.950 --> 01:10:09.010 Und das ist das, was uns eben jetzt hier interessiert, was wir uns im 01:10:09.010 --> 01:10:09.890 Folgenden anschauen. 01:10:11.370 --> 01:10:19.250 Wir verwenden dabei eben wieder die Turing-Maschinen als allgemeine 01:10:19.250 --> 01:10:21.970 Definition. 01:10:23.770 --> 01:10:26.890 Die zwei wesentlichen Aspekte, die wir uns dabei anschauen, sind die 01:10:26.890 --> 01:10:28.590 Zeit - und die Platzkomplexität. 01:10:30.210 --> 01:10:34.390 Und die sind folgendermaßen definiert, die Zeitkomplexität der 01:10:34.390 --> 01:10:40.490 Berechnung von f mit einer Turing-Maschine für ein bestimmtes 01:10:40.490 --> 01:10:48.630 Wortelement m1 ist die Länge der kürzesten Konfigurationsfolge von der 01:10:48.630 --> 01:10:51.250 Anfangs - zur Endkonfiguration. 01:10:52.210 --> 01:10:56.150 Das heißt, diese Turing-Maschine durchläuft eine Konfiguration nach 01:10:56.150 --> 01:10:56.530 der anderen. 01:10:57.690 --> 01:11:02.550 Und ich gucke mir jetzt an, wie viele Konfigurationsfolgen muss denn 01:11:02.550 --> 01:11:06.830 diese Turing-Maschine im besten Fall durchlaufen, um von Anfangs- zur 01:11:06.830 --> 01:11:08.070 Endkonfiguration zu kommen. 01:11:09.770 --> 01:11:12.170 Und das gibt mir quasi ein Maß für die Zeit. 01:11:12.930 --> 01:11:17.950 Ich betrachte jeden Konfigurationsübergang als einen Zeitschritt, als 01:11:17.950 --> 01:11:21.810 einen elementaren Schritt und zähle, wie viele solche Zeitschritte 01:11:21.810 --> 01:11:22.510 braucht sie denn. 01:11:23.370 --> 01:11:30.510 Hier nochmal formal aufgeschrieben, T von n ist die maximale... 01:11:40.840 --> 01:11:43.240 Ah ja, nee, das ist was anderes. 01:11:45.060 --> 01:11:48.860 Also diese Zeitkomplexität war hier definiert für ein bestimmtes Wort. 01:11:49.680 --> 01:11:57.100 Und wir definieren jetzt hier noch das Groß-T von m, das Groß-T von n, 01:11:57.580 --> 01:12:00.640 als das maximale Kleine-T von w. 01:12:02.360 --> 01:12:06.000 Wobei das w alle Worte sein können mit einer bestimmten Länge m. 01:12:06.800 --> 01:12:10.820 Also wir schauen uns hier den schlechtesten Fall an, für ein Wort der 01:12:10.820 --> 01:12:11.340 Länge n. 01:12:11.940 --> 01:12:15.480 Und welche Zeitkomplexität hat da eine Turing-Maschine? 01:12:16.350 --> 01:12:23.200 Und bei der Platzkomplexität ist es im Prinzip das gleiche, nur dass 01:12:23.200 --> 01:12:26.900 wir uns hier nach der Zeit den Platz anschauen, den die Turing 01:12:26.900 --> 01:12:27.610 -Maschine braucht. 01:12:31.960 --> 01:12:37.200 Die Platzkomplexität P von w der Berechnung von f mit einer Turing 01:12:37.200 --> 01:12:39.140 -Maschine für w-Element m1... 01:12:39.140 --> 01:12:43.000 ist die Anzahl der durch Schreiben veränderten Zellen des Bandes in 01:12:43.000 --> 01:12:46.840 der kürzesten Konfigurationenfolge von der Initial-zu-End 01:12:46.840 --> 01:12:47.640 -Konfiguration. 01:12:48.960 --> 01:12:54.060 Und genauso wie wir eben das bei der Zeit gemacht haben, machen wir 01:12:54.060 --> 01:12:59.520 das mit dem Groß-T abhängig von m und nicht mehr von w. 01:13:00.040 --> 01:13:04.260 Und schauen uns eben den schlechtesten Fall an, für alle Worte mit der 01:13:04.260 --> 01:13:04.740 Länge n. 01:13:07.650 --> 01:13:14.950 Man könnte natürlich auch Maße definieren für das mittlere Verhalten 01:13:14.950 --> 01:13:17.470 oder das Verhalten im besten Fall. 01:13:20.710 --> 01:13:27.690 Der beste Fall ist normalerweise nicht sonderlich interessant, weil 01:13:27.690 --> 01:13:30.590 das ja dann nur für ein bestimmtes Problem gilt. 01:13:31.330 --> 01:13:36.390 Das mittlere Verhalten wäre sehr interessant, wenn wir also wüssten, 01:13:36.490 --> 01:13:39.710 wie lange braucht ein Algorithmus im Durchschnitt, wenn ich ihm ein 01:13:39.710 --> 01:13:41.030 beliebiges Problem gebe. 01:13:42.110 --> 01:13:46.530 Aber das ist eben im Allgemeinen nicht so einfach zu fassen und 01:13:46.530 --> 01:13:49.990 deswegen beschränken wir uns hier auf den Berechnungsaufwand im 01:13:49.990 --> 01:13:50.870 schlechtesten Fall. 01:13:58.230 --> 01:13:59.010 Okay. 01:14:02.130 --> 01:14:06.690 Jetzt können wir Komplexitätsklassen definieren, aufgrund der 01:14:06.690 --> 01:14:08.490 Definition, die wir gerade gemacht haben. 01:14:10.230 --> 01:14:13.550 Sei g eine beliebige Funktion. 01:14:30.490 --> 01:14:37.390 Also f ist die Funktion der Turing-Maschine, wie die Turing-Maschine 01:14:37.390 --> 01:14:37.910 berechnet. 01:14:41.410 --> 01:14:53.250 Und jetzt bezeichnen wir mit d Time von g alle Funktionen f, wobei f 01:14:53.250 --> 01:14:59.010 mit einer Zeitkomplexität o von g von einer deterministischen Turing 01:14:59.010 --> 01:15:00.830 -Maschine berechenbar ist. 01:15:02.950 --> 01:15:04.470 Okay, was heißt das? 01:15:05.170 --> 01:15:15.270 Das g sind typische Funktionen, beispielsweise n oder n hoch k oder 2 01:15:15.270 --> 01:15:23.590 hoch n oder n log n oder was auch immer, wie sie es eben auch aus den 01:15:23.590 --> 01:15:27.750 Komplexitätsklassen kennen, also n², was auch immer. 01:15:30.830 --> 01:15:36.990 Und dieses d Time g sind jetzt alle Funktionen, die ich beispielsweise 01:15:36.990 --> 01:15:44.810 in Zeit o von n² oder o von 2 hoch n von einer deterministischen 01:15:44.810 --> 01:15:46.270 Turing -Maschine berechnen kann. 01:15:47.370 --> 01:15:55.330 Und mit n Time bezeichnen wir das gleiche, aber für eine nicht 01:15:55.330 --> 01:15:56.830 -deterministische Turing-Maschine. 01:15:58.650 --> 01:16:02.950 Wenn Sie sich erinnern, Turing-Maschinen, deterministische und nicht 01:16:02.950 --> 01:16:07.430 -deterministische sind gleich mächtig, aber wir hatten gezeigt, dass 01:16:07.430 --> 01:16:10.990 nicht -deterministische Turing-Maschinen viel schneller sein können. 01:16:11.250 --> 01:16:13.730 Beziehungsweise wenn ich mit einer deterministischen eine nicht 01:16:13.730 --> 01:16:17.330 -deterministischen simuliere, dass ich exponentiellen Aufwand mehr 01:16:17.330 --> 01:16:17.970 haben kann. 01:16:20.930 --> 01:16:25.230 Und d Space und n Space können wir analog definieren. 01:16:26.650 --> 01:16:31.090 Eben die Platzkomplexität o von g jeweils wieder von einer 01:16:31.090 --> 01:16:34.630 deterministischen Turing-Maschine und von einer nicht 01:16:34.630 --> 01:16:36.150 -deterministischen Turing-Maschine. 01:16:48.620 --> 01:16:54.040 Dann gibt es noch ganz besondere Klassen, also das war jetzt eine 01:16:54.040 --> 01:16:56.480 allgemeine Definition, aber ganz im Speziellen. 01:16:57.940 --> 01:17:02.280 Die Klasse der in polynomieller Zeit berechenbaren Funktionen. 01:17:03.020 --> 01:17:10.740 Und das sind für uns auch die Funktionen, wo wir im Prinzip sagen, die 01:17:10.740 --> 01:17:12.180 sind effizient berechenbar. 01:17:26.330 --> 01:17:35.070 Die bezeichnen wir als P. Und das ist gerade die Vereinigung aller d 01:17:35.070 --> 01:17:36.830 Time n hoch k. 01:17:37.770 --> 01:17:41.850 Also wir haben hier im Polynom stehen, alles was in polynomieller 01:17:41.850 --> 01:17:45.170 Zeitkomplexität berechenbar ist, für alle k Element n. 01:17:45.350 --> 01:17:48.870 Also uns ist egal, ob jetzt n Quadrat oder n hoch 5 oder n hoch 10. 01:17:49.830 --> 01:17:53.770 Und all diese Funktionen, die wir in dieser Zeitkomplexität berechnen 01:17:53.770 --> 01:17:58.210 können, bezeichnen wir als P. Von einer deterministischen Turing 01:17:58.210 --> 01:17:58.670 -Maschine. 01:17:59.850 --> 01:18:01.930 Also hier d Time. 01:18:07.390 --> 01:18:13.170 Und np haben wir hier n Time, das ist die Klasse der von nicht 01:18:13.170 --> 01:18:15.810 -deterministischen Turing-Maschinen in polynomieller Zeit 01:18:15.810 --> 01:18:16.810 berechenbaren Funktionen. 01:18:22.960 --> 01:18:29.580 Nicht-deterministisch hatten wir ja definiert als eine Maschine, die 01:18:29.580 --> 01:18:32.120 irgendwie ein Orakel hat und weiß, was sie zu tun hat. 01:18:32.540 --> 01:18:36.460 Im Prinzip weiß, welche Alternativen sie auswählen muss. 01:18:38.160 --> 01:18:42.180 Man kann das auch für Optimierungsprobleme oder 01:18:42.180 --> 01:18:48.320 Berechenbarkeitsprobleme so deuten, dass eine nicht-deterministische 01:18:48.320 --> 01:18:51.580 Turing -Maschine eine potenzielle Lösung raten kann. 01:18:53.780 --> 01:18:59.980 Und dann in polynomieller Zeit die Korrektheit der Lösung überprüfen 01:18:59.980 --> 01:19:00.300 kann. 01:19:02.320 --> 01:19:06.360 Die nicht-deterministische Turing-Maschine kann das in polynomieller 01:19:06.360 --> 01:19:07.260 Zeit berechnen. 01:19:11.850 --> 01:19:15.270 Die deterministische könnte das im Prinzip, wenn sie die Information 01:19:15.270 --> 01:19:18.150 von der nicht-deterministischen hätte, über die korrekte Lösung. 01:19:19.030 --> 01:19:23.430 Dann könnte sie einfach den Pfad in dem Baum, wenn sie sich erinnern, 01:19:23.550 --> 01:19:27.710 nachgehen und könnte verifizieren, okay, das ist so oder das ist nicht 01:19:27.710 --> 01:19:28.010 so. 01:19:32.010 --> 01:19:38.210 Und deswegen NP bedeutet, bei den Problemen in NP kann man eine 01:19:38.210 --> 01:19:42.650 potenzielle Lösung raten und dann in polynomieller Zeit die 01:19:42.650 --> 01:19:43.650 Korrektheit überprüfen. 01:19:45.710 --> 01:19:53.250 Ganz offensichtlich gilt, dass das P Teilmenge ist von NP, weil ich 01:19:53.250 --> 01:19:56.530 natürlich was mit einer nicht-deterministischen Turing-Maschine in 01:19:56.530 --> 01:20:00.130 polynomieller Zeit berechnen kann, auch mit einer deterministischen 01:20:00.130 --> 01:20:02.630 Turing -Maschine in polynomieller Zeit berechnen kann. 01:20:04.190 --> 01:20:06.450 Was nicht so klar ist, ist die Umkehrung. 01:20:08.110 --> 01:20:13.350 Und das ist, denke ich, das berühmteste offene Problem der Informatik, 01:20:13.990 --> 01:20:17.830 die Frage, gilt P gleich NP oder gilt P ungleich NP? 01:20:21.110 --> 01:20:30.390 Was eben bedeuten würde, haben deterministische... 01:20:50.610 --> 01:20:59.530 Also ich denke, weshalb das so ein entscheidendes Problem ist, darauf 01:21:01.090 --> 01:21:05.210 kommen wir noch in der nächsten Stunde zu sprechen. 01:21:09.890 --> 01:21:15.570 Man weiß eben von vielen praktischen Problemen, dass sie in NP liegen. 01:21:16.770 --> 01:21:21.270 Dass also ich mit einer nicht-deterministischen Turing-Maschine die in 01:21:21.270 --> 01:21:22.930 polynomieller Zeit berechnen könnte. 01:21:24.590 --> 01:21:29.090 Aber man kann nicht zeigen, dass es nicht auch mit einer 01:21:29.090 --> 01:21:31.590 deterministischen Turing-Maschine geht. 01:21:34.010 --> 01:21:37.650 Das heißt, man kennt keinen Algorithmus, der das deterministisch in 01:21:37.650 --> 01:21:39.170 polynomieller Zeit löst. 01:21:40.370 --> 01:21:44.270 Und die brennende Frage ist eben jetzt, kann es überhaupt keinen 01:21:44.270 --> 01:21:45.590 solchen Algorithmus geben? 01:21:46.590 --> 01:21:48.870 Das wäre der Fall P ist ungleich NP. 01:21:50.590 --> 01:21:54.090 Oder kann es einen solchen Algorithmus geben, aber es ist nur noch 01:21:54.090 --> 01:21:56.990 keiner schlau genug gewesen und hat ihn erfunden? 01:21:57.690 --> 01:21:59.990 Das wäre der Fall P ist gleich NP. 01:22:00.890 --> 01:22:04.310 Und das ist natürlich eine brennende Frage. 01:22:06.250 --> 01:22:11.130 Ich denke aber, darauf werde ich einfach in der nächsten Stunde 01:22:11.130 --> 01:22:11.650 eingehen. 01:22:12.330 --> 01:22:13.070 Bis Montag.