WEBVTT 00:06.880 --> 00:13.240 Das Übungsblatt 3 ging im Wesentlichen nicht um zwei Gesamtkapitel, 00:13.360 --> 00:15.300 aber um Teile von Kapiteln. 00:15.440 --> 00:20.480 Und zwar einmal um das Kapitel, befinden wir uns im Skriptkapitel 3, 00:21.280 --> 00:23.480 und zwar Touringmaschinen und Berechenbarkeit. 00:24.680 --> 00:28.720 Da ging es jetzt bei den Übungen im Wesentlichen um universelle 00:28.720 --> 00:34.120 Touringmaschinen, Entscheidbarkeit und Semi-Entscheidbarkeit, Satz von 00:34.120 --> 00:36.520 Reis, Post-Korrespondenz-Problem. 00:37.640 --> 00:43.200 Und die Aufgaben 4 und 5, da ging es dann schon um Kapitel 4, ist das 00:43.200 --> 00:46.200 im Skript, das ist Komplexitätsklassen. 00:47.140 --> 00:50.580 Da geht es dann nochmal um Sprachen, Probleme und Zeitkomplexitäten, 00:51.100 --> 00:54.760 Klasse NP und über die Klasse P und NP hinaus. 00:55.560 --> 01:00.640 Das haben wir gemacht, gerade die Zusatzaufgabe, das war eine 01:00.640 --> 01:04.240 Fleißaufgabe im Wesentlichen und damit ihr auch wisst, wo liegen die 01:04.240 --> 01:06.840 Probleme P und P und was gibt es noch darüber hinaus. 01:08.740 --> 01:12.560 So, machen wir noch eine kleine Wiederholung zum Stoff, bevor wir in 01:12.560 --> 01:14.960 die Übungen richtig einsteigen. 01:16.580 --> 01:18.760 Was heißt entscheidbar? 01:19.800 --> 01:24.100 In der Vorlesung haben wir gehört, eine Sprache, L ist entscheidbar. 01:25.800 --> 01:33.100 Wenn es eine Turing-Maschine gibt, die auf der Eingabe stoppt und 01:33.100 --> 01:37.560 sagt, ob W Element der Sprache ist oder nicht. 01:38.320 --> 01:41.820 Aber sie stoppt in jedem Fall, auch wenn W nicht Element der Sprache 01:41.820 --> 01:42.180 ist. 01:43.180 --> 01:47.240 Wir sagen dann, die Turing-Maschine M entscheidet die Sprache L. 01:49.740 --> 01:52.620 Dann, das nächste ist Semi-Entscheidbarkeit. 01:53.740 --> 01:57.320 Eine Sprache, L ist semi-entscheidbar. 01:57.560 --> 02:02.200 Wenn es eine Turing-Maschine gibt, die auf der Eingabe W, wenn W 02:02.200 --> 02:05.640 Element der Sprache L ist, stoppt und sie akzeptiert. 02:06.600 --> 02:11.180 Und wenn W nicht Element der Sprache ist, dann ist es nicht definiert. 02:11.300 --> 02:13.860 Das heißt, wir wissen dann nicht das Verhalten der Turing-Maschine. 02:13.860 --> 02:17.680 In dem Fall sagen wir einfach nur, M akzeptiert die Sprache L. 02:20.340 --> 02:23.980 Und genau die Beziehung zwischen Entscheidbarkeit und Semi 02:23.980 --> 02:27.880 -Entscheidbarkeit, da hatten wir dann, eine Sprache, L ist genau dann 02:27.880 --> 02:34.200 entscheidbar, wenn L und deren Komplementsprache L, C semi 02:34.200 --> 02:35.080 -entscheidbar sind. 02:36.140 --> 02:39.540 Und diese Sätze brauchen wir auch für die Aufgabe 1 und 2. 02:41.780 --> 02:44.040 Und eine universelle Turing-Maschine. 02:44.640 --> 02:46.840 Wir haben ja Turing-Maschinen durchgerechnet. 02:47.140 --> 02:49.840 Ich glaube, ihr habt da relativ viele Beispiele gehabt. 02:50.680 --> 02:54.360 Manchen ging das dann schon zu weit. 02:54.560 --> 02:57.840 Das waren zu viele Turing-Maschinen. 02:58.960 --> 03:01.760 Das haben wir gemacht, damit ihr ein Gefühl dafür bekommt, weil jetzt 03:01.760 --> 03:05.060 wird es im Wesentlichen komplizierter, weil wir benutzen die Turing 03:05.060 --> 03:06.120 -Maschinen jetzt auch richtig. 03:07.180 --> 03:13.100 Und zwar, bisher hatten wir ja eine Turing-Maschine, oder hatten wir 03:13.100 --> 03:15.400 Turing -Maschinen kennengelernt für spezielle Aufgaben. 03:15.900 --> 03:19.760 Das heißt, die Turing-Maschine hat addiert, oder hat irgendwelche 03:19.760 --> 03:22.120 anderen Aufgaben gemacht, hat Einsen rausgelöscht, Nullen 03:22.120 --> 03:25.960 rausgelöscht, was auch immer, oder schreibt zwei Nullen am Ende der 03:25.960 --> 03:26.600 Eingabe. 03:27.600 --> 03:31.720 Und ja, unser intuitiver Wunsch ist, wir haben ja jetzt auch nicht ein 03:31.720 --> 03:34.520 Laptop, was eine Aufgabe erfüllt. 03:34.520 --> 03:36.420 Zum Beispiel addiert. 03:37.440 --> 03:39.580 Sondern unsere Rechner können ja mehr. 03:39.940 --> 03:43.700 Das heißt, wir haben Programme, die verschiedene Aufgaben auf dem PC 03:43.700 --> 03:44.520 realisieren. 03:45.200 --> 03:48.300 Und dieser intuitive Wunsch, den haben wir auch bei Turing-Maschinen. 03:48.980 --> 03:50.840 Das ist unsere universelle Turing-Maschine. 03:51.680 --> 03:57.640 Die Idee ist, wir haben einen programmierbaren Rechner, der als 03:57.640 --> 04:01.700 Eingabe ein Programm und die Eingabe für das Programm bekommt. 04:01.700 --> 04:05.200 So kann man sich eine universelle Turing-Maschine vorstellen. 04:07.020 --> 04:11.000 Wir geben eine Turing-Maschine rein, mithilfe von einer Gödel-Nummer 04:12.180 --> 04:15.940 und einer Eingabe für diese Turing-Maschine, die wir in die 04:15.940 --> 04:17.480 universelle Turing-Maschine geben. 04:19.300 --> 04:24.720 Die Turing-Maschine M ist hier beschrieben. 04:25.600 --> 04:28.440 Das heißt, wir haben wieder Zustände, wir haben Alphabet, wir haben 04:28.440 --> 04:31.340 Bandalphabet, wir haben eine Übergangsfunktion, wir haben Startzustand 04:31.340 --> 04:32.360 und wir haben Endzustände. 04:33.460 --> 04:40.280 Und für diese Turing-Maschine haben wir eine eindeutige Gödel-Nummer. 04:41.780 --> 04:48.880 Die Gödel-Nummer von M ist eine Kodierung der Turing-Maschine. 04:49.040 --> 04:52.840 Das ist eine eindeutige Kodierung, die wir in die universelle Turing 04:52.840 --> 04:56.040 -Maschine geben, damit die weiß, welche Turing-Maschine sie simulieren 04:56.040 --> 04:56.400 soll. 04:57.320 --> 05:01.380 Die Kodierung hatten wir in der Vorlesung wie folgt definiert. 05:01.440 --> 05:10.560 Wir haben eine Übergangsfunktion und die wird kodiert in der Folge. 05:10.720 --> 05:14.720 Das heißt, wir haben QI, wir befinden uns im Zustand QI. 05:15.660 --> 05:18.960 Das heißt, wir haben I0, dann haben wir ein Trennzeichen, das ist in 05:18.960 --> 05:19.900 dem Fall die 1. 05:20.540 --> 05:24.020 Dann haben wir das, was wir gerade lesen. 05:25.040 --> 05:27.400 Das müssen wir irgendwie kodieren. 05:27.640 --> 05:29.180 Und das sind gerade J0. 05:30.380 --> 05:33.620 Und dann gehen wir in den Zustand QR. 05:35.060 --> 05:37.400 Das heißt, wir haben ein Trennzeichen, wir haben R0. 05:42.160 --> 05:43.420 Dann geht es halt weiter. 05:43.560 --> 05:44.900 Wir haben immer wieder ein Trennzeichen. 05:45.420 --> 05:46.900 Und wir machen gleich noch ein Beispiel dafür. 05:48.320 --> 05:54.740 Die Kodierung sieht dann so aus, dass wir für alle möglichen 05:54.740 --> 05:55.900 Übergänge... 05:57.060 --> 05:58.520 Hierfür kriegen wir einen Code. 05:59.020 --> 06:00.600 Das ist beispielsweise Code 1. 06:01.360 --> 06:08.320 Und die Gödelnummer ist so repräsentiert, dass wir die Codes 06:08.320 --> 06:11.560 hintereinander schreiben und mit Trennzeichen zwei Einsen. 06:12.080 --> 06:15.140 Und die Gödelnummer beginnt immer mit drei Einsen und endet immer mit 06:15.140 --> 06:15.880 drei Einsen. 06:15.880 --> 06:20.000 Damit ihr dafür ein Gefühl bekommt, habe ich hier eine Turing 06:20.000 --> 06:20.380 -Maschine. 06:21.640 --> 06:22.760 Die macht irgendwas. 06:24.140 --> 06:26.320 Das ist im Moment nicht interessant für uns, was sie macht. 06:26.820 --> 06:28.020 Sie hat eine Zustandsmenge. 06:30.560 --> 06:33.380 Da müsste Q3 stehen. 06:39.200 --> 06:41.380 Wir haben die Übergangsfunktion. 06:42.060 --> 06:48.380 Und eure Aufgabe ist es jetzt, die Gödelnummer von M hinzuschreiben. 06:49.020 --> 06:52.240 Dafür habt ihr fünf Minuten Zeit, weil es benötigt ein bisschen Zeit. 06:55.300 --> 06:56.880 Dann machen wir mal weiter. 06:57.600 --> 06:58.940 Ich präsentiere jetzt mal die Lösung. 06:59.140 --> 07:01.340 Ich weiß jetzt nicht, ob ihr es geschafft habt oder nicht. 07:03.460 --> 07:07.260 Wir haben jetzt auch nicht so viel Zeit, weil die Evaluation auch ein 07:07.260 --> 07:08.280 bisschen Zeit einnimmt. 07:09.320 --> 07:11.040 Wie funktioniert das Ganze? 07:11.900 --> 07:13.700 Was ist die Gödelnummer von M? 07:14.900 --> 07:20.720 Wir kodieren uns erstmal das Bandalphabet. 07:21.940 --> 07:28.060 Das heißt, wir haben hier X1 repräsentiert die Null vom Bandalphabet. 07:28.320 --> 07:30.060 X2 entspricht dann der Eins. 07:30.460 --> 07:31.980 X3 den Blank. 07:34.120 --> 07:37.600 Und dann als nächstes kodieren wir uns noch die Richtung. 07:38.520 --> 07:40.360 Das heißt, die Eins ist unsere Richtung nach links. 07:41.020 --> 07:42.440 Die Zwei die Richtung nach rechts. 07:42.820 --> 07:46.100 Und die Drei, das heißt, wir bleiben an der Position. 07:48.220 --> 07:53.560 Das ist das, was wir vorhin in der Definition gesehen haben. 07:53.560 --> 07:59.960 Das heißt, wir müssen jetzt diesen Übergang irgendwie kodieren mit 07:59.960 --> 08:01.860 Nullen und Einsen. 08:02.800 --> 08:09.600 Die Zustände sind die Zustände Q0, Q1, Q2, QF. 08:10.280 --> 08:18.000 Im vorigen Beispiel war Q1, Q2, Q3 und QF das. 08:18.940 --> 08:20.160 Das kann passieren. 08:21.260 --> 08:24.020 Und was wir jetzt machen ist, wir haben den Zustand QI. 08:25.060 --> 08:29.480 Den repräsentieren wir mit I plus 1 Nullen. 08:30.220 --> 08:35.580 Wir haben das gelesene Zeichen, das repräsentieren wir mit J Nullen 08:35.580 --> 08:36.700 und so weiter. 08:38.920 --> 08:42.260 Die Frage ist jetzt, wie viele Einträge haben wir in der Tabelle? 08:43.120 --> 08:53.640 Ja, wir haben gerade 6 Einträge, weil wir haben N minus 1, also 3 mal 08:53.640 --> 08:58.900 der Anzahl des Bandalphabets. 09:01.160 --> 09:04.960 2 mal 3, also 6 Einträge. 09:07.960 --> 09:10.380 Und die müssen wir jetzt kodieren. 09:10.880 --> 09:12.780 Und dazu nutzen wir hier diese Regel. 09:14.420 --> 09:15.960 Und wie funktioniert das? 09:16.420 --> 09:18.960 Der erste Eintrag sieht wie folgt kodiert aus. 09:21.520 --> 09:27.320 Das heißt, wir haben den Zustand Q0 mit einer Null kodiert. 09:28.360 --> 09:33.560 Dann kommt das gelesene Zeichen, das haben wir auch mit einer Null 09:33.560 --> 09:34.080 kodiert. 09:34.080 --> 09:40.260 Dann als nächstes der aktuelle, also der neue Zustand. 09:40.580 --> 09:42.680 Den haben wir mit 4 kodiert. 09:43.980 --> 09:46.800 Das, was wir schreiben, mit einer Null kodiert. 09:47.120 --> 09:50.480 Und die Bewegungsrichtung mit 3 Nullen kodiert. 09:50.720 --> 09:52.080 Das sind gerade hier... 09:52.900 --> 09:55.240 Wir bewegen uns nicht. 09:55.620 --> 09:57.880 Das ist hier die 3. 09:58.180 --> 10:00.580 Das sind die 3 Nullen hier hinten. 10:02.560 --> 10:06.660 Wir schreiben auf dem Band eine Null. 10:08.300 --> 10:11.960 Die Null haben wir hier kodiert. 10:14.560 --> 10:18.680 Und der neue Zustand, der Zustand Q11. 10:19.700 --> 10:22.800 Und das sind gerade unsere K plus 1 Nullen. 10:22.980 --> 10:24.180 Das heißt in diesem Fall 4. 10:27.780 --> 10:29.900 Und das kann ich beliebig weitermachen. 10:29.900 --> 10:32.760 Man kriegt dann am Ende die Gödelnummer. 10:35.940 --> 10:39.340 Und die setzt sich dann, wie schon gesagt, aus den einzelnen 10:39.340 --> 10:40.420 Kodierungen zusammen. 10:43.160 --> 10:45.400 Das ist die Binärdarstellung. 10:49.140 --> 10:51.660 Das ist dann die natürliche Zahl dazu. 11:01.290 --> 11:05.950 Als nächstes die Definition von einer universellen Turing-Maschine. 11:08.630 --> 11:12.010 Eine Turing-Maschine M heißt universell. 11:12.490 --> 11:18.810 Falls für jede Einbahnturing-Maschine M und jede Eingabe gilt, dass M 11:18.810 --> 11:22.050 0 gestartet auf der Gödelnummer und der Eingabe X hält. 11:22.050 --> 11:27.570 Hält genau dann, wenn die eigentliche Turing-Maschine gestartet auf 11:27.570 --> 11:29.110 der gleichen Eingabe hält. 11:30.510 --> 11:32.310 Und wenn M gestartet mit X. 11:33.670 --> 11:37.470 Und andersrum, wenn die Turing-Maschine darauf nicht hält, dann hält 11:37.470 --> 11:39.750 natürlich auch die universelle Turing-Maschine darauf nicht. 11:42.600 --> 11:46.460 Und die Ausgabe ist natürlich dann auch die gleiche von der 11:46.460 --> 11:52.820 universellen Turing-Maschine, die M simuliert, auf der Eingabe X, wie 11:52.820 --> 11:54.800 M mit der Eingabe X. 11:57.320 --> 11:59.380 Und dazu hatten wir letztes Mal schon ein Bildchen. 12:00.020 --> 12:02.760 Wir haben die Turing-Maschine die zwei Zahlen addiert. 12:03.980 --> 12:04.800 X und Y. 12:05.920 --> 12:07.920 Die geben wir als Gödelnummer rein. 12:10.200 --> 12:16.420 Und für die Eingabe X gleich 5 und Y nach 5 erwarten wir jetzt, dass 12:16.420 --> 12:21.060 die universelle Turing-Maschine uns die Ausgabe 10 gibt. 12:22.360 --> 12:26.680 Und das ist die Funktionsweise von der universellen Turing-Maschine. 12:30.660 --> 12:35.140 Als nächstes hatten wir dann noch so ein bisschen den Satz von Reis 12:35.140 --> 12:36.120 motiviert. 12:39.160 --> 12:45.060 Die Idee war hier, wir haben Verifikationsprogramm M, geben die 12:45.060 --> 12:51.060 Gödelnummer in die universelle Turing-Maschine rein und geben als 12:51.060 --> 12:56.740 Eingabe ein beliebiges Programm M' rein und die Bedingung für die 12:56.740 --> 12:58.160 Korrektheit von M'. 12:58.880 --> 13:03.680 Und dann simuliert die universelle Turing-Maschine das 13:03.680 --> 13:09.180 Verifikationsprogramm M auf der Eingabe von M'. 13:09.180 --> 13:15.020 Und wenn das korrekt ist, dann erwartet man ein Ja und im anderen Fall 13:15.020 --> 13:15.700 dann Nein. 13:16.740 --> 13:22.340 Das Problem hier war, dass wenn wir M, also sich selbst, als Eingabe 13:22.340 --> 13:26.140 geben, dann müsste M seine eigene Korrektheit beweisen können. 13:26.820 --> 13:28.580 Und das ist irgendwie ein Widerspruch. 13:29.520 --> 13:31.760 Und die gleiche Idee ist auch beim Satz vom Reis. 13:33.920 --> 13:35.580 Nur allgemeiner noch gefasst. 13:37.620 --> 13:39.960 Genau, das war so der Gedanke, der Grundgedanke. 13:40.380 --> 13:42.520 Und jetzt kommen wir zu den eigentlichen Aufgaben. 13:43.740 --> 13:48.720 Und zwar Aufgabe 1 war bezüglich der Semi-Entscheidbarkeit. 13:49.720 --> 13:57.100 Und zwar solltet ihr zeigen, dass das Kompliment des Halteproblems 13:57.100 --> 13:58.560 nicht semi-entscheidbar ist. 13:59.420 --> 14:04.840 Die Idee dabei ist, wir haben mehrere Aussagen aus der Vorlesung. 14:05.820 --> 14:10.200 Wir haben erstmal gezeigt, dass das Halteproblem nicht entscheidbar 14:10.200 --> 14:10.560 ist. 14:12.060 --> 14:17.820 Und dann noch den Satz, den hat hier auch oben als Hinweis gegeben, 14:19.560 --> 14:25.300 dass L und LC, wenn L und LC semi-entscheidbar sind, oder L und LC 14:25.300 --> 14:28.780 sind genau dann semi-entscheidbar, wenn auch L entscheidbar ist. 14:29.380 --> 14:33.280 Und diese beiden Sachen nutzen wir jetzt für den Beweis aus. 14:33.280 --> 14:41.140 Wir zeigen jetzt im nächsten Schritt, dass HC nicht semi-entscheidbar 14:41.140 --> 14:41.580 ist. 14:42.620 --> 14:46.460 Und es gilt, 14:50.000 --> 14:51.460 dass H semi-entscheidbar ist. 14:53.160 --> 14:54.680 Also wir zeigen das nicht. 14:55.240 --> 14:56.740 H ist semi-entscheidbar. 14:57.740 --> 15:02.800 Dann konstruieren wir, dass die Annahme H semi-entscheidbar ist. 15:03.000 --> 15:12.020 Wir konstruieren eine universelle Turingmaschine M, die unsere 15:12.020 --> 15:15.620 Turingmaschine TW simuliert. 15:18.600 --> 15:26.640 Und M akzeptiert TW genau dann, sobald die Berechnung beendet wurde. 15:27.300 --> 15:30.220 Und im anderen Fall wissen wir halt nicht, was passiert. 15:30.360 --> 15:32.940 Das ist gerade die Idee von semi-entscheidbarkeit. 15:35.080 --> 15:39.120 Und da H allerdings nicht entscheidbar ist, und jetzt nutzen wir genau 15:39.120 --> 15:47.740 diesen Satz hier oben aus, aber das Kompliment von H semi-entscheidbar 15:47.740 --> 15:52.740 kann also HC nicht semi-entscheidbar sein, weil sonst wäre H 15:52.740 --> 15:53.500 entscheidbar. 15:59.680 --> 16:08.120 Das heißt, wenn H und HC semi-entscheidbar wären, dann wäre auch H 16:08.120 --> 16:08.960 entscheidbar. 16:08.960 --> 16:10.220 Und das geht halt nicht. 16:10.320 --> 16:13.300 Wir haben in der Vorlesung gezeigt, dass H nicht entscheidbar ist. 16:14.880 --> 16:20.540 Und damit ist die Aufgabe quasi gezeigt. 16:28.720 --> 16:31.060 Dann zur nächsten Aufgabe. 16:31.760 --> 16:36.320 Da solltet ihr zeigen, dass das Kompliment der Diagonalsprache semi 16:36.320 --> 16:37.180 -entscheidbar ist. 16:39.860 --> 16:42.880 Auch hier hatten wir wieder Aussagen aus der Vorlesung. 16:44.540 --> 16:47.000 Die Diagonalsprache erstmal ist definiert. 16:48.040 --> 16:51.320 Wir haben Wi unter der Bedingung, dass die Turing-Maschine Mi 16:51.320 --> 16:53.880 akzeptiert das Wi nicht. 16:54.660 --> 16:55.920 Das war gerade die Aussage. 16:56.020 --> 16:59.680 Das heißt, wir haben als Eingabe die Gödelnummer von Mi. 16:59.900 --> 17:01.200 Das ist gerade dieses Wi. 17:01.720 --> 17:04.980 Und Mi akzeptiert seine eigene Gödelnummer nicht. 17:05.980 --> 17:11.200 Das heißt, die Diagonalsprache ist nicht entscheidbar. 17:12.060 --> 17:14.440 Auch das haben wir in der Vorlesung gezeigt. 17:15.900 --> 17:21.800 Und jetzt die Sprache, die Komplimentsprache der Diagonalsprache ist 17:21.800 --> 17:27.880 definiert unter Mi akzeptiert Wi. 17:29.440 --> 17:31.700 Also gerade das Kompliment von hier oben. 17:34.060 --> 17:36.980 Also Wi unter der Bedingung Mi akzeptiert Wi. 17:38.460 --> 17:41.860 Das ist das Kompliment der Diagonalsprache. 17:43.260 --> 17:45.860 Und auch hier verwenden wir wieder eine universelle Turing-Maschine 17:45.860 --> 17:54.940 mit der Eingabe Mi, also die Gödelnummer von Mi und der Eingabe V. 17:57.100 --> 18:05.920 Mi akzeptiert die Eingabe genau dann, wenn auch die universelle Turing 18:05.920 --> 18:07.860 -Maschine die Eingabe akzeptiert. 18:08.880 --> 18:15.580 Und Semi-Entscheidbarkeit bedeutet ja wiederum, dass wenn Mi die 18:15.580 --> 18:20.920 Eingabe nicht akzeptiert, dann akzeptiert auch die universelle Turing 18:20.920 --> 18:22.120 -Maschine die Eingabe nicht. 18:22.120 --> 18:26.840 Allerdings wissen wir nicht, ob die Turing-Maschine stoppt oder nicht. 18:28.160 --> 18:30.180 Und das reicht in diesem Fall auszuzeigen. 18:30.960 --> 18:32.340 Und auch hier sind wir dann fertig. 18:40.580 --> 18:43.640 Das war jetzt zu Semi-Entscheidbarkeit die Aufgaben. 18:45.600 --> 18:47.460 Kommen wir zur Aufgabe 2. 18:48.740 --> 18:53.160 Da ging es um Abgeschlossenheit von entscheidbaren Sprachen. 18:54.080 --> 19:00.620 Die erste Aufgabe hieß, ihr solltet zeigen, dass die Menge der 19:00.620 --> 19:04.440 entscheidbaren Sprachen unter dem klinischen Abschluss abgeschlossen 19:04.440 --> 19:04.820 ist. 19:04.820 --> 19:14.520 Das heißt, wie für jede Sprache L gilt auch, dass der klinische 19:14.520 --> 19:16.400 Abschluss von L entscheidbar ist. 19:22.660 --> 19:32.160 Die Idee dazu ist, wenn L entscheidbar ist, dann gibt es auch eine 19:32.160 --> 19:34.980 Turing -Maschine M, die L entscheidet. 19:36.020 --> 19:39.420 Das heißt, wir haben hier die Notation L von M ist gleich L. 19:39.420 --> 19:43.620 Das heißt, die Turing-Maschine M entscheidet L. 19:46.480 --> 19:51.100 Als nächstes konstruieren wir uns eine nicht-deterministische Turing 19:51.100 --> 19:52.980 -Maschine M'. 19:53.920 --> 19:58.860 Und das Verfahren funktioniert wie folgt. 19:59.220 --> 20:01.000 Wir haben eine Eingabe X. 20:02.200 --> 20:08.680 Und die nicht-deterministische Turing-Maschine wählt ein nicht-leeres 20:08.680 --> 20:09.320 Präfix. 20:09.620 --> 20:13.400 Das nennen wir hier in diesem Fall Pi von der Eingabe X. 20:14.360 --> 20:21.580 Und wir überprüfen mithilfe der Turing-Maschine M, also die gerade die 20:21.580 --> 20:27.460 Sprache entscheidet, ob der Präfix in der Sprache L liegt. 20:29.320 --> 20:31.000 Und es gibt da wieder zwei Fälle. 20:32.080 --> 20:34.080 Entweder Pi liegt in der Sprache. 20:34.760 --> 20:38.240 Dann heißt es, M akzeptiert X nicht. 20:40.280 --> 20:43.420 Quatsch, Pi liegt nicht in der Sprache. 20:43.560 --> 20:44.960 Das heißt, M akzeptiert X nicht. 20:45.320 --> 20:47.140 Und der andere Fall ist genau das Gegenteil. 20:47.540 --> 20:48.780 Pi liegt in der Sprache. 20:49.660 --> 20:51.580 Und M löscht Pi vom Band. 20:52.360 --> 20:55.740 Und falls das Band dann leer ist, dann akzeptiert es die Eingabe. 20:55.740 --> 20:59.120 Im anderen Fall springen wir wieder hier nach oben, wählen uns das 20:59.120 --> 21:06.920 nächste nicht-leere Präfix und überprüfen dann wieder mit M, ob der 21:06.920 --> 21:08.360 Präfix in der Sprache liegt. 21:08.880 --> 21:12.740 Entweder es liegt nicht in der Sprache oder es liegt in der Sprache. 21:13.000 --> 21:19.080 Und je nachdem entscheidet dann M wieder, ob es akzeptiert oder nicht. 21:20.500 --> 21:21.340 Genau. 21:30.360 --> 21:31.040 Okay. 21:32.900 --> 21:35.740 Dann kommen wir zur nächsten Aufgabe. 21:39.120 --> 21:43.200 Die Aufgabe war, dass ihr zeigen solltet, dass die Menge der 21:43.200 --> 21:48.660 entscheidbaren Sprachen bezüglich der Operation MIN abgeschlossen ist. 21:50.060 --> 21:52.340 MIN haben wir wie folgt definiert. 21:53.680 --> 21:55.400 X ist Element der Sprache. 21:56.240 --> 22:01.800 Unter der Bedingung, dass kein echtes Präfix von X in L liegt. 22:05.160 --> 22:08.900 Und ein Präfix heißt echt, wenn es nicht X ist. 22:08.980 --> 22:10.760 Das hatten wir noch als Hinweis dazu geschrieben. 22:11.760 --> 22:12.560 Und das ist auch wichtig. 22:17.390 --> 22:19.010 Wie gehen wir da vor? 22:19.010 --> 22:29.550 Der erste Schritt ist, die Turing-Maschine TL entscheidet die Sprache 22:29.550 --> 22:29.870 L. 22:31.410 --> 22:36.170 Und wir haben eine Turing-Maschine T', die generiert uns alle echten 22:36.170 --> 22:38.970 Präfixe der Eingabe. 22:40.250 --> 22:41.690 Ohne Wiederholung. 22:43.050 --> 22:47.590 Und wir konstruieren uns eine nicht deterministische Turing-Maschine 22:47.590 --> 22:48.650 wieder im Strich. 22:49.470 --> 22:50.390 Der nächste Schritt. 22:51.050 --> 22:56.470 Und die Arbeitsweise der Turing-Maschine T, die gerade die Sprache, 22:57.150 --> 23:02.830 die MIN L entscheidet, auf der Eingabe X funktioniert wie folgt. 23:03.550 --> 23:04.610 Wir haben den ersten Schritt. 23:05.150 --> 23:08.990 Wir gucken, ob X in der Sprache ist. 23:09.990 --> 23:11.830 Das heißt TL entscheidet X. 23:12.450 --> 23:18.690 Und wenn TL nicht akzeptiert, dann liegt dieses X nicht in der 23:18.690 --> 23:19.230 Sprache. 23:19.990 --> 23:24.510 Und T hält an und akzeptiert damit dann auch nicht. 23:25.030 --> 23:28.950 Weil die initiale Eingabe ist nicht Element der Sprache. 23:29.750 --> 23:34.330 Im nächsten Schritt generieren wir uns das nächste echte Präfix. 23:34.790 --> 23:38.210 Das nennen wir in diesem Fall P. Von der Eingabe X. 23:39.490 --> 23:47.170 Und wenn es keine weiteren Präfixe gibt, also wenn T Strich nichts 23:47.170 --> 23:54.570 mehr generieren kann, dann akzeptiert unsere Turing-Maschine T die 23:54.570 --> 23:55.030 Eingabe. 23:55.830 --> 24:02.370 Und im nächsten Fall, wenn es einen Präfix gibt, dann entscheidet 24:02.370 --> 24:06.550 wieder TL, ob P in der Sprache liegt oder nicht. 24:07.550 --> 24:11.570 Jetzt gibt es die Fälle, dass P Element der Sprache ist. 24:12.510 --> 24:16.490 Dann ist gerade das hier verletzt. 24:16.590 --> 24:19.730 Das heißt, dann hält T und akzeptiert nicht. 24:20.630 --> 24:24.870 Und im anderen Fall gehen wir wieder zurück zu wir generieren uns das 24:24.870 --> 24:26.230 nächste echte Präfix. 24:27.010 --> 24:32.150 Und das machen wir dann wieder so lange, bis wir kein weiteres Präfix 24:32.150 --> 24:32.790 mehr finden. 24:33.510 --> 24:37.410 Und in dem Fall akzeptieren wir dann die Eingabe. 24:40.760 --> 24:47.620 Das ist die wesentliche Arbeitsweise der Turing-Maschine T. 24:48.260 --> 24:54.660 Und die Idee, wie man zeigt, dass die Menge der entscheidenden 24:54.660 --> 24:57.820 Sprachen unter der Operation MIN abgeschlossen ist. 25:00.460 --> 25:06.300 Jetzt kommen wir dazu, dass ihr ein bisschen aktiv werdet. 25:06.300 --> 25:11.480 Wir hatten einige Sachen nicht mit auf dem Übungsblatt, weil es 25:11.480 --> 25:12.480 Aufgaben gab. 25:12.740 --> 25:15.880 Die benutzen wir halt ganz gerne für ein Übungsblatt, aber die wurden 25:15.880 --> 25:17.840 schon in einigen Tutorien besprochen. 25:19.620 --> 25:23.060 Und damit aber der ein oder andere hier keinen Nachteil hat, haben wir 25:23.060 --> 25:24.500 sie jetzt hier mit reingenommen. 25:25.640 --> 25:28.960 Und zwar sollt ihr jetzt zeigen, dass die Menge der semi 25:28.960 --> 25:32.580 -entscheidbaren Sprachen unter Vereinigung und Schnitt abgeschlossen 25:32.580 --> 25:32.960 sind. 25:33.880 --> 25:35.920 Dafür gebe ich euch mal drei Minuten. 25:41.330 --> 25:47.790 Was man erst zeigt, ist, dass die unter der Vereinigung abgeschlossen 25:47.790 --> 25:48.270 sind. 25:50.870 --> 25:55.310 Man hat zwei Turing-Maschinen, M1 und M2. 25:55.310 --> 26:04.010 Die eine, also M1, ist die Turing-Maschine, die L1 akzeptiert. 26:05.050 --> 26:11.310 Und die zweite Turing-Maschine ist die, die die Sprache L2 akzeptiert. 26:12.730 --> 26:22.010 Und man verwendet eine Zwei-Band-Turing-Maschine M' mit zwei Köpfen 26:22.010 --> 26:28.730 und simuliert einmal M1 auf Band 1 und M2 auf Band 2. 26:30.550 --> 26:37.470 Und was man jetzt macht, sobald M1 auf Band 1 akzeptiert, akzeptiert 26:37.470 --> 26:38.490 man die Eingabe. 26:39.230 --> 26:47.210 Und wenn das nicht der Fall ist, dann guckt man halt, sobald M2 auf 26:47.210 --> 26:52.150 Band 2 akzeptiert, also wenn eins von den beiden akzeptiert, dann 26:52.150 --> 26:53.510 akzeptiert man die Eingabe. 26:53.770 --> 26:54.510 Das ist die Idee. 26:55.430 --> 27:00.310 Und damit zeigt man, dass gerade die Vereinigung abgeschlossen ist. 27:02.530 --> 27:07.090 Das heißt M' akzeptiert L1 vereinigt L2. 27:08.190 --> 27:09.710 Vereinigung ist semi-entscheidbar. 27:11.150 --> 27:14.930 In anderen Fällen wissen wir halt nicht, wenn beide nicht akzeptieren, 27:15.050 --> 27:17.550 dann kann es passieren, dass die beiden nicht halten. 27:21.210 --> 27:25.670 Dann gucken wir uns als nächstes, ob der Schnitt abgeschlossen ist. 27:26.850 --> 27:31.350 Und der Gedanke ist im Wesentlichen der gleiche. 27:31.370 --> 27:34.210 Wir haben wieder zwei Turing-Maschinen M1 und M2. 27:34.810 --> 27:41.910 Wir simulieren die Turing-Maschine M1 auf Band 1 und M2 auf Band 2. 27:42.910 --> 27:51.190 Und sobald M1 auf Band 1 akzeptiert und in diesem Fall müssen auch M2 27:51.190 --> 27:55.610 auf Band 2 akzeptieren, erst dann dürfen wir die Eingabe akzeptieren. 27:56.420 --> 28:09.270 Damit sind wir auch fertig und haben gezeigt, dass die Vereinigung und 28:09.270 --> 28:12.350 der Schnitt abgeschlossen sind unter der Menge der semi-entscheidbaren 28:12.350 --> 28:12.660 Sprachen. 28:23.750 --> 28:27.350 Dann zu der Frage bezüglich der Codierung der Gödel-Nummer. 28:28.070 --> 28:31.150 Wir haben uns das jetzt nochmal überlegt. 28:31.670 --> 28:34.370 Und zwar gibt es zwei Möglichkeiten. 28:34.910 --> 28:37.310 Die erste Möglichkeit, man codiert das noch mit rein. 28:38.330 --> 28:42.270 Das wäre intuitiv, wahrscheinlich die intuitivste. 28:43.170 --> 28:45.190 Das haben wir jetzt hier nicht gemacht. 28:45.510 --> 28:48.410 Man kann natürlich auch sagen, die universelle Turing-Maschine muss 28:48.410 --> 28:52.390 nicht wissen, ob das ein akzeptierender oder nicht akzeptierender 28:52.390 --> 28:53.230 Zustand ist. 28:54.750 --> 29:00.190 Und gibt dann einfach nur aus, in welchem Zustand sie gehalten hat. 29:00.370 --> 29:05.930 In dem Fall war es akzeptierende U2, glaube ich. 29:07.070 --> 29:09.970 Und dann entscheidet man im Nachhinein, ob das ein akzeptierender 29:09.970 --> 29:11.790 Zustand war oder ein Fehlzustand. 29:16.550 --> 29:17.810 Beantwortet das die Frage? 29:37.280 --> 29:43.000 Gut, dann habe ich noch eine Aufgabe für euch. 29:43.860 --> 29:51.140 Und zwar die Menge der semi-entscheidbaren Sprachen, dass die unter 29:51.140 --> 29:53.720 der Komplementbildung nicht abgeschlossen ist. 29:54.720 --> 29:55.820 Das solltet ihr jetzt zeigen. 29:57.160 --> 30:00.680 Und dafür gebe ich euch etwa drei Minuten, vielleicht auch ein 30:00.680 --> 30:03.300 bisschen weniger, weil die Zeit uns jetzt langsam auch wegrennt. 30:04.360 --> 30:08.240 Was wir verwenden, wir verwenden die universelle Sprache. 30:10.620 --> 30:15.920 Wir haben die Aussagen aus der Vorlesung, dass die universelle Sprache 30:15.920 --> 30:18.440 LU -semi-entscheidbar ist. 30:20.340 --> 30:23.780 Und dass LU-nicht-entscheidbar ist. 30:24.940 --> 30:29.960 Das ist im Wesentlichen das gleiche Argument, glaube ich sogar. 30:32.740 --> 30:34.960 Und genau, für eine Sprache... 30:43.880 --> 30:47.040 Genau, das ist eigentlich H genau das gleiche Argument. 30:47.940 --> 30:50.180 Das ist wie in 1B, genau. 30:50.380 --> 30:53.360 Und dann zeige ich, genau, das ist komplett richtig. 30:53.580 --> 30:55.500 Jetzt habe ich es auch ein bisschen nachverzogen. 30:56.620 --> 30:59.940 Dauert hier vorne ein bisschen länger, als wenn man es auf dem Blatt 30:59.940 --> 31:00.560 Papier sieht. 31:00.560 --> 31:04.560 Also entschuldigt, wenn es nicht gleich... 31:05.500 --> 31:07.340 Genau, das ist genau das gleiche Argument. 31:07.480 --> 31:11.460 Man nimmt dann halt, wie bei der Diagonalsprache, ok, sagt man, LU-C 31:11.460 --> 31:12.640 ist semi-entscheidbar. 31:13.880 --> 31:17.640 Das heißt, man nutzt wieder den Satz aus und zeigt damit den 31:17.640 --> 31:19.880 Widerspruch, dass LU-nicht-entscheidbar ist. 31:20.920 --> 31:26.540 Dass wenn LU-C, also die Komplement von LU, semi-entscheidbar wäre und 31:26.540 --> 31:30.640 LU -semi-entscheidbar ist, naja, dann müsste LU-entscheidbar sein, ist 31:30.640 --> 31:32.160 es aber nicht, das haben wir ja gezeigt. 31:32.340 --> 31:40.000 Und damit ist auch, genau, damit haben wir gezeigt, dass LU-C nicht 31:40.000 --> 31:41.180 semi -entscheidbar ist. 31:44.340 --> 31:49.660 Genau, das ist gerade hier nochmal der Satz, den wir ausnutzen aus der 31:49.660 --> 31:50.300 Vorlesung. 31:58.540 --> 32:03.520 Genau, und jetzt, gut, das nächste mache ich mal aus Zeitgründen 32:03.520 --> 32:04.880 gleich selbst. 32:04.880 --> 32:06.800 Aber ihr könnt euch das gerne wieder überlegen. 32:08.960 --> 32:11.060 Oder ne, ich gebe euch einfach mal die drei Minuten. 32:11.560 --> 32:14.380 Die Menge der entscheidbaren Sprachen, also ihr sollt zeigen, dass die 32:14.380 --> 32:17.440 Menge der entscheidbaren Sprachen unter Vereinigung und Schnitt 32:17.440 --> 32:18.420 abgeschlossen ist. 32:20.980 --> 32:28.700 So, welche Ideen nutzen wir, um zu zeigen, dass das für Vereinigung 32:28.700 --> 32:29.000 gilt? 32:31.580 --> 32:33.580 Also wir hatten schon mal so eine ähnliche Idee. 32:34.960 --> 32:35.860 Einen Tipp kann ich geben. 32:50.780 --> 32:57.440 Naja, wir nehmen wieder eine Turingmaschine M1, die L1 entscheidet und 32:57.440 --> 32:59.920 eine Turingmaschine M2, die L2 entscheidet. 33:00.940 --> 33:02.780 Was wir machen, haben wir schon gemacht. 33:03.980 --> 33:05.640 Wir nehmen wieder eine 2-Band-Turingmaschine. 33:06.660 --> 33:10.200 Auf dem einen Band wird M1 simuliert, auf dem zweiten Band M2. 33:10.200 --> 33:13.640 Und dann wieder die gleiche Aussage. 33:13.760 --> 33:16.120 Interessant wird es dann für den Schnitt. 33:20.920 --> 33:27.280 Und zwar für den Schnitt verwenden wir das Gesetz von De Morgan. 33:29.400 --> 33:36.640 Und wir hatten den Tipp gegeben, oder ich hatte den Tipp gegeben, dass 33:36.640 --> 33:39.040 unter Komplementbildung es abgeschlossen ist. 33:39.740 --> 33:44.600 Das heißt, was wir jetzt hier sagen, die Sprache L1 repräsentiert 33:44.600 --> 33:50.300 unser A hier oben und die Sprache L2 gerade das B. 33:52.760 --> 34:00.620 Und dann gilt natürlich, nicht A ist die Komplementsprache von L1 und 34:00.620 --> 34:04.680 nicht B ist die Komplementsprache von L2. 34:04.680 --> 34:06.720 Also Komplement von L2. 34:09.120 --> 34:13.440 Und was man dann eigentlich nur noch macht, ist einsetzen. 34:14.100 --> 34:22.880 Und was wir wissen ist, aus dem ersten, wir haben ja gezeigt, dass die 34:22.880 --> 34:24.280 Vereinigung abgeschlossen ist. 34:24.860 --> 34:26.860 Und für die Vereinigung wissen wir das schon. 34:28.020 --> 34:32.260 Und durch den Hinweis und den ersten Schritt wissen wir, dass das 34:32.260 --> 34:32.680 gilt. 34:32.680 --> 34:45.000 Und damit wissen wir auch im Wesentlichen, dass das L1 geschnitten L2, 34:45.140 --> 34:47.560 das Komplement davon ist, entscheidbar. 34:48.080 --> 34:55.820 Und auch das Komplement vom Komplement ist gerade L1 geschnitten L2 34:55.820 --> 34:57.720 und auch das ist dann entscheidbar. 34:58.720 --> 35:02.760 Und dafür nutzen wir dann auch den Hinweis aus. 35:07.910 --> 35:10.130 Gut, das war es zur Aufgabe 2. 35:10.550 --> 35:14.930 Da habt ihr jetzt nochmal ein paar Aufgaben gesehen, wie die 35:14.930 --> 35:17.150 funktionieren, was die Ideen sind. 35:19.030 --> 35:22.070 Und wir kommen dann zur Aufgabe 3. 35:23.250 --> 35:25.090 Da geht es um Nichtentscheidbarkeit. 35:26.090 --> 35:35.750 Und man sollte zeigen, dass die Menge D nicht entscheidbar ist, wobei 35:35.750 --> 35:48.490 D definiert ist als W, wobei W Element 0,1 Stern ist und unter der 35:48.490 --> 35:54.230 Bedingung, dass die Turing-Maschine T, W hält auf keiner Eingabe. 35:56.450 --> 36:05.070 Und da nutzt man das alte Problem oder verwendet das alte Problem. 36:06.390 --> 36:12.410 Das heißt, wenn D entscheidbar wäre, dann wäre auch das alte Problem 36:12.410 --> 36:13.130 entscheidbar. 36:16.110 --> 36:20.030 Also das ist die Idee für den Beweis. 36:21.610 --> 36:29.070 Und die Annahme ist, dass TD eine Turing-Maschine ist, die D 36:29.070 --> 36:29.710 entscheidet. 36:32.530 --> 36:36.970 Und TD akzeptiert die Eingabe. 36:37.930 --> 36:45.150 Das bedeutet dann auch, T, W hält auf keiner Eingabe und akzeptiert in 36:45.150 --> 36:46.870 allen anderen Fällen nicht. 36:49.210 --> 36:54.110 Und das alte Problem könnte dann auch wie folgt entschieden werden. 36:55.110 --> 37:01.090 Wir benutzen eine universelle Turing-Maschine wieder, die nennen wir 37:01.090 --> 37:08.310 TU, mit der Eingabe der Gödel-Nummer von TD und einer Eingabe V. 37:09.230 --> 37:14.710 Und wenn die universelle Turing-Maschine die Eingabe akzeptiert mit 37:14.710 --> 37:21.770 der Gödel-Nummer von TD und V, dann gibt sie halt nicht akzeptieren 37:21.770 --> 37:22.210 aus. 37:23.100 --> 37:29.050 Und wenn TU die Eingabe nicht akzeptiert, dann gibt akzeptiere aus. 37:38.420 --> 37:49.360 Das heißt, TD, die Turing-Maschine, zu Menge D akzeptiert, wenn TW auf 37:49.360 --> 37:50.460 keine Eingabe hält. 37:51.420 --> 37:56.360 Und in allen anderen Fällen akzeptiert sie nicht. 37:57.980 --> 38:02.560 Und wir verwenden dann wieder eine universelle Turing-Maschine, TU, 38:02.820 --> 38:06.980 mit der Eingabe der Gödel-Nummer von TD und der Eingabe V. 38:07.640 --> 38:13.820 Und wenn die universelle Turing-Maschine die Eingabe akzeptiert, dann 38:13.820 --> 38:15.780 sollte sie nicht akzeptieren ausgeben. 38:15.780 --> 38:22.540 Und in allen anderen Fällen akzeptiert sie die Ausgabe. 38:24.320 --> 38:34.800 Und damit ist die Menge D nicht entscheidbar. 38:41.680 --> 38:42.700 Okay. 38:44.160 --> 38:50.400 Dann kommen wir auch schon zu Aufgaben, zu Komplexitätsklassen. 38:53.280 --> 38:59.740 Und zwar hieß es in der Aufgabe 4, das Entscheidungsproblem, ob eine 38:59.740 --> 39:08.160 gegebene Zahl eine Potenz von 2 ist, ist durch das Problembeispiel und 39:08.160 --> 39:10.560 die Ja-Beispiele gegeben. 39:11.560 --> 39:19.240 Nun haben wir ein Codierungsschemata Sb, das heißt, seien Sb die 39:19.240 --> 39:25.420 Codierungsschemata, die natürliche Zahlen auf ihre B, ihre 39:25.420 --> 39:27.460 Repräsentation abbilden. 39:27.460 --> 39:31.980 Also hier sieht sich dieses B. 39:32.920 --> 39:39.720 Betrachten Sie nun L mit dem Entscheidungsproblem und den 39:39.720 --> 39:47.220 Codierungsschemata mit dem unnäheren Codierungsschemata und einmal mit 39:47.220 --> 39:53.600 dem binären Codierungsschemata Und beschreiben Sie für jede der beiden 39:53.600 --> 39:56.740 Sprachen kurz die Arbeitsweise einer deterministischen Turing 39:56.740 --> 40:01.040 -Maschine, die sie entscheidet und geben Sie ihre Laufzeit 40:01.040 --> 40:02.080 asymptotisch an. 40:02.980 --> 40:05.700 Sind die Sprachen in P oder sind sie in NP? 40:06.920 --> 40:12.440 Also sind die Sprachen in P, die eine Frage, und die nächste Frage, 40:12.560 --> 40:13.300 sind sie in NP? 40:14.260 --> 40:14.960 Nächste Frage. 40:17.280 --> 40:21.480 So, was wir erstmal betrachten, wir betrachten uns das mit dem 40:21.480 --> 40:28.480 Codierungsschema, mit dem binären Codierungsschema zum Problem und 40:28.480 --> 40:35.100 eine Konvention, die wir uns festlegen, ist, es gibt keine führenden 40:35.100 --> 40:38.280 Nullen, außer die Eingabe ist Null. 40:39.800 --> 40:49.040 Und die Beobachtung ist, dass die Zweierpotenz bei binärer Darstellung 40:49.040 --> 40:54.600 im Wesentlichen so aussieht, das weiß, glaube ich, jeder von euch. 40:55.160 --> 40:58.500 Und was man dann überprüft, ist, ob die Eingabe Null ist. 41:00.960 --> 41:05.300 Und falls das der Fall ist, dann stoppe die Berechnung und lehne die 41:05.300 --> 41:06.000 Eingabe ab. 41:06.000 --> 41:14.960 Und in allen anderen Fällen gucken wir schrittweise nach rechts, man 41:14.960 --> 41:18.560 guckt sich dann erstmal die erste Zahl an, wenn es eine Null ist, dann 41:18.560 --> 41:23.160 ist die Eingabe Null und wir brechen die Berechnung ab und lehnen die 41:23.160 --> 41:23.940 Eingabe ab. 41:23.940 --> 41:27.540 Wenn wir eine Eins lesen, dann müssen wir halt noch rechts gucken, ob 41:27.540 --> 41:29.520 es weitere Einsen gibt. 41:31.300 --> 41:36.720 Und wenn wir am Ende gelangen und lesen keine weitere Eins bzw. 41:37.880 --> 41:44.520 wenn noch eine Eins vorkommt, dann lehnen wir ab und beenden die 41:44.520 --> 41:48.200 Berechnung und sonst akzeptieren wir die Eingabe. 41:53.060 --> 41:56.260 Die Zeitkomplexität der Turing-Maschine ist linear in der 41:56.260 --> 41:57.140 Eingabegröße. 41:58.080 --> 42:03.720 Das heißt, für das erste Codierungsschema liegen wir in P. 42:07.470 --> 42:10.110 Und liegen wir damit auch in NP? 42:15.090 --> 42:16.050 Okay, ich sehe nicken. 42:17.950 --> 42:23.390 Für das zweite, das war das unnähere Codierungsschema. 42:28.350 --> 42:32.790 Eine Turing-Maschine, die das entscheidet, konstruieren wir uns wie 42:32.790 --> 42:33.290 folgt. 42:34.890 --> 42:39.250 Wir durchlaufen immer wieder die Eingabe und bei jedem Durchlauf 42:39.250 --> 42:46.910 merken wir uns, ob wir gerade sind oder ob wir ungerade sind im 42:46.910 --> 42:47.930 aktuellen Zeitpunkt. 42:49.110 --> 42:51.250 Also ungerade viele Einsen meine ich damit. 42:53.690 --> 42:55.730 Also nochmal zur Wiederholung. 42:56.210 --> 42:59.170 Jeden Durchlauf merken wir uns, ob wir gerade oder ungerade viele 42:59.170 --> 43:01.750 Einsen gelesen haben auf dem Band. 43:02.830 --> 43:12.190 Und eine Möglichkeit ist, bei jedem Durchlauf ersetzen wir uns jede 43:12.190 --> 43:13.470 zweite Eins durch eine Null. 43:15.930 --> 43:27.970 Und wenn wir am Ende ein Ungerade rausbekommen, dann lehnen wir ab und 43:27.970 --> 43:29.590 beenden die Berechnung. 43:30.730 --> 43:36.170 Und ansonsten, falls wir am Ende eine Eins sehen, bleiben wir stehen 43:36.170 --> 43:38.110 und akzeptieren die Eingabe. 43:39.210 --> 43:44.690 Und auch hier ist die Zeitkomplexität der Turing-Maschine quadratisch 43:44.690 --> 43:46.450 in der Eingabegröße. 43:57.370 --> 44:05.310 Und jetzt ist die Frage, liegt das Problem in P oder in NP? 44:08.960 --> 44:10.720 Die Frage ist an euch gerichtet. 44:10.900 --> 44:11.600 Liegt sie in P? 44:20.220 --> 44:23.400 Sie liegt in P und damit liegt sie auch in NP. 44:27.210 --> 44:31.190 Jetzt kommen wir zur für mich interessantesten Aufgabe. 44:31.710 --> 44:35.410 Das ist zwar nur die Zusatzaufgabe, aber sie ist im Wesentlichen 44:35.410 --> 44:36.410 spannend. 44:37.890 --> 44:38.870 Zumindest finde ich das. 44:39.950 --> 44:45.770 Und da solltet ihr einmal definieren, wie ist PSPACE definiert und wie 44:45.770 --> 44:47.210 ist X-Time definiert. 44:48.370 --> 44:51.650 Und schön wäre es halt gewesen, wenn ihr das in eigenen Worten 44:51.650 --> 44:53.150 formuliert. 44:54.410 --> 44:59.210 Und die Idee war dabei nicht, den Wikipedia-Artikel rauszukopieren, 44:59.350 --> 45:02.030 sondern ihr solltet halt schon verstehen, was bedeutet das. 45:03.330 --> 45:08.770 Und beim nächsten hatten wir eine gewisse Anzahl von Klassen gegeben. 45:08.770 --> 45:17.810 Das war einmal NLP, NP, PSPACE, NP-SPACE, EXP und EXP-SPACE. 45:18.670 --> 45:21.130 Und ihr solltet die ein bisschen zuordnen, d.h. 45:21.790 --> 45:28.270 die Beziehungen zwischen den einzelnen Klassen miteinander in einem 45:28.270 --> 45:33.430 geeigneten Diagramm, in einer geeigneten Grafik wieder aufs Blatt 45:33.430 --> 45:33.990 Papier bringen. 45:34.730 --> 45:44.270 Und als nächstes solltet ihr sagen, was für heutige Computer eine 45:44.270 --> 45:52.530 sinnvolle Rechenzeit gibt. 45:53.530 --> 45:56.990 Das war keine sinnvolle Rechenzeit. 46:00.450 --> 46:08.990 Probleme, die von heutigen Computern in nicht akzeptabler Rechenzeit 46:08.990 --> 46:11.390 oder Speicherplatz lösbar sind. 46:11.390 --> 46:12.610 Da gibt es einige. 46:15.590 --> 46:17.910 Und ich habe für euch ein bekanntes rausgepickt. 46:18.770 --> 46:25.450 Und als nächstes, damit beschäftigen sich viele, was passiert, wenn P 46:25.450 --> 46:26.490 gleich NP ist. 46:27.270 --> 46:33.430 Und gerade wenn ihr in den Bereich Kryptografie geht, wird es dann 46:33.430 --> 46:33.990 spannend. 46:34.870 --> 46:37.590 Aber auch in anderen Bereichen ist es natürlich eine spannende Frage, 46:37.710 --> 46:39.650 was passiert, wenn P gleich NP ist. 46:40.230 --> 46:46.210 Aber vielleicht beeinflusst das die Kryptografie am negativsten, 46:47.010 --> 46:48.410 könnte man sagen. 46:52.450 --> 46:54.010 Fangen wir mit dem ersten an. 46:54.130 --> 46:58.990 Definieren Sie PSPACE und EXP bzw. 46:59.270 --> 46:59.910 EXPTIME. 47:01.010 --> 47:03.450 Weiß ich jetzt gar nicht, was wir draufgeschrieben haben. 47:03.930 --> 47:06.410 Also EXP ist das gleiche wie EXPTIME. 47:07.950 --> 47:12.190 Und PSPACE ist gerade die Klasse der Entscheidungsprobleme, die von 47:12.190 --> 47:15.970 einer depterministischen Turingmaschine in polynomial vier Platz 47:15.970 --> 47:17.050 gelöst werden kann. 47:18.170 --> 47:22.270 Und dazu hättet ihr auch das noch weiter ausformulieren können. 47:24.570 --> 47:28.950 Und wir können auch schreiben, dass es nicht unbedingt eine 47:28.950 --> 47:31.250 deterministische Turingmaschine sein muss, wir können sagen irgendeine 47:31.250 --> 47:31.830 Turingmaschine. 47:32.350 --> 47:34.550 Und warum, das werde ich gleich noch zeigen. 47:35.530 --> 47:39.710 Und EXP ist die Klasse der Entscheidungsprobleme, die von einer 47:39.710 --> 47:45.410 deterministischen Turingmaschine in O von zwei hochunken Polynomen 47:45.410 --> 47:47.150 weit gelöst werden können. 47:51.290 --> 47:55.850 Das sind im Wesentlichen die Definitionen, davon gibt es komplexere 47:55.850 --> 48:01.290 oder weniger komplexere Definitionen, aber das hätte uns in diesem 48:01.290 --> 48:02.110 Fall gereicht. 48:03.110 --> 48:06.930 Und jetzt die Beziehung zwischen den Klassen. 48:08.690 --> 48:20.130 L ist die Klasse der Entscheidungsprobleme, die von einer 48:20.130 --> 48:26.310 deterministischen Turingmaschine in logarithmischer Zeit gelöst werden 48:26.310 --> 48:26.730 können. 48:29.190 --> 48:32.050 Und das ist gerade links unten. 48:32.990 --> 48:38.030 Und L ist eine Teilmenge von NL, das ist im Wesentlichen das gleiche, 48:38.110 --> 48:39.730 bloß wie P und NP. 48:40.190 --> 48:45.110 Das heißt hier haben wir eine deterministische Turingmaschine, die das 48:45.110 --> 48:48.010 in logarithmisch viel Zeit berechnen kann, hier eine nicht 48:48.010 --> 48:48.950 deterministische. 48:49.970 --> 48:57.290 Dann NL ist Teilmenge von P. P ist Teilmenge von NP. 48:59.030 --> 49:03.070 Dann kommt PSPACE, Teilmenge von PSPACE. 49:04.970 --> 49:09.590 Und als nächstes, also das alles umfassend, ist EXPTIME. 49:11.450 --> 49:15.430 Und EXPTIME ist Teilmenge von EXPACE. 49:17.130 --> 49:21.030 Und jetzt hatten wir eigentlich immer so deterministische 49:21.030 --> 49:22.790 Turingmaschinen, nicht deterministische Turingmaschinen. 49:25.890 --> 49:27.270 Wie sieht es jetzt hier aus? 49:27.350 --> 49:29.970 Wir haben PSPACE, wie sieht es mit NPSPACE aus? 49:29.970 --> 49:38.870 Für NPSPACE wurde gezeigt, dass NPSPACE gleich PSPACE ist. 49:39.290 --> 49:43.350 Was auch erklärt, warum wir, ob wir nun eine deterministische 49:43.350 --> 49:45.950 Turingmaschine nehmen oder eine nicht deterministische Turingmaschine, 49:46.330 --> 49:50.150 wir können es in Polymer viel Platz berechnen. 49:51.610 --> 49:52.170 So. 49:53.570 --> 49:57.590 Und die zweite Frage war bezüglich eines Problems, was nicht in 49:57.590 --> 50:01.350 sinnvoller Rechenzeit und Speicherplatz gelöst werden kann. 50:01.550 --> 50:03.470 Da kann man erstmal ein bisschen allgemeiner vorgehen. 50:03.670 --> 50:04.410 Wir haben L. 50:06.690 --> 50:08.270 Dann gehen wir weiter. 50:08.570 --> 50:10.990 Das liegt alles noch im grünen Bereich. 50:10.990 --> 50:19.830 Und dann wird es interessant, wenn wir Richtung NP kommen, PSPACE, 50:21.070 --> 50:30.090 EXPTIME und man vermutet, dass man zumindest hier ist man auf jeden 50:30.090 --> 50:32.750 Fall verloren, was Probleme angeht. 50:32.750 --> 50:37.890 Und EXPACE umfasst halt alle Probleme. 50:39.430 --> 50:41.190 L, NL, P, NP. 50:42.210 --> 50:49.330 Und was die große Preisfrage ist, ist L gleich NL oder was wir halt 50:49.330 --> 50:51.230 kennen ist P gleich NP. 50:52.250 --> 50:53.430 Das ist ein Millenniumsproblem. 50:54.650 --> 50:56.690 Wir wissen auch nicht, ob die beiden gleich sind. 50:56.690 --> 51:00.770 Man weiß eigentlich hier in dieser Beziehung nur, das ist eine 51:00.770 --> 51:02.590 Teilmenge, aber ist es auch gleich? 51:03.330 --> 51:04.790 Das ist noch eine große Preisfrage. 51:06.790 --> 51:09.290 Wir wissen es nur für PSPACE und NPSPACE. 51:10.610 --> 51:13.770 Und das sind im Wesentlichen noch nicht alle Komplexitätsklassen, die 51:13.770 --> 51:14.150 es gibt. 51:14.750 --> 51:17.830 Es gibt auch eine Seite, die heißt Complexity Zoo. 51:19.630 --> 51:24.350 Und das ist wirklich quasi ein Zoo voller Komplexitätsklassen. 51:24.870 --> 51:28.890 Und wen das mehr interessiert, es gibt auch in der Master, also wenn 51:28.890 --> 51:32.350 ihr im Master seid, eine Vortiefungsvorlesung. 51:33.110 --> 51:35.530 Und die beschäftigt sich mit Komplexitätsklassen. 51:36.750 --> 51:40.670 Das ist ein spannendes Feld und wer sich da interessiert, kann dort 51:40.670 --> 51:41.410 gerne hingehen. 51:43.350 --> 51:45.910 Da wird auf jeden Fall noch mehr erfahren darüber. 51:46.770 --> 51:52.050 So, was ich jetzt hier für die Aufgabe B verwendet habe, ist das 51:52.050 --> 51:55.770 Problem des Handlungsreisenden, also TSP. 51:56.570 --> 51:58.490 Ihr habt das ja in der Vorlesung gehabt. 51:59.530 --> 52:04.590 Und wenn man ein mögliches exaktes Lösungsverfahren angeben möchte, 52:05.690 --> 52:08.870 dann ist eins, was verwendet wird. 52:08.970 --> 52:13.630 Man berechnet alle Weglängen aller möglichen Rundreisen. 52:14.630 --> 52:16.230 Was bedeutet das? 52:17.230 --> 52:22.450 Das ist schon für eine kleine Anzahl von Städten unpraktikabel. 52:24.010 --> 52:32.750 Und zwar, wenn man N Städte hat, dann hat man quasi N-1 Fakultät für 52:32.750 --> 52:35.050 verschiedene mögliche Rundreisen. 52:35.650 --> 52:36.910 Was bedeutet das in Zahlen? 52:36.910 --> 52:41.570 Wenn ich 16 Städte oder Standorte hätte und ich müsste für alle und 52:41.570 --> 52:47.550 für diese die beste Rundreise berechnen, dann habe ich schon 653 52:47.550 --> 52:48.990 Milliarden verschiedene Rundreisen. 52:50.990 --> 52:55.510 Und ab 17 Standorten ist es dann schon im Billionenbereich. 52:56.790 --> 52:58.050 Also das geht schnell hoch. 53:00.870 --> 53:02.810 Genau, das war das nächste Thema. 53:03.550 --> 53:05.130 Das ist jetzt ein Problem. 53:05.230 --> 53:09.090 Davon gibt es natürlich noch einige mehr. 53:10.250 --> 53:12.270 Das ist für euch wahrscheinlich das Anschauliste. 53:18.260 --> 53:24.400 Im nächsten Schritt, das ist dann die Frage, ist P gleich NP? 53:26.260 --> 53:28.760 Ich habe das versucht, ein bisschen grafisch schön darzustellen. 53:32.340 --> 53:36.220 Naja, es ist eines der Millennium-Preis-Probleme. 53:36.400 --> 53:41.920 Also wenn ihr das löst, dann sitzt ihr definitiv nicht mehr lange 53:41.920 --> 53:42.220 hier. 53:48.520 --> 53:53.800 Das bedeutet dann, wir können die Probleme in NP genauso effizient... 53:54.580 --> 54:01.340 oder die Frage, die das auch beinhaltet, kann man Probleme, die in NP 54:01.340 --> 54:03.900 sind, genauso effizient lösen wie in P. 54:07.900 --> 54:12.800 Wenn der Beweis konstruktiv ist, also wenn er nicht konstruktiv ist, 54:12.980 --> 54:15.900 dann weiß man generell nicht die Auswirkungen. 54:16.040 --> 54:17.180 Das muss man vielleicht sagen. 54:18.040 --> 54:24.800 Wenn man also einen konstruktiven Beweis hat, also dann erstmal, okay, 54:24.860 --> 54:26.680 viele Probleme sind in NP vollständig. 54:26.780 --> 54:29.780 Davon habt ihr jetzt in der Vorlesung schon einige kennengelernt und 54:29.780 --> 54:31.500 seid auch einige Beweise durchgegangen. 54:34.060 --> 54:35.780 Genau, hier hatte ich nochmal dazu eine Skizze. 54:36.620 --> 54:39.540 Und was ich euch eigentlich zeigen wollte, ist das Beispiel 54:39.540 --> 54:40.620 Kryptographie. 54:41.960 --> 54:45.360 Wenn ich mich noch recht erinnere, gibt es auch verschiedene Welten, 54:45.360 --> 54:49.100 die in der Kryptographie dargestellt werden. 54:49.400 --> 54:56.060 Und eine Welt sagt auch, okay, was ist die Welt, wenn P gleich NP ist? 54:56.180 --> 54:58.140 Und was könnte denn alles passieren? 54:59.220 --> 55:04.240 Naja, viele Verfahren in der Kryptographie vertrauen gerade darauf, 55:04.400 --> 55:05.860 dass P und gleich NP ist. 55:07.280 --> 55:14.040 Und wenn das nicht mehr der Fall ist, dann kann es passieren, dass man 55:14.040 --> 55:19.720 effizient NP vollständige Probleme berechnen kann. 55:20.340 --> 55:24.780 Und das bedeutet insbesondere auch, dass man Verfahren wie das Public 55:24.780 --> 55:30.360 Key Verfahren, was überall im Internet verwendet wird, oder AIS, 3DS, 55:30.660 --> 55:34.800 also eure Router, die ihr daheim zu stehen habt, eure WLAN Access 55:34.800 --> 55:38.200 Points, das könnt ihr dann alles wegschmeißen. 55:38.200 --> 55:40.800 Also das ist die Idee. 55:41.060 --> 55:47.240 Und wenn P gleich NP ist, dann könnte es passieren, dass das eintritt. 55:47.380 --> 55:49.000 Das ist ein mögliches Szenario. 55:49.120 --> 55:52.220 Davon gibt es natürlich noch unheimlich viele andere Szenarien. 55:52.320 --> 55:54.280 Manche würden sich freuen, wenn das der Fall ist. 55:54.720 --> 55:57.160 Die Kryptographie wahrscheinlich eher nicht. 55:58.320 --> 56:01.840 Aber dann muss man sich echt andere Verfahren ausdenken, wenn das der 56:01.840 --> 56:02.480 Fall ist. 56:04.460 --> 56:08.620 Und damit will ich auch so ein bisschen zeigen, die theoretische 56:08.620 --> 56:14.120 Informatik hört sich in vielen Fällen vielleicht für euch nicht so 56:14.120 --> 56:19.640 interessant an, aber es gibt auch wirklich Probleme. 56:19.960 --> 56:25.940 Wenn die auftreten, dann hat das direkten Einfluss in der Praxis oder 56:25.940 --> 56:29.380 in diesem Fall kann direkten Einfluss auf die Praxis haben. 56:30.340 --> 56:34.720 Und bezüglich Komplexitätsklassen auch noch eine Motivation. 56:36.120 --> 56:42.440 Ihr habt ein Problem, das ist schwer zu lösen, aber euer... und das 56:42.440 --> 56:46.100 wird auch in Gary Johnson als Motivation verwendet. 56:47.820 --> 56:52.380 Und ihr seid mittlerweile schon im Arbeitsleben dann und ihr kriegt 56:52.380 --> 56:59.600 von eurem Arbeitgeber die Aufgabe, ein Problem zu lösen, was schwer 56:59.600 --> 56:59.940 ist. 57:00.120 --> 57:04.420 Ihr wisst natürlich in dem Moment noch nicht, dass es schwer ist und 57:04.420 --> 57:06.680 dass es nicht effizient zu lösen ist. 57:07.540 --> 57:10.960 Und ihr probiert rum und merkt, okay, die Laufzeiten sind katastrophal 57:10.960 --> 57:15.820 und überlegt euch, kann man das überhaupt effizient lösen. 57:16.660 --> 57:19.820 Und ihr könnt jetzt nicht zu einem Chef gehen, Laufzeiten sind 57:19.820 --> 57:21.720 katastrophal, ich kann ja aber nicht sagen, warum. 57:21.720 --> 57:26.060 Ich glaube, das ist ein guter Grund, gefeuert zu werden oder zumindest 57:26.060 --> 57:30.880 nicht in die nächste gewünschte Gehaltsgruppe zu kommen. 57:33.520 --> 57:36.620 Und dann müsst ihr ihm zeigen, okay, es geht einfach nicht besser. 57:36.960 --> 57:40.540 Dieses Problem ist einfach schwer, man kann es nicht effizient lösen. 57:41.220 --> 57:45.080 Und das ist eine Möglichkeit, ihm zu zeigen, okay, das Problem ist 57:45.080 --> 57:47.840 schwer, ich kann es nicht effizient lösen, aber es kann niemand 57:47.840 --> 57:48.840 effizient lösen. 57:50.460 --> 57:52.260 Und damit will ich auch die Übung beenden. 57:52.420 --> 57:55.740 Ich hoffe, es hat euch Spaß gemacht und wir sehen uns beim nächsten Mal.