WEBVTT 00:04.570 --> 00:06.730 Guten Morgen fangen wir an. 00:07.390 --> 00:10.990 Sie haben ja in der letzten Woche bereits begonnen mit dem neuen 00:10.990 --> 00:13.790 Kapitel Berechenbarkeit Turing-Maschinen. 00:14.770 --> 00:18.090 Und das Konzept der Turing-Maschine wurde auch bereits eingeführt. 00:18.890 --> 00:21.490 Daran werden wir jetzt gleich weiter anknüpfen. 00:21.870 --> 00:26.070 Aber nochmal, was ist Sinn und Zweck dieses Kapitels? 00:26.230 --> 00:35.070 Also innerhalb des ganzen Fokus oder Themas, das von der theoretischen 00:36.290 --> 00:43.770 Informatik abgedeckt wird, ist das Kapitel Berechenbarkeit dasjenige, 00:43.930 --> 00:49.230 was sozusagen diese ganz grundlegenden Fragen gibt es Grenzen der 00:49.230 --> 00:50.010 Berechenbarkeit? 00:50.170 --> 00:56.450 Gibt es irgendwelche Probleme, die nicht berechenbar sind, abklärt? 00:57.450 --> 01:01.330 Das heißt, es ist ganz grundlegend, was wir hier in dem Kapitel 01:01.330 --> 01:02.270 besprechen werden. 01:03.070 --> 01:09.630 Und wenn wir dazu Turing-Maschinen betrachten, dann ähnlich wie bei 01:09.630 --> 01:16.210 den endlichen Automaten, als ein abstraktes Modell für echte Rechner, 01:16.670 --> 01:21.030 um Aussagen machen zu können darüber, was echte Rechner können und vor 01:21.030 --> 01:22.710 allem, was sie nicht können. 01:24.090 --> 01:30.230 Und das Turing-Maschinen-Modell, das wir kennengelernt haben, 01:49.980 --> 01:52.020 sah also so aus. 01:52.280 --> 01:59.740 Zunächst mal, das ist ein deterministisches Berechnungsmodell, das wir 01:59.740 --> 02:00.740 jetzt betrachten. 02:01.340 --> 02:06.140 Wir werden, das schon vorab, auch eine nicht deterministische Variante 02:06.140 --> 02:10.800 der Turing-Maschine im nächsten Kapitel betrachten und auch darüber 02:10.800 --> 02:13.520 uns dann Gedanken machen, was eigentlich deterministische und nicht 02:13.520 --> 02:17.540 deterministische Turing-Maschinen miteinander zu tun haben oder wie 02:17.540 --> 02:19.040 die zueinander bestehen. 02:19.100 --> 02:22.160 Aber jetzt erst mal, die nicht deterministische Turing-Maschine 02:22.160 --> 02:26.500 besteht aus einer Zustandsmenge Q, die endlich ist, wie beim endlichen 02:26.500 --> 02:31.320 Automat, einem Eingabealphabet Sigma, das ebenfalls endlich ist, das 02:31.320 --> 02:33.060 ist eben auch wie beim endlichen Automat. 02:33.140 --> 02:39.400 Es gibt ein spezielles Symbol Plank, das nicht im Eingabealphabet ist 02:39.400 --> 02:44.540 und wir betrachten noch weitere Symbole, die so Art Hilfssymbole sind 02:44.540 --> 02:49.340 und diese Symbole zusammen mit dem Eingabealphabet und dem Plank 02:49.340 --> 02:54.800 bilden das Bandalphabet Gamma, das aber eben auch endlich ist. 02:55.780 --> 02:59.340 Wir haben einen ausgezeichneten Startzustand und wir haben eine 02:59.340 --> 03:03.900 Übergangsfunktion, die nimmt sich einen Zustand her und ein Symbol aus 03:03.900 --> 03:09.320 dem Bandalphabet und bildet die ab auf einen neuen Zustand, ein neues 03:09.320 --> 03:16.000 Symbol aus dem Bandalphabet und eine Aktion, die sein kann, gehe nach 03:16.000 --> 03:18.640 links, gehe nach rechts oder bleibe stehen. 03:19.780 --> 03:22.980 Das heißt also, von einem Zustand wird in einen neuen Zustand 03:22.980 --> 03:26.640 übergegangen, das ist so ähnlich wie beim endlichen Automat, aber das 03:26.640 --> 03:32.380 konkret jetzt gelesene Symbol aus Gamma wird möglicherweise 03:32.380 --> 03:35.920 überschrieben und dann geht der Lese-Schreibkopf nach links oder nach 03:35.920 --> 03:40.700 rechts oder bleibt dort stehen, wo er ist und dann kann man noch eine 03:40.700 --> 03:48.100 Menge von Endzuständen definieren, Zustände, für die gilt, wenn die 03:48.100 --> 03:52.700 Turing -Maschine in einen dieser Zustände kommt, hält sie und man kann 03:52.700 --> 04:00.100 dann eben auch noch definieren oder auch nicht, ob das akzeptierende 04:00.100 --> 04:03.560 Endzustände sind, ob es mehr als einen akzeptierenden Endzustand gibt 04:03.560 --> 04:04.220 und so weiter. 04:05.060 --> 04:09.580 Das sozusagen nochmal zur formalen Einführung und dann haben Sie auch 04:09.580 --> 04:13.060 schon gesehen an Beispielen, wie so eine Turing-Maschine arbeitet. 04:13.300 --> 04:16.560 Heute werden wir weitere Beispiele betrachten. 04:17.700 --> 04:23.140 Hier nur nochmal die wichtigen Punkte zur Arbeitsweise der Turing 04:23.140 --> 04:23.580 -Maschine. 04:24.800 --> 04:30.640 Also es geht wieder in erster Linie darum, ob dieses Maschinenmodell, 04:30.860 --> 04:35.000 Turing -Maschine oder eine konkrete, eine vorgegebene Sprache 04:35.000 --> 04:38.440 akzeptiert oder erkennen kann. 04:39.320 --> 04:45.340 Und wir sagen, eine Turing-Maschine akzeptiert eine Eingabe über dem 04:45.340 --> 04:49.720 Eingabealphabet, wenn sie nach Lesen der entsprechende Eingabe in 04:49.720 --> 04:52.960 einem Zustand aus F stoppt. 04:53.060 --> 04:56.540 Also diese Endzustände, so wie wir es jetzt erstmal in der Definition 04:57.300 --> 05:00.660 festgelegt haben, sind akzeptierende Endzustände. 05:01.620 --> 05:06.020 Und sie akzeptiert dann eine ganze Sprache, genau dann, wenn sie 05:06.020 --> 05:12.760 ausschließlich aus Eingaben aus dieser Sprache in einem akzeptierenden 05:12.760 --> 05:14.300 Endzustand stoppt. 05:14.420 --> 05:17.500 Also wenn sie ausschließend oder genau die Worte aus der Sprache 05:17.500 --> 05:18.020 akzeptiert. 05:18.260 --> 05:21.160 Das ist im Prinzip so wie beim endlichen Automaten. 05:21.160 --> 05:26.840 Und wir sagen dann, dass eine Sprache entscheidbar ist, anderes Wort 05:26.840 --> 05:31.500 ist rekursiv, wenn es eine Turing-Maschine gibt, die auf allen 05:31.500 --> 05:38.680 Eingaben stoppt und eine Eingabe W genau dann akzeptiert, wenn W aus 05:38.680 --> 05:39.520 der Sprache ist. 05:40.620 --> 05:47.580 Also hier geht es jetzt um sozusagen den Begriff Berechenbarkeit. 05:51.340 --> 05:54.840 Im Zusammenhang mit Sprachen nennt man das Entscheidbarkeit. 05:55.000 --> 05:58.520 Sie werden gleich auch den Begriff Berechenbarkeit kennenlernen. 05:58.700 --> 06:03.160 Und es gibt jetzt sozusagen zwei Varianten. 06:04.580 --> 06:09.700 Es kann sein, dass eine Turing-Maschine einer vorgegebenen Sprache auf 06:09.700 --> 06:14.780 allen Eingaben hält und genau auf den Eingaben aus der Sprache in 06:14.780 --> 06:18.000 einem akzeptierenden Endzustand hält. 06:18.140 --> 06:21.660 Wenn es zu einer Sprache so eine Turing-Maschine gibt, dann heißt die 06:21.660 --> 06:22.700 Sprache entscheidbar. 06:23.200 --> 06:26.500 Es gäbe aber auch die Variante, dass man sagt, naja gut, was bei 06:26.500 --> 06:31.280 Eingaben passiert, die nicht aus der Sprache sind. 06:32.040 --> 06:36.380 Das interessiert uns nicht so. 06:36.840 --> 06:41.480 Da fordern wir nicht unbedingt, dass die Turing-Maschine überhaupt 06:41.480 --> 06:42.160 anhält. 06:43.740 --> 06:49.200 Und eine Sprache heißt dann präkursiv aufzählbar oder semi 06:49.200 --> 06:54.420 -entscheidbar, wenn es eine Turing-Maschine gibt, die genau die 06:54.420 --> 06:58.840 Eingaben w akzeptiert, die aus l sind. 07:00.360 --> 07:04.220 Und hier wird nichts darüber gesagt, was passiert, wenn w nicht in l 07:04.220 --> 07:04.560 ist. 07:05.700 --> 07:10.260 Das heißt also, hier könnte es so sein, dass bei w nicht aus l, also 07:10.260 --> 07:13.880 Eingaben w, die nicht aus l sind, die Turing-Maschine auch gar nicht 07:13.880 --> 07:14.380 anhält. 07:18.010 --> 07:23.510 Diese beiden Konzepte, Entscheidbarkeit einerseits, Semi 07:23.510 --> 07:26.530 -Entscheidbarkeit andererseits, die werden wir genauer betrachten. 07:27.030 --> 07:34.410 Die stehen sozusagen für die intuitiven Begriffe von etwas ist 07:34.410 --> 07:39.630 berechenbar oder nicht so richtig berechenbar, semi-berechenbar oder 07:39.630 --> 07:40.430 gar nicht berechenbar. 07:42.070 --> 07:46.370 Aber wie gesagt, das müssen wir noch genauer definieren. 07:47.070 --> 07:52.470 Um jetzt über die Arbeitsweise einer Turing-Maschine reden zu können, 07:52.930 --> 07:59.250 brauchen wir noch eine Notation, die im Prinzip beschreibt, wie ein 07:59.250 --> 08:03.990 einzelner Zustand einer Abarbeitung der Turing-Maschine aussieht oder 08:03.990 --> 08:05.850 wie man den kompakt beschreiben kann. 08:06.230 --> 08:09.590 Das ist die Notation oder der Begriff der Konfiguration. 08:10.170 --> 08:14.570 Wenn man uns eine spezielle Situation in der sich eine Turing-Maschine 08:14.570 --> 08:20.210 M befinden kann anguckt, dann kann man diese Situation durch die 08:20.210 --> 08:25.590 sogenannte Konfiguration beschreiben und eine Konfiguration sieht also 08:25.590 --> 08:30.290 so aus, das ist ein Wort gefolgt von einem Zustand Q in Klammern, 08:30.810 --> 08:34.570 gefolgt von einem Symbol, gefolgt von einem Wort. 08:35.670 --> 08:41.390 Also eine Konfiguration hat die Form W, Q in Klammern, A, V, wobei W 08:41.390 --> 08:47.030 und V eben Worte über dem Bandalphabet sind, A ein Symbol aus dem 08:47.670 --> 08:49.970 Bandalphabet ist und Q ein Zustand. 08:51.130 --> 08:55.850 Und was wird damit beschrieben mit W, Q in Klammern, A, V? 08:56.470 --> 09:01.130 Damit wird beschrieben, dass zu diesem Zeitpunkt durch die 09:01.130 --> 09:06.470 Konfiguration W, Q, A, V beschrieben wird. 09:07.130 --> 09:11.310 Die Turing-Maschine sich gerade im Zustand Q befindet. 09:12.790 --> 09:18.930 An der Stelle, wo der Lese-Schreibkopf steht, das Symbol A steht. 09:20.170 --> 09:25.230 Links vom Lese-Schreibkopf das Wort W steht und rechts vom Lese 09:25.230 --> 09:28.010 -Schreibkopf das Wort V steht. 09:28.730 --> 09:32.970 Also dass wir Q gerade an die Stelle schreiben zwischen W und A, V 09:35.390 --> 09:40.950 signalisiert oder zeigt oder kodiert, dass links vom Lese-Schreibkopf 09:40.950 --> 09:42.210 das Wort W steht. 09:43.390 --> 09:49.110 Der Lese-Schreibkopf direkt an der Stelle, wo der Lese-Schreibkopf 09:49.110 --> 09:52.070 steht, das Symbol A steht und rechts daneben V. 09:52.790 --> 09:55.650 Und dann muss man halt noch dazu sagen, in welchem Zustand die Turing 09:55.650 --> 10:00.450 -Maschine ist und das ist eben gerade dann Q bei dieser Konfiguration. 10:02.030 --> 10:03.230 Das ist ganz einfach. 10:03.930 --> 10:08.950 Schauen wir uns einfach mal an, wie man dann eben eine Abarbeitung 10:08.950 --> 10:14.110 einer speziellen Eingabe für eine spezielle Turing-Maschine über die 10:14.110 --> 10:18.710 Konfiguration, die die Turing-Maschine durchläuft, beschreiben kann. 10:19.210 --> 10:23.450 Wir haben hier eine Turing-Maschine, die sieht so aus. 10:26.490 --> 10:32.130 Wenn eine 0 gelesen wird, bleiben wir im Anfangszustand S und gehen 1 10:32.130 --> 10:32.730 nach rechts. 10:32.890 --> 10:36.370 Das passiert so lange, bis eine 1 gesehen wird. 10:36.610 --> 10:40.230 Dann gehen wir in den Zustand Q1, gehen wieder 1 nach rechts. 10:40.710 --> 10:43.250 Soweit ist auch noch nichts geändert worden an der Eingabe. 10:44.010 --> 10:48.350 Wenn dann im Zustand Q1 eine 1 gelesen wird, geht man wieder weiter 10:48.350 --> 10:54.310 nach rechts, ändert nichts an der Eingabe, bis man an dem Ende der 10:54.310 --> 10:57.270 Eingabe angekommen ist, also ein Blank gelesen wird. 10:57.770 --> 11:00.210 Das Blank wird auch unverändert gelassen. 11:01.190 --> 11:05.710 Die Turing-Maschine geht vom Zustand Q1 in den Zustand Q2 über und 11:05.710 --> 11:06.790 geht wieder nach links. 11:07.110 --> 11:10.590 Also von hier nach da bis wir hier hinkommen, sind wir sozusagen 11:10.590 --> 11:13.490 einmal von links nach rechts über das Wort gegangen. 11:15.170 --> 11:22.230 Und dann beim Zustand Q2 passiert folgendes, wenn eine 1 gelesen wird, 11:22.350 --> 11:26.590 wird diese 1 durch ein Blank überschrieben und 1 nach links gegangen. 11:26.890 --> 11:32.150 Und die Turing-Maschine geht in den Zustand Q3 und im Zustand Q3 wird 11:32.150 --> 11:35.010 nichts anderes gemacht, als nach vorne zu gehen. 11:35.290 --> 11:38.410 Also egal, ob dann eine 0 oder eine 1 gelesen wird, die 0 oder 1 wird 11:38.410 --> 11:41.970 auf dem Band unverändert gelassen und dieser Schreibtopf geht nach 11:41.970 --> 11:42.270 vorne. 11:42.470 --> 11:48.610 Wenn wir hier waren, sind wir ganz nach rechts gegangen, gehen dann in 11:48.610 --> 11:51.330 den Zustand und gehen hier wieder ganz nach links. 11:51.930 --> 11:54.350 Also rechts haben wir die 1 gelöscht, dann gehen wir ganz nach links. 11:54.910 --> 11:59.250 Und wenn wir ganz links am Anfang des Wortes angekommen sind und an 11:59.250 --> 12:03.370 der Stelle davor, da steht ja dann ein Blank, gehen wir in den Zustand 12:03.370 --> 12:08.230 Q4 über, lassen das Blank unverändert und gehen wieder nach rechts. 12:09.450 --> 12:15.010 Wenn da eine 0 gelesen wird, wird die 0 durch ein Blank überschrieben, 12:15.010 --> 12:20.550 nach Q5 gegangen und dann wird, je nachdem was gelesen wird, entweder 12:20.550 --> 12:24.230 nach Q6 gegangen und die Eingabe unverändert gelassen, nämlich wenn da 12:24.230 --> 12:28.010 ein 1 und ein 0 steht, oder wenn da ein Blank steht, wird in den 12:28.010 --> 12:29.930 akzeptierenden Endzustand gegangen. 12:30.590 --> 12:33.610 Und ansonsten, wenn da noch nicht ein Blank stand, dann gehen wir 12:33.610 --> 12:39.510 wieder nach rechts, bei dem Übergang von Q5 nach Q6 und bei den 12:39.510 --> 12:44.910 Übergängen von nach Q6 gehen wir wieder über die Eingabe ganz nach 12:44.910 --> 12:48.550 rechts, verändern die Eingabe nicht, bis wir am Ende angekommen sind 12:48.550 --> 12:54.850 und kommen dann wieder in unseren Zustand Q2 der genau dann, wenn eben 12:57.990 --> 13:01.810 wir gehen nach Q2 und wieder 1 nach links und der eben genau dann, 13:01.930 --> 13:08.070 wenn da am rechten Rand, also am Ende der Eingabe eine 1 steht, wieder 13:08.070 --> 13:12.230 diese 1 überschreibt und dann hier durch diesen Zykel führt. 13:12.890 --> 13:14.210 Und was macht dieser Zykel? 13:14.430 --> 13:18.050 Ich habe schon gesagt, man geht nach rechts, wenn man eine 1 liest, 13:18.450 --> 13:21.870 wird die gelöscht und geht wieder nach links und genau dann, wenn ganz 13:21.870 --> 13:23.910 links eine 0 steht, wird die gelöscht. 13:24.090 --> 13:27.750 Das heißt, bei jedem Durchlauf durch den Zykel wird rechts eine 1 und 13:27.750 --> 13:29.650 links eine 0 gelöscht. 13:30.890 --> 13:37.830 Und genau dann, wenn das sozusagen aufgeht und bei diesem Durchlauf 13:37.830 --> 13:44.290 nur noch bei Planks landet, also genauso viele 1 in rechts wie 0 in 13:44.290 --> 13:48.370 links gelöscht wurden, kommt man in den akzeptierenden Endzustand. 13:49.790 --> 13:56.770 Aus dieser Studie dessen, was die Turing-Maschine macht, kann man 13:56.770 --> 14:03.270 ableiten, dass sie also genau die Sprache 0 hoch N, 1 hoch N, N größer 14:03.270 --> 14:05.310 gleich 1 akzeptiert. 14:05.490 --> 14:08.550 Also die Sprache bestehend aus einer Folge von Nullen gefolgt von 14:08.550 --> 14:10.570 einer Folge von Einsen. 14:11.630 --> 14:14.910 Derart, dass die Anzahl der Nullen genau die Anzahl der Einsen ist. 14:15.110 --> 14:18.310 Von dieser Sprache wissen wir, sie ist nicht regulär. 14:18.770 --> 14:21.590 Es gibt keinen endlichen Automaten, der diese Sprache erkennen kann. 14:21.970 --> 14:25.690 Aber offensichtlich gibt es eine Turing-Maschine, die diese Sprache 14:25.690 --> 14:26.450 erkennen kann. 14:26.550 --> 14:30.730 Und jetzt schauen wir uns mal an, sozusagen Schritt für Schritt, was 14:30.730 --> 14:34.250 also diese Turing-Maschine bei einer Eingabe, die da gerade genau 14:34.250 --> 14:38.590 passt, nämlich zwei Nullen gefolgt von zwei Einsen, macht und wie die 14:38.590 --> 14:41.550 Konfigurationen aussehen, die dadurch laufen werden. 14:43.770 --> 14:50.190 Also, sie startet in S und liest 0. 14:52.750 --> 14:57.890 Die Konfiguration, die dies beschreibt, startet mit dem Wort, das 14:57.890 --> 15:03.210 links von der Stelle steht, an der der Lese-Schreibkopf ist. 15:04.170 --> 15:06.410 Das ist Plank, eine Folge von Planks. 15:07.690 --> 15:12.530 Dann wird der Zustand in Klammern angegeben, in dem sich die Turing 15:12.530 --> 15:14.130 -Maschine befindet, das ist S. 15:15.450 --> 15:21.110 Genau daneben wird das Symbol angegeben, das an der Stelle steht, an 15:21.110 --> 15:25.350 dem gerade der Lese-Schreibkopf ist, oder das gerade gelesen wird, das 15:25.350 --> 15:30.690 ist hier die 0, gefolgt von dem Rest des Wortes, das rechts davon 15:30.690 --> 15:30.990 steht. 15:30.990 --> 15:32.110 Das ist 011. 15:33.150 --> 15:35.290 Und was machen wir, wenn wir hier eine 0 lesen? 15:36.290 --> 15:39.710 Wir lassen die unverändert und gehen mit dem Lese-Schreibkopf 1 nach 15:39.710 --> 15:40.050 rechts. 15:40.310 --> 15:44.490 Das heißt, die darauf folgende Konfiguration sieht so aus 0S in 15:44.490 --> 15:45.570 Klammern 011. 15:47.390 --> 15:51.130 Und dann wird wieder eine 0 gelesen und dann bleibt man wieder im 15:51.130 --> 15:55.790 Zustand S und der Lese-Schreibkopf geht 1 nach rechts, das heißt, 15:55.910 --> 16:01.830 darauf folgt dann die Konfiguration 00 S1 in Klammern 11. 16:02.770 --> 16:08.170 Das heißt, da wo der Lese-Schreibkopf ist, da steht eine 1, rechts 16:08.170 --> 16:11.330 davon eine weitere 1 und links davon 2 Nullen. 16:11.530 --> 16:13.070 Wir sind im Zustand S1. 16:13.450 --> 16:17.690 So, wenn jetzt im Zustand S1 eine 1 gelesen wird, gehen wir in einen 16:17.690 --> 16:21.470 neuen Zustand über, nämlich in Q1 und der Lese-Schreibkopf geht 1 nach 16:21.470 --> 16:23.570 rechts und ansonsten bleibt das Ganze unverändert. 16:24.030 --> 16:32.750 Das heißt, die darauf folgende Konfiguration ist dann 001 Q1 gefolgt 16:32.750 --> 16:33.310 von 1. 16:33.450 --> 16:37.070 Was ich hier nicht dazu schreibe, ist, dass danach dann lauter Planks 16:37.070 --> 16:37.430 kommen. 16:38.590 --> 16:45.510 So, im Zustand Q1 wird, wenn eine 1 gelesen wird, diese 1 unverändert 16:45.510 --> 16:49.110 gelassen, wir bleiben im Zustand Q1, der Lese-Schreibkopf geht 1 nach 16:49.110 --> 16:49.310 rechts. 16:49.430 --> 16:54.650 Das heißt, die folgende Konfiguration sieht dann so aus 0011 Zustand 16:54.650 --> 16:56.830 Q1 Plank. 16:56.830 --> 17:01.550 So, wenn jetzt ein Plank gelesen wird im Zustand Q1, dann gehen wir in 17:01.550 --> 17:05.710 den Zustand Q2 über das Plank wird unverändert gelassen und der Lese 17:05.710 --> 17:07.370 -Schreibkopf geht wieder 1 nach links. 17:07.550 --> 17:12.750 Das heißt also, die folgende Konfiguration sieht dann so aus 001 17:12.750 --> 17:16.230 Zustand Q2, Lese-Schreibkopf steht an der 1. 17:16.530 --> 17:17.770 Rechts davon nur Planks. 17:19.510 --> 17:23.770 So, bei Q2 ist es so, wenn eine 1 gelesen wird, wird diese 1 durch 17:23.770 --> 17:27.210 einen Plank überschrieben und wir gehen mit dem Lese-Schreibkopf 1 17:27.210 --> 17:29.730 nach links und der neue Zustand ist Q3. 17:30.250 --> 17:36.510 Das heißt also, auf diese Konfiguration folgt die Konfiguration 00 Q3 17:36.510 --> 17:37.070 1. 17:42.770 --> 17:47.730 In Q3 ist es ja so, wenn 0 oder 1 gelesen wird, gehen wir einfach nach 17:47.730 --> 17:48.090 links. 17:48.590 --> 17:49.910 Die Eingabe bleibt unverändert. 17:50.090 --> 17:54.450 Das heißt also, was dann gefolgt ist, hier 1 nach links rücken, also 17:54.450 --> 17:59.750 die Konfiguration 0 Q3, gefolgt von 01 und dann wieder wenn wir hier 17:59.750 --> 18:06.770 eine 0 lesen, 1 nach links rücken, also Plank Q3 001 und dann wenn wir 18:06.770 --> 18:12.350 jetzt die 0 lesen, wieder bleiben unverändert in Q3 gehen 1 nach 18:12.350 --> 18:15.710 links, also Plank Q3 Plank 001. 18:16.150 --> 18:19.750 So, jetzt wird ein Plank gelesen, wenn in dem Zustand Q3 ein Plank 18:19.750 --> 18:21.750 gelesen wird, gehen wir nach Q4. 18:22.710 --> 18:26.330 Plank wird unverändert gelassen und der Lese-Schreibkopf geht wieder 1 18:26.330 --> 18:26.850 nach rechts. 18:27.010 --> 18:32.250 Das heißt, es folgt dann die Konfiguration Plank Q4, gefolgt von 001. 18:33.210 --> 18:37.010 Und in Q4 wird jetzt auch die Eingabe wieder verändert, nämlich wenn 18:37.010 --> 18:41.770 dann eine 0 gelesen wird, wird die 0 durch ein Plank überschrieben und 18:41.770 --> 18:42.950 1 nach rechts gegangen. 18:43.450 --> 18:46.670 Hier wird tatsächlich... und in Q5 übergegangen. 18:46.750 --> 18:48.150 Hier wird tatsächlich eine 0 gelesen. 18:48.310 --> 18:53.070 Das heißt also, die folgende Konfiguration ist Plank Q5 01. 18:54.330 --> 18:59.270 Und wenn wir in Q5 eine 0 lesen, wird die unverändert gelassen. 18:59.410 --> 19:03.110 Wir gehen nach Q6 und es wird einfach 1 nach rechts gegangen. 19:03.330 --> 19:07.410 Das heißt also, darauf folgt die Konfiguration 0 Q6 1. 19:07.890 --> 19:11.590 Wenn wir Q6 0 oder 1 lesen, wird einfach nach rechts gegangen. 19:12.430 --> 19:14.230 Die Eingabe unverändert gelassen. 19:14.410 --> 19:20.430 Das heißt also, danach ist die Konfiguration 01 Q6 Plank. 19:21.350 --> 19:23.130 So, jetzt wird ein Plank gelesen. 19:23.230 --> 19:26.750 Wenn wir im Zustand Q6 ein Plank lesen, dann gehen wir einfach wieder 19:26.750 --> 19:29.070 nach links und gehen in den Zustand Q2. 19:29.310 --> 19:33.690 Das heißt, darauf folgt dann die Konfiguration 0 Q2 1. 19:34.350 --> 19:37.330 Und dann geht es wieder hier durch den Zykel durch. 19:38.050 --> 19:43.090 Das gehe ich jetzt nicht einzeln durch, bis wir tatsächlich bei Q5 ein 19:43.090 --> 19:44.030 Plank lesen. 19:44.510 --> 19:49.310 Dann gehen wir nach rechts und in den akzeptierenden Endzustand. 19:51.010 --> 19:51.930 Okay. 19:53.410 --> 19:54.210 Gut. 19:54.270 --> 19:58.090 Das heißt also, über diese Mutation, Konfiguration kann man die 19:58.090 --> 20:05.910 Berechnung einer Turing-Maschine zu einer konkreten Eingabe 20:05.910 --> 20:07.070 vollständig beschreiben. 20:11.370 --> 20:12.070 Okay. 20:12.070 --> 20:18.190 Bisher haben wir nur darauf geschaut, ob zu einer bestimmten Eingabe 20:18.190 --> 20:23.950 die Turing-Maschine in einem akzeptierenden Endzustand endet oder 20:23.950 --> 20:24.650 nicht. 20:24.850 --> 20:30.770 Gar nicht endet oder in einem nicht akzeptierenden Zustand hält. 20:31.750 --> 20:35.390 Wir haben aber hier an dem Beispiel gesehen, dass die Turing-Maschine 20:35.390 --> 20:39.110 auch das, was auf dem Band als Eingabe steht, verändert. 20:40.210 --> 20:46.130 Hier bei diesem Beispiel wurde die Eingabe letztendlich gelöscht. 20:46.470 --> 20:49.990 Das ist nicht sonderlich spannend, aber man könnte sich ja auch 20:49.990 --> 20:50.930 anderes vorstellen. 20:51.690 --> 20:55.610 Und dann wären wir bei der Sichtweise, zu einer Eingabe wird eine 20:55.610 --> 20:56.650 Ausgabe produziert. 20:57.550 --> 21:03.750 Was ja eigentlich das Interesse ist, dass ein Rechner zu einer Eingabe 21:03.750 --> 21:06.050 eine bestimmte Ausgabe produziert. 21:06.650 --> 21:09.850 Das kann man mit der Turing-Maschine eben auch formal fassen. 21:10.450 --> 21:13.890 Nämlich das, was da passiert, wir geben eine bestimmte Eingabe rein, 21:14.010 --> 21:17.730 die Turing-Maschine verändert das, was da auf dem Band als Eingabe 21:17.730 --> 21:22.610 steht und hält dann am Schluss mit irgendeiner Ausgabe auf dem Band. 21:23.070 --> 21:26.830 Das kann man interpretieren als die Realisierung einer Funktion. 21:28.190 --> 21:33.510 Und entsprechend sagen wir, eine Funktion, die von den Worten über dem 21:33.510 --> 21:38.850 Eingabe -Alphabet in die Menge der Worte über dem Band-Alphabet führt, 21:38.990 --> 21:42.870 heißt Turing-berechenbar oder total rekursiv. 21:43.090 --> 21:47.670 Wenn es eine Turing-Maschine gibt, die bei Eingabe von irgend so einem 21:47.670 --> 21:55.870 Wort aus Sigma-Sternchen gerade den Funktionswert f von dem Wort, das 21:55.870 --> 21:57.970 ist was aus Gamma-Sternchen, ausgibt. 21:58.750 --> 22:02.990 Wenn also bei Eingabe w am Schluss f von w auf dem Band steht. 22:05.490 --> 22:09.530 Und wir sagen dann eben auch, die Turing-Maschine realisiert oder eine 22:09.530 --> 22:13.730 Turing -Maschine realisiert so eine Funktion f von Sigma-Stern nach 22:13.730 --> 22:19.090 Gamma -Stern, falls gilt, dass f von w ist eben genau die Ausgabe der 22:19.090 --> 22:23.590 Turing -Maschine, wenn sie bei Eingabe w stoppt und wenn sie nicht 22:23.590 --> 22:25.090 stoppt, umdefiniert. 22:30.720 --> 22:35.400 Und hier haben wir mal ein Beispiel einer solchen Turing-Maschine, die 22:35.400 --> 22:39.600 eine sinnvolle Ausgabe zu einer Eingabe produziert. 22:40.080 --> 22:51.100 Das Eingabe-Alphabet ist 0,1 0,1, ein Wort über 0,1 kann man natürlich 22:51.100 --> 22:53.400 als binäre Zahl interpretieren. 22:54.000 --> 22:56.400 Und genau das macht die Turing-Maschine hier. 22:56.940 --> 23:02.540 Sie interpretiert die Eingabe als eine binäre Zahl und akzeptiert 23:02.540 --> 23:08.660 genau solche Eingaben, die entweder nur die 0 sind, also die Eingabe, 23:08.820 --> 23:11.760 die nur aus 0 besteht, oder keine führende 0 haben. 23:13.420 --> 23:15.280 Und was macht sie mit der Eingabe? 23:15.640 --> 23:17.580 Sie addiert eine 1 drauf. 23:17.880 --> 23:19.100 Das ist das, was hier passiert. 23:19.700 --> 23:21.260 Schauen wir uns das mal genauer an. 23:23.260 --> 23:33.240 Wenn bei s eine 0 gelesen wird, bleibt die 0 auf dem Band stehen. 23:33.360 --> 23:36.520 Der Lese-Schreibkopf geht 1 nach rechts und die Turing-Maschine geht 23:36.520 --> 23:38.040 in den Zustand Q4 über. 23:38.920 --> 23:43.580 Wenn in Q4 danach Plank gelesen wird, dann war also die Eingabe nur 23:43.580 --> 23:48.440 die 0, bleibt das Plank unverändert und der Lese-Schreibkopf geht 23:48.440 --> 23:52.360 wieder 1 nach links und die Turing-Maschine geht in Q5 über. 23:53.200 --> 23:57.240 Dort liest sie dann 0, diese 0, die hier am Anfang gelesen wird. 23:57.240 --> 23:59.160 Diese 0 wird in 1 geändert. 24:00.360 --> 24:04.980 Der Lese-Schreibkopf geht wieder 1 nach links und die Turing-Maschine 24:04.980 --> 24:06.620 geht in den akzeptierenden Endzustand. 24:06.740 --> 24:10.560 Das heißt, wenn die Eingabe 0 war, ist die Ausgabe tatsächlich 1. 24:11.020 --> 24:12.800 Also erstmal die Eingabe wird akzeptiert. 24:12.920 --> 24:17.680 Wir enden im akzeptierenden Endzustand F und das, was auf dem Band 24:17.680 --> 24:18.860 danach steht, ist die 1. 24:19.000 --> 24:20.440 Gut, das war jetzt noch der einfache Fall. 24:20.900 --> 24:24.820 Die einzige andere Möglichkeit, wo die Turing-Maschine etwas macht, 24:24.820 --> 24:30.020 also nicht total undefiniert ist, ist, wenn sie als allererstes eine 1 24:30.020 --> 24:30.440 liest. 24:31.220 --> 24:32.640 Und was macht sie dann? 24:32.920 --> 24:36.020 Sie lässt die 1 unverändert stehen, geht 1 nach rechts und geht in den 24:36.020 --> 24:37.320 Zustand Q1 über. 24:37.840 --> 24:42.160 Bei dem Zustand Q1 passiert nichts anderes, als dass ganz ans Ende der 24:42.160 --> 24:43.420 Eingabe gegangen wird. 24:44.380 --> 24:49.180 Wird 1 oder 0 gelesen, unverändert gelassen, mit dem Lese-Schreibkopf 24:49.180 --> 24:51.360 1 nach rechts gegangen, in Q1 geblieben. 24:52.140 --> 24:55.500 Es wird nichts anderes gemacht, als ganz nach rechts ans Ende der 24:55.500 --> 24:57.780 Eingabe gegangen oder die Eingabe vollständig gelesen. 24:58.080 --> 25:01.540 Wenn wir dann am Ende der Eingabe sind, dann folgt ein Blank-Symbol. 25:01.660 --> 25:04.200 Dieses Blank-Symbol wird unverändert gelassen. 25:04.360 --> 25:09.160 Wir gehen wieder 1 zurück, an die letzte Stelle der Eingabe und in den 25:09.160 --> 25:10.000 Zustand Q2. 25:14.140 --> 25:23.440 Wenn ganz hinten eine 1 stand, wird stattdessen eine 0 geschrieben, 1 25:23.440 --> 25:28.600 nach vorne gegangen und wieder nach Q2 gegangen oder in Q2 geblieben. 25:29.780 --> 25:34.740 Und in Q2 ist, solange da eine 1 gelesen wird, passiert immer 25:34.740 --> 25:35.220 dasselbe. 25:35.440 --> 25:38.980 Es wird diese 1 durch eine 0 überschrieben und 1 nach vorne gegangen. 25:39.640 --> 25:43.720 Das geschieht so lange, bis irgendwo eine 0 gelesen wird. 25:44.520 --> 25:46.300 Diese 0 wird zu einer 1 gemacht. 25:47.900 --> 25:53.120 Noch 1 weiter nach vorne gegangen und dann nach Q3 gegangen, wo nichts 25:53.120 --> 25:56.900 anderes passiert, als dass Nullen und Einsen gelesen und unverändert 25:56.900 --> 26:00.200 gelassen werden und immer weiter nach vorne gegangen wird. 26:00.620 --> 26:05.420 Bis man an einem Blank ankommt und dieses Blank führt uns dann zum 26:05.420 --> 26:07.140 akzeptierenden Endzustand. 26:07.880 --> 26:09.540 Was wäre in dem Fall passiert? 26:09.700 --> 26:12.900 Wir haben eine Eingabe, da hinten sind Einsen. 26:13.000 --> 26:18.060 Wenn man eine 1 aufsummiert, wird die 1 zu einer 0 und man muss einen 26:18.060 --> 26:19.280 Übertrag sich merken. 26:19.480 --> 26:22.840 Das heißt, wenn eine weitere 1 kommt, wird wieder die 1 zu einer 0 und 26:22.840 --> 26:24.580 man muss sich den Übertrag merken. 26:24.700 --> 26:26.420 Und das ist das, was hier genau passiert. 26:26.980 --> 26:33.200 Solange, bis man vorne angekommen ist 26:36.900 --> 26:42.100 oder solange, bis man irgendwann die Chance hat oder irgendwann eine 0 26:42.100 --> 26:46.780 steht und da den Übertrag los wird und danach bleibt alles 26:46.780 --> 26:47.280 unverändert. 26:47.980 --> 26:53.520 Andere Möglichkeit ist, die ganze Eingabe besteht nur aus Einsen. 26:54.420 --> 26:58.320 Da würden alle diese Einsen immer durch eine 0 ersetzt, bis wir ganz 26:58.320 --> 27:03.360 vorne angekommen sind, das heißt also an dem Symbol vor der Eingabe, 27:03.820 --> 27:07.820 das ist ein Blank-Symbol, und dort unseren Übertrag loswerden, also 27:07.820 --> 27:09.600 dort dann eine 1 hinschreiben. 27:14.560 --> 27:17.180 Man könnte sagen, sie bleibt jetzt irgendwo stehen, aber die 27:17.180 --> 27:23.280 Konvention guckt sich nicht mehr den Rest der Eingabe nochmal an, aber 27:23.280 --> 27:28.660 die Konvention sagt, sie soll in jedem Fall egal, ob der Übertrag an 27:28.660 --> 27:35.140 einem Blank losgeworden wurde oder bei einer 0 losgeworden wurde, ganz 27:35.140 --> 27:37.080 nach vorne wieder gehen. 27:37.080 --> 27:38.420 Das ist richtig beobachten. 27:43.860 --> 27:47.580 Hier haben wir auch nochmal hingeschrieben, welche Funktion also 27:47.580 --> 27:48.320 realisiert wird. 27:48.640 --> 27:51.440 Ja, das ist richtig. 27:55.720 --> 27:57.600 Es steht 1 vor dem Wort. 27:58.680 --> 28:01.860 Gut, das Wort hat eine gewisse Länge, das hat irgendwie mit irgendwas 28:01.860 --> 28:02.440 gestartet. 28:03.020 --> 28:06.340 Danach steht sie auf jeden Fall 1 vor dem Wort. 28:06.560 --> 28:09.480 Also entweder wird das sozusagen das, was vor dem Wort stand, das 28:09.480 --> 28:13.800 Blank durch eine 1 überschrieben oder es bleibt unverändert. 28:13.980 --> 28:14.940 Und da steht sie. 28:21.020 --> 28:26.920 So, und die Funktion, die realisiert wird, ist eben, die Eingabe wird 28:26.920 --> 28:30.240 als Binärzahl aufgefasst und es wird eine 1 drauf addiert. 28:33.420 --> 28:38.800 Beziehungsweise, es wird eine 1 drauf addiert und es wird aber auch 28:38.800 --> 28:46.380 nur gemacht bei Binärzahlen, die so aussehen, entweder ist die 28:46.380 --> 28:53.420 Binärzahl die 0 oder eine Zahl beginnend mit einer 1. 28:56.220 --> 29:00.560 Das ist keine Einschränkung an das, was die Turing-Maschine im Prinzip 29:00.560 --> 29:06.000 kann, denn für jede Binärzahl ist im Prinzip interessant, das was 29:06.000 --> 29:07.900 passiert ab der ersten 1. 29:09.900 --> 29:13.320 Aber das ist jetzt einfach per Konvention so, dass wir sagen, hier 29:13.320 --> 29:17.100 wollen wir nur Eingaben akzeptieren, die folgendermaßen aussehen, das 29:17.100 --> 29:20.760 ist die 0 oder das ist eine Binärzahl, die mit einer 1 beginnt. 29:21.460 --> 29:25.860 Und wenn dem nicht so ist, dann ist das, was diese Turing-Maschine 29:25.860 --> 29:30.580 macht, dass sie die Eingabe auf undefiniert abbildet. 29:30.740 --> 29:37.360 Das passiert bei so einer Eingabe, die eben nicht 0 ist oder mit einer 29:37.360 --> 29:39.740 1 startet, nicht definiert ist. 29:42.380 --> 29:46.320 Und die Zustände, um das nochmal zu beschreiben, haben verschiedene 29:46.320 --> 29:46.980 Aufgaben. 29:50.940 --> 29:55.080 Innerhalb von Q1 oder solange wir in Q1 sind, passiert nichts anderes, 29:55.340 --> 29:59.160 als dass der Leseschreibkopf bis ans Ende der Eingabe geht. 29:59.980 --> 30:07.520 Q2 ist zuständig für die Bildung des Übertrags durch Addition von 30:07.520 --> 30:10.880 einer 1 zu einer bereits vorhandenen 1. 30:12.700 --> 30:17.600 Q3 ist zuständig für die Bewegung des Leseschreibkopfes nach links, 30:18.260 --> 30:22.240 nachdem eben die Aufsummierung abgeschlossen ist, also kein Übertrag 30:22.240 --> 30:23.620 mehr untergebracht werden muss. 30:24.520 --> 30:29.300 Und Q4 und Q5 sind sozusagen die Sonderbehandlung für den Fall, dass 30:29.300 --> 30:33.300 die Eingabe nur die 0 ist und F ist der akzeptierende Endzustand. 30:41.350 --> 30:44.930 Entscheidbarkeit von Sprachen und Berechenbarkeit von Funktionen kann 30:44.930 --> 30:47.130 man auch direkt als Konzepte zusammenbringen. 30:50.930 --> 30:53.530 Was heißt nochmal Entscheidbarkeit einer Sprache? 30:54.590 --> 30:59.030 Also eine Turing-Maschine akzeptiert eine Sprache, wenn sie genau auf 30:59.030 --> 31:03.030 den Eingaben aus der Sprache in einem ausgezeichneten Endzustand 31:03.030 --> 31:03.550 stoppt. 31:03.650 --> 31:06.790 Und eine Sprache heißt entscheidbar, wenn es eine Turing-Maschine 31:06.790 --> 31:10.730 gibt, die auf allen Eingaben stoppt und genau diese Sprache 31:10.730 --> 31:11.530 akzeptiert. 31:12.330 --> 31:16.330 Und andererseits heißt eine Funktion berechenbar, wenn es eine Turing 31:16.330 --> 31:20.350 -Maschine gibt, die gerade diese Funktion realisiert. 31:20.670 --> 31:26.710 Und wieso sind diese beiden Konzepte gleich? 31:27.290 --> 31:32.710 Naja gut, vielleicht machen wir jetzt erstmal eine Festlegung, die der 31:32.710 --> 31:36.090 Vereinfachung dient, wenn man über Turing-Maschinen spricht. 31:36.830 --> 31:40.330 Man kann eine Turing-Maschine, die auf allen Eingaben stoppt, immer so 31:40.330 --> 31:45.210 modifizieren, dass sie genau zwei ausgezeichnete Zustände hat, auf 31:45.210 --> 31:46.270 denen gestoppt wird. 31:46.850 --> 31:51.330 Der eine heißt Qj für Qja und der andere heißt Qn für Qnein. 31:51.970 --> 31:55.630 Und das Stoppen heißt in dem einen Fall, wenn in Qj gestoppt wird, 31:56.030 --> 31:59.150 akzeptieren und im anderen Fall, naja, nicht akzeptieren. 31:59.470 --> 32:04.830 Also wenn die Turing-Maschine bei allen Eingaben stoppt, dann kann man 32:04.830 --> 32:09.290 sozusagen für die einen, die akzeptierenden, nach Qj noch den Übergang 32:09.290 --> 32:13.150 machen und für die anderen, die nicht akzeptieren, nach Qn. 32:16.090 --> 32:20.670 Das heißt, Qj hat sozusagen die Rolle akzeptierender Endzustand und Qn 32:21.430 --> 32:24.170 die andere Möglichkeit, zu stoppen. 32:25.410 --> 32:29.310 Dann ist eine Sprache genau dann entscheidbar, wenn es eine Turing 32:29.310 --> 32:35.230 -Maschine gibt, die immer in einem dieser Zustände Qj oder Qn anhält, 32:35.430 --> 32:39.790 also egal wie die Eingabe aussieht, in Qj oder Qn anhält und gerade 32:39.790 --> 32:43.730 für die Eingaben W aus L in Qj anhält. 32:46.870 --> 32:52.050 Und mit dieser Turing-Maschine, die zwei Haltezustände kennt, einen 32:52.050 --> 32:58.130 akzeptierenden Qj und einen nicht akzeptierenden Qn, kann man 1 zu 1 32:58.130 --> 33:03.150 übersetzen in eine Turing-Maschine, die in dem einen Fall eine 1 als 33:03.150 --> 33:06.850 Ausgabe produziert und in dem anderen Fall eine 0 als Ausgabe 33:06.850 --> 33:07.610 produziert. 33:08.850 --> 33:13.850 Also dann kann man das übersetzen in eine Sprache ist entscheidbar 33:13.850 --> 33:19.030 genau dann, wenn ihre charakteristische Funktion berechenbar ist. 33:19.210 --> 33:23.930 Und charakteristische Funktion das ist gerade die Funktion, die die 33:23.930 --> 33:27.890 Worte aus L auf 1 abbildet und die anderen auf 0. 33:30.450 --> 33:34.250 Das heißt also, Berechenbarkeit dieser Funktion ist genau dasselbe wie 33:34.250 --> 33:37.930 Entscheidbarkeit der entsprechenden Sprache oder Entscheidbarkeit der 33:37.930 --> 33:44.390 Sprache L ist dasselbe wie Berechenbarkeit der charakteristischen 33:44.390 --> 33:45.710 Funktion zu L. 33:46.750 --> 33:52.470 Gut, jetzt gibt es ja auch Sprachen, vermutlich zumindest, die semi 33:52.470 --> 33:53.570 -entscheidbar sind. 33:54.650 --> 33:58.630 Da haben wir nur dieses Halten in einem ausgezeichneten Zustand für 33:58.630 --> 34:01.490 den Fall, dass die Eingabe aus der Sprache ist. 34:01.610 --> 34:04.910 Im anderen Fall kann auch passieren, dass die Turing-Maschine 34:04.910 --> 34:06.110 überhaupt nicht hält. 34:07.230 --> 34:17.630 Da wird also dann eine Funktion berechnet, die eben gerade die Wörter 34:17.630 --> 34:23.310 aus L auf 1 abbildet, aber für andere Wörter undefiniert ist. 34:27.300 --> 34:31.000 Also, entscheidbar, semi-entscheidbar und Berechenbarkeit der 34:31.840 --> 34:35.180 charakteristischen Funktion und dieser, ich sag mal, abgewandelten 34:35.840 --> 34:41.740 charakteristischen Funktion Schießstern L kann man sozusagen in 34:41.740 --> 34:42.540 Einklang bringen. 34:42.680 --> 34:45.500 Aber wir werden meistens nur über Akzeptieren von Sprachen oder nicht 34:45.500 --> 34:47.560 Akzeptieren von Sprachen reden. 34:48.740 --> 34:57.120 So, die Churchill-These, ganz wichtig, die besagt jetzt, die Menge der 34:57.120 --> 35:01.840 Turing -berechenbaren Funktionen ist genau die Menge der im intuitiven 35:01.840 --> 35:04.700 Sinne überhaupt berechenbaren Funktionen. 35:05.100 --> 35:08.020 Das ist eine These, das ist kein Satz, das kann man nicht beweisen, 35:08.720 --> 35:15.020 aber das ist eine These, die etwas darüber aussagt, ob die Turing 35:15.020 --> 35:23.040 -Maschine das Modell ist für das, was wir intuitiv sozusagen als 35:23.040 --> 35:25.580 Berechnen auffassen. 35:28.060 --> 35:34.960 Hier ist intuitiv berechenbar oder im intuitiven Sinne überhaupt 35:34.960 --> 35:42.900 berechenbare Funktion ein Begriff, der an unsere Intuition anspricht 35:42.900 --> 35:44.640 und der nicht definiert ist. 35:47.340 --> 35:50.960 Die Interpretation der Turing-Maschine sind formale Modelle für 35:50.960 --> 35:51.560 Algorithmen. 35:52.140 --> 35:55.180 Das ist letztendlich das, was uns interessiert, ein abstraktes, 35:55.320 --> 36:00.160 möglichst einfach zu beschreibendes Modell dafür, was ein Algorithmus 36:00.160 --> 36:00.600 macht. 36:01.640 --> 36:06.480 Zugegebenermaßen ist die Turing-Maschine relativ weit entfernt erstmal 36:06.480 --> 36:09.640 von dem, was wir uns unter einem Algorithmus vorstellen. 36:10.280 --> 36:14.340 Die Random Access-Maschine ist da deutlich näher dran, aber für 36:14.340 --> 36:19.660 Beweise über Berechenbarkeit oder Komplexität von Problemen ist die 36:19.660 --> 36:23.360 Turing -Maschine ein geeignetes Modell. 36:24.400 --> 36:31.340 Die Churchill-These sagt eben, ja, und die ist auch das Modell, das 36:31.340 --> 36:37.500 sozusagen den Berechenbarkeitsbegriff abstrahiert. 36:38.360 --> 36:41.960 Und sie sagt, kein Berechnungsverfahren kann algorithmisch genannt 36:41.960 --> 36:45.540 werden, wenn es nicht von einer Turing-Maschine ausführbar ist. 36:47.920 --> 36:53.220 Also nochmal, die Churchill-These ist ohne eine präzise Definition von 36:53.220 --> 36:56.640 intuitiv, berechenbar nicht beweisbar. 36:56.760 --> 36:57.540 Es ist nur eine These. 36:58.040 --> 37:00.760 Sie wird aber in der Informatik allgemein akzeptiert. 37:02.160 --> 37:09.520 Wenn man über Berechnungsmodelle spricht, dann ist die Turing-Maschine 37:09.520 --> 37:14.300 nach wie vor das Modell, das alles das, was wir uns als Computer, den 37:14.300 --> 37:20.000 man bauen kann, technisch realisieren kann, sozusagen abstrahiert. 37:20.180 --> 37:24.080 Und das bleibt auch unverändert trotz Quantencomputer oder anderer 37:24.080 --> 37:26.320 Entwicklungen oder biologischer Computer. 37:27.680 --> 37:33.840 Bisher gibt es keinen Hinweis darauf, dass es einen Rechner geben 37:33.840 --> 37:39.220 wird, Rechner in welchem Sinn auch immer, der nicht durch die Turing 37:39.220 --> 37:41.000 -Maschine abstrahiert. 37:49.860 --> 37:51.820 Das steht hier also nochmal. 37:52.320 --> 37:56.400 Keine Beispiele von Funktionen, die man intuitiv als berechenbar 37:56.400 --> 37:59.200 ansehen würde, die aber nicht Turing-berechenbar sind. 37:59.340 --> 38:00.680 Das ist die eine Seite. 38:02.680 --> 38:11.020 Und auf der anderen Seite Versuche, Modelle, Abstraktionen von echten 38:11.020 --> 38:16.280 Computern aufzustellen, die mächtiger sind als Turing-Maschinen, das 38:16.280 --> 38:17.000 fliegen alle fehl. 38:17.200 --> 38:21.780 Das führt immer wieder auf diese einfache Turing-Maschine mit ihrem 38:23.160 --> 38:25.840 Einband und ihrem Lese-Schreibkopf in ihren Zuständen, ihrer 38:25.840 --> 38:26.740 Übergangsfunktion. 38:26.940 --> 38:30.120 Das ist ja wirklich ein ganz, ganz primitives Modell. 38:34.100 --> 38:39.680 Und man kann insbesondere auch für die andersartigen Ansätze, die 38:39.680 --> 38:46.160 Abstraktionen eines Computers zu definieren, immer zeigen, was diese 38:46.160 --> 38:50.840 Maschine kann, ist entweder weniger mächtig als das, was eine Turing 38:50.840 --> 38:53.440 -Maschine kann, oder eben äquivalent zu einer Turing-Maschine, 38:54.440 --> 38:59.180 sozusagen simulierbar durch eine Turing-Maschine, wie zum Beispiel die 38:59.180 --> 39:00.040 Register -Maschine. 39:01.120 --> 39:05.840 Und einfach nur der Vollständigkeit halber dann schnell für Varianten 39:05.840 --> 39:09.020 der Turing-Maschinen, die man auch betrachten kann, die aber alle 39:09.020 --> 39:13.040 immer durch eine Einband-Turing-Maschine mit einem Lese-Schreibkopf, 39:13.280 --> 39:18.340 wie wir es hier betrachten, simuliert werden kann. 39:18.840 --> 39:22.300 Zum Beispiel eine Turing-Maschine mit einem Band, die aber mehrere 39:22.300 --> 39:23.560 Lese -Schreibköpfe hat. 39:27.620 --> 39:28.800 Meinetwegen Endstück. 39:29.660 --> 39:34.460 Die auf das Eingabeband zugreifen und durch eine endliche Kontrolle 39:34.460 --> 39:35.340 gesteuert werden. 39:36.440 --> 39:39.860 Das schlägt sich halt darin nieder, wie die Übergangsfunktion 39:39.860 --> 39:40.520 aussieht. 39:40.760 --> 39:45.620 Da hat man dann statt einem Übergang von Q kreuz Gamma einen Übergang 39:45.620 --> 39:47.780 von Q kreuz Gamma hoch N. 39:49.040 --> 39:53.020 Jeder, der N Lese-Schreibköpfe, liest irgendein Symbol aus Gamma und 39:53.020 --> 39:58.660 abhängig von diesem N-Tuppel von Symbolen und dem Zustand, in dem die 39:58.660 --> 40:00.440 Turing -Maschine ist, wird was gemacht. 40:00.900 --> 40:01.720 Und was wird gemacht? 40:01.840 --> 40:04.780 Gut, es wird mit einem neuen Zustand übergegangen und an diesen N 40:04.780 --> 40:07.820 Stellen, an denen Lese-Schreibköpfe stehen, wird das Symbol 40:07.820 --> 40:12.280 überschrieben und es wird dann mit jedem Lese-Schreibkopf nach links 40:12.280 --> 40:14.760 oder nach rechts gegangen oder gar nichts gemacht. 40:15.160 --> 40:19.340 Das heißt also, der Übergang geht nach Q kreuz Gamma hoch N kreuz 40:20.000 --> 40:25.900 Menge L für links, N für nichts, R für rechts hoch N. 40:34.840 --> 40:40.400 Ja, man könnte sich das natürlich so vorstellen, dass man diese 40:40.400 --> 40:45.040 Zustände für jeden dieser Lese-Schreibköpfe sozusagen sagt, was wird 40:45.040 --> 40:49.360 jetzt in Abhängigkeit von dem, was du jetzt liest, gemacht. 40:49.620 --> 40:51.500 Kann man als N-Tuppel auffassen. 40:52.080 --> 40:55.920 An jeder Stelle steht jeweils, wie der Zustand zu interpretieren ist, 40:56.000 --> 41:00.940 in Abhängigkeit von dem, was der entsprechende Lese-Schreibkopf liest. 41:00.940 --> 41:04.280 Und natürlich muss man hier noch ein paar weitere Festlegungen 41:04.280 --> 41:04.760 treffen. 41:05.340 --> 41:11.220 Wenn zwei Lese-Schreibköpfe an derselben Stelle stehen und der eine 41:11.220 --> 41:16.380 bei Lesen des entsprechenden Symbols vielleicht das eine schreiben 41:16.380 --> 41:19.860 würde und der andere das andere, dann gäbe es ja einen Konflikt oder 41:20.920 --> 41:21.960 haut das nicht hin. 41:22.080 --> 41:25.280 Also hier muss man natürlich dann irgendwelche Prioritätsregeln auch 41:25.280 --> 41:28.620 noch festlegen, was in so einem Fall passiert, damit das wirklich eine 41:30.560 --> 41:33.880 wohl definierte, arbeitende Turing-Maschine ist. 41:34.800 --> 41:38.700 Sie können sich genauso so ein Konzept vorstellen von einer Turing 41:38.700 --> 41:44.040 -Maschine, die mehrere Bänder hat und noch mal ein Lese-Schreibkopf, 41:44.160 --> 41:47.760 der auf jedes dieser Bänder zugreifen kann. 41:48.060 --> 41:52.200 Die Übergangsfunktion ist dann so, Delta geht von Q-Kreuz, Gamma 41:52.200 --> 41:57.480 -Kreuz, 1 bis N, 1 bis N für die N-Bänder über zu Q-Kreuz, Gamma 41:57.480 --> 42:01.880 -Kreuz, links, rechts, N-Kreuz, 1 bis N also in Abhängigkeit von dem 42:01.880 --> 42:09.800 Zustand und dem, was gelesen wird auf dem Band, wo man gerade ist wird 42:09.800 --> 42:14.240 in einen neuen Zustand übergegangen an der Stelle, an dem die Lese 42:14.240 --> 42:17.040 -Schreibkopf gerade war, ein neues Symbol geschrieben oder Symbol 42:17.040 --> 42:22.680 überschrieben, nach links oder rechts gegangen oder stehen geblieben 42:22.680 --> 42:29.200 und das möglicherweise bei einem anderen Band eins nach unten gegangen 42:29.200 --> 42:31.420 oder nach oben eins nach rechts 42:36.140 --> 42:38.860 und das kann man sich jetzt natürlich auch so vorstellen, dass man 42:38.860 --> 42:43.100 diese N-Bänder hat und für jedes Band einen eigenen Lese-Schreibkopf 42:43.100 --> 42:47.580 und dann ist die Übergangsfunktion Delta eine, die von Q-Kreuz, Gamma 42:47.580 --> 42:53.680 -Hoch, N-Kreuz, 1 bis M-Hoch, N geht nach Q-Kreuz, Gamma-Hoch, N 42:53.680 --> 43:02.840 -Kreuz, L N, R-Hoch, N-Kreuz, 1 bis M-Hoch, N oder aber das Band ist 43:02.840 --> 43:06.020 nicht nur einfach so ein eindimensionales Band, sondern ein 43:06.020 --> 43:09.600 zweidimensionales Feld und der Lese-Schreibkopf, also wir haben jetzt 43:09.600 --> 43:12.660 wieder nur einen Lese-Schreibkopf kann nicht nur nach links und rechts 43:12.660 --> 43:14.240 gehen, sondern auch nach oben und unten. 43:14.820 --> 43:18.000 Dann sieht also die Übergangsfunktion so aus. 43:18.860 --> 43:22.280 Wir haben eben nicht ein Arbeitsband, sondern ein Arbeitsfeld. 43:22.920 --> 43:24.000 Und, und, und. 43:27.080 --> 43:30.800 Das war jetzt nur mal so ganz grob, was man sich so alles vorstellen 43:30.800 --> 43:31.220 kann. 43:31.880 --> 43:35.760 Festgelegt werden muss zum Beispiel, wann so eine Mehrkopfmaschine 43:35.760 --> 43:40.840 dann wirklich stoppen würde, welcher Kopf gewinnt, wenn es irgendwie 43:40.840 --> 43:45.440 Konflikte gibt, also mehrere Lese-Schreibköpfe verschiedene Symbole an 43:45.440 --> 43:50.000 die selbe Stelle schreiben würden und so weiter. 43:50.000 --> 43:53.440 Sowas muss bei diesen Modifikationen der Einband-Turing-Maschine 43:53.750 --> 43:54.300 geklärt werden. 43:54.700 --> 43:58.920 Aber egal, wie Sie sich das sinnvoll vorstellen oder was Sie da 43:58.920 --> 44:03.500 sinnvoll im Konzept aufstellen, alle diese Modelle sind äquivalent zur 44:03.500 --> 44:05.800 normalen Turing-Maschine. 44:10.660 --> 44:14.760 Und äquivalent sein, ich gehe mal davon aus, dass das in der Übung 44:14.760 --> 44:18.220 dann auch vertieft wird, heißt, man kann das, was die eine Turing 44:18.220 --> 44:21.080 -Maschine macht, durch die andere simulieren. 44:22.720 --> 44:26.600 Also das, was irgendwie eine Mehrband-Turing-Maschine macht, durch so 44:26.600 --> 44:29.500 eine Einband-Turing-Maschine mit einem Lese-Schreibkopf, wie wir sie 44:29.500 --> 44:31.680 hier immer betrachten, simulieren. 44:35.330 --> 44:40.250 Gut, jetzt haben wir bisher, wie beim endlichen Automat, auch immer 44:40.250 --> 44:43.630 eine ganz spezifische Turing-Maschine betrachtet. 44:44.070 --> 44:47.910 Die kann eine einzige Aufgabe erfüllen, eine bestimmte Sprache 44:47.910 --> 44:51.330 akzeptieren oder nicht, eine bestimmte Funktion berechnen oder nicht. 44:51.330 --> 44:56.330 Das ist ja noch was anderes als das, was ein Computer kann, der 44:56.330 --> 44:58.850 durchaus unterschiedliche Funktionen berechnen kann. 45:01.650 --> 45:06.330 Was so eine Turing-Maschine macht, entspricht eher einem konkreten 45:06.330 --> 45:14.910 Programm oder einer Realisierung eines bestimmten Lösungsalgorithmus 45:14.910 --> 45:19.510 auf einem Chip, der genau einen bestimmten Algorithmus durchführen 45:19.510 --> 45:19.810 kann. 45:19.810 --> 45:27.810 Aber wir wollen doch über universelle Maschinen Aussagen treffen, also 45:27.810 --> 45:32.570 eine Maschine, der man ein Programm gibt, und dann eine Eingabe, auf 45:32.570 --> 45:34.050 der dieses Programm abläuft. 45:34.910 --> 45:38.050 Das ist jetzt der nächste große Schritt, dass wir die universelle 45:38.050 --> 45:42.230 Turing -Maschine definieren, die praktisch die verschiedensten 45:42.230 --> 45:45.310 konkreten Turing-Maschinen, wie wir sie bisher betrachtet haben, 45:46.750 --> 45:47.710 realisieren kann. 45:48.410 --> 45:52.190 Das heißt, diese Turing-Maschinen, die wir so bisher betrachtet haben, 45:52.290 --> 45:56.810 spezielle Turing-Maschinen, die auch so eine Binärzahl 1 addiert oder 45:56.810 --> 46:03.790 die 0 hoch n, 1 hoch n erkennen kann, als Programm auffassen und eine 46:03.790 --> 46:07.530 Turing -Maschine betrachten, die so ein Programm bekommt und dann 46:07.530 --> 46:11.030 genau das macht, was diese spezielle Turing-Maschine, die durch das 46:11.030 --> 46:15.010 Programm beschrieben wird, tun würde bei einer bestimmten Eingabe. 46:19.320 --> 46:24.260 Und um das hinzubekommen, also sozusagen das Denkmodell einer 46:24.260 --> 46:28.740 universellen Turing-Maschine, normieren wir Turing-Maschinen. 46:29.040 --> 46:32.260 Also spezielle Turing-Maschinen normieren wir in dem Sinne, dass wir 46:32.260 --> 46:35.240 sagen, naja, die sehen alle irgendwie gleichartig aus. 46:35.820 --> 46:39.180 Wir wollen ja eine spezielle Turing-Maschine im Prinzip als ein 46:39.180 --> 46:41.640 Programm ausdrücken. 46:41.820 --> 46:44.380 Das heißt, wir müssen es irgendwie kodieren als etwas, was wir der 46:44.380 --> 46:48.160 universellen Turing-Maschine als Eingabe geben. 46:48.340 --> 46:49.500 Hier, tu folgendes. 46:50.040 --> 46:55.060 Dafür also jetzt die Normierung der Turing-Maschine und Normierung 46:55.060 --> 47:02.600 heißt, naja, gewisse Festlegungen, die Zustände werden durchnummeriert 47:02.600 --> 47:07.880 von Q1 bis Qn und der erste, Q1, ist gerade der Startzustand und der 47:07.880 --> 47:12.760 zweite, Q2, ist der akzeptierende Endzustand, wenn wir sowas festlegen 47:12.760 --> 47:13.080 wollen. 47:13.080 --> 47:17.120 Und genauso wird das Eingabe-Alphabet einfach durchnummeriert. 47:17.260 --> 47:19.300 Das sind die Symbole A1 bis AK. 47:20.340 --> 47:25.520 Und für das Band-Alphabet gilt, die ersten K-Symbole sind gerade diese 47:26.360 --> 47:30.960 Symbole aus Sigma, A1 bis AK, und dann folgen die weiteren, AK plus 1 47:30.960 --> 47:31.600 bis AL. 47:34.120 --> 47:37.780 Und wenn wir das so machen, ist das natürlich keine Einschränkung der 47:37.780 --> 47:39.420 Mächtigkeit einer Turing-Maschine. 47:39.860 --> 47:44.080 Man kann bei jeder beliebigen Turing-Maschine das so hinkriegen, dass 47:44.080 --> 47:46.640 sie diese Form hat, durch Unbenennung. 47:47.480 --> 47:48.900 Anderes wird hier noch nicht gemacht. 47:50.400 --> 47:56.280 Das Gute aber ist, dass man eine so normierte Turing-Maschine kodieren 47:56.280 --> 47:57.900 kann als 0,1-Wort. 47:59.960 --> 48:01.220 Das ist jetzt ganz wichtig. 48:01.640 --> 48:09.620 Eine normierte Turing-Maschine M lässt sich eindeutig als Wort über 0 48:09.620 --> 48:13.200 ,1 Sternchen kodieren. 48:13.700 --> 48:14.720 Wie geht das? 48:16.280 --> 48:18.740 Was macht eine Turing-Maschine aus? 48:20.360 --> 48:23.200 Was die Arbeitsweise einer Turing-Maschine oder die Arbeit einer 48:23.200 --> 48:27.960 Turing -Maschine ausmacht, ist eben, welche Übergänge sie macht bei 48:27.960 --> 48:31.080 bestimmten Konfigurationen. 48:31.160 --> 48:36.460 Was ist die Konfiguration, die auf eine bestimmte Konfiguration folgt? 48:37.780 --> 48:41.100 Das heißt, wenn wir eine Turing-Maschine M haben, bestehend aus 48:41.100 --> 48:46.820 Zustandsmenge Q, Sigma, Gamma, Delta, S und F, dann wollen wir die 48:46.820 --> 48:51.840 durch 0,1 kodieren und diese 0,1-Kodierung heißt Gödelnummer von M, 48:52.540 --> 48:55.680 bezeichnet auch als M in diesen eckigen Klammern. 48:56.780 --> 49:01.380 Dann ist dafür diese Kodierung wichtig und das Entscheidende, wie die 49:01.380 --> 49:02.120 Übergänge sind. 49:02.300 --> 49:05.860 Alle denkbaren Übergänge müssen kodiert werden. 49:07.660 --> 49:10.800 Ein Übergang sieht allgemein so aus. 49:11.140 --> 49:14.920 Turing-Maschine ist in irgendeinem Zustand QI und es wird AJ gelesen. 49:15.800 --> 49:19.120 Und dieses Delta, die Übergangsfunktion, sagt was dann passiert, 49:19.340 --> 49:24.720 nämlich die Turing-Maschine geht in den Zustand QR, AJ wird durch AS 49:24.720 --> 49:29.900 überschrieben und der Lese-Schreibkopf macht eine von drei möglichen 49:32.040 --> 49:38.180 Bewegungen, links, rechts oder tue gar nichts, die man auch kodieren 49:38.180 --> 49:43.060 kann als links ist die erste Möglichkeit, also Index 1, rechts ist die 49:43.060 --> 49:47.520 zweite Möglichkeit, Index 2 und nichts tun ist die dritte Möglichkeit, 49:48.080 --> 49:48.780 Index 3. 49:49.800 --> 49:53.380 Das heißt, worauf es hier ankommt, sind ja eigentlich nur die Indizes, 49:53.600 --> 49:54.280 die da stehen. 49:55.180 --> 50:00.280 Wir haben die Zustände durchnummeriert und die Nummer des Zustands, 50:00.460 --> 50:04.240 wievielte in unserer Nummerierung bei der Nummerierung ist das, ist 50:04.240 --> 50:05.360 eigentlich nur entscheidend. 50:05.760 --> 50:10.100 Genauso bei einem Symbol, das wir lesen, das wievielte in unserer 50:10.100 --> 50:14.580 Nummerierung ist das und für das, was danach passiert, ist genauso nur 50:14.580 --> 50:17.820 entscheidend für den Zustand, in den wir gehen, der wievielte ist das 50:17.820 --> 50:19.780 denn in unserer Nummerierung. 50:19.940 --> 50:24.040 Für das Symbol, das beschrieben wird, das wievielte ist es denn aus 50:24.040 --> 50:28.920 unserem Bandalphabet und für die Aktion, die gemacht wird, die 50:28.920 --> 50:32.360 wievielte von den drei Möglichkeiten ist es eigentlich. 50:33.020 --> 50:39.120 Das heißt also, so einen Übergang kann man nummieren als so viele 50:39.120 --> 50:44.260 Nullen, wie der Index von dem Zustand ist, in dem wir uns befinden, 50:45.600 --> 50:50.480 gefolgt von einer 1, um klarzustellen, jetzt ist der Zustand codiert, 50:51.200 --> 50:56.080 gefolgt von so vielen Nullen, wie der Index des Symbols, das gerade 50:56.080 --> 51:00.360 gelesen wird, gefolgt von einer 1, um zu sagen, okay, jetzt haben wir 51:00.360 --> 51:03.680 also die Codierung von dem Zustand, in dem die Turing-Maschine ist, 51:03.980 --> 51:07.740 und die Codierung des Symbols, das sie gelesen hat, und was jetzt 51:07.740 --> 51:11.400 kommt, ist eben das, was die Folge von dem ist. 51:11.840 --> 51:15.560 Also gefolgt dann von so vielen Nullen, wie der Index des 51:15.560 --> 51:19.480 Folgezustands ist, gefolgt von einer 1, weil die Einsen haben hier nur 51:19.480 --> 51:23.960 die Funktion zu trennen, Trennsymbol zu sein, gefolgt von so vielen 51:23.960 --> 51:29.300 Nullen, wie der Index des Symbols ist, das jetzt hier geschrieben 51:29.300 --> 51:35.180 wird, also mit dem aj überschrieben wird, also s, as, 0 hoch s, 51:35.600 --> 51:40.400 gefolgt von einer 1, gefolgt von so vielen Nullen, wie der Index der 51:40.400 --> 51:42.320 Aktion ist, die jetzt gemacht wird. 51:42.860 --> 51:43.980 Das ist ganz einfach. 51:44.120 --> 51:47.340 So, und wenn Sie jetzt alle möglichen Übergänge, die die Turing 51:47.340 --> 51:52.940 -Maschine machen kann, jeweils so codieren, und in irgendeiner 51:52.940 --> 51:58.040 beliebigen Reihenfolge hintereinander schreiben und dann zwischen 51:58.040 --> 52:03.340 Codierung von einem Übergang und dem nächsten einfach nur zwei Einsen 52:03.340 --> 52:08.140 schreiben als Trennsymbol und dann vielleicht noch vorne drei Einsen, 52:08.240 --> 52:12.540 um zu zeigen, jetzt geht's los, jetzt kommt die Codierung einer Turing 52:12.540 --> 52:16.800 -Maschine und am Schluss drei Einsen, um zu codieren, und jetzt ist 52:16.800 --> 52:20.060 Schluss, jetzt ist die vollständig beschrieben, dann haben Sie die 52:20.060 --> 52:24.140 Turing -Maschine codiert durch ein Wort, das nur aus Nullen und Einsen 52:24.140 --> 52:24.780 besteht. 52:25.340 --> 52:28.460 Das ist die Gödelnummer einer Turing-Maschine. 52:29.520 --> 52:35.080 Also, Code i ist einfach der i-te Übergang von allen möglichen 52:35.080 --> 52:38.460 Übergängen, die die Turing-Maschine machen kann, nach irgendeiner 52:38.460 --> 52:43.520 beliebigen, aber festgewählten Reihenfolge der Übergänge. 52:46.080 --> 52:49.280 Codierungen einzelner Übergänge werden getrennt durch zwei Einsen, am 52:49.280 --> 52:52.720 Anfang stehen drei Einsen, am Ende stehen drei Einsen, und das ist die 52:52.720 --> 52:53.520 ganze Codierung. 52:57.940 --> 53:01.840 Das ist die Gödelnummer. 53:05.700 --> 53:09.780 Die können natürlich, die Codierungen, ziemlich lang werden, denn 53:09.780 --> 53:13.700 diese Indizes, die werden einfach durch Nullen codiert. 53:14.520 --> 53:16.520 Das ist eine Unerkodierung. 53:18.680 --> 53:21.340 Nichts mit Binär, das ist einfach unnäher kodiert. 53:22.240 --> 53:26.700 Und die Einsen, die haben eigentlich nur die Funktion, Trennsymbol zu 53:26.700 --> 53:29.960 sein, als Trennsymbol zu dienen. 53:30.400 --> 53:37.940 Jede Turing-Maschine wird auf die Art durch irgendein 01-Wort kodiert. 53:38.320 --> 53:42.400 Wenn Sie jetzt alle möglichen 01-Worte betrachten, sind da natürlich 53:42.400 --> 53:47.120 etliche drunter, die passen nicht zu einer Turing-Maschine, weil die 53:47.120 --> 53:49.720 Codierung einer Turing-Maschine fängt ja immer mit drei Einsen an. 53:50.160 --> 53:51.080 So geht es schon mal los. 53:51.320 --> 53:55.740 Und da ist noch etliches mehr, was irgendwie unpassend sein kann, wenn 53:55.740 --> 53:58.080 Sie ein beliebiges 01-Wort nehmen. 53:58.540 --> 54:04.960 Man kann aber jetzt vereinbaren, dass alle die 01-Worte, die nicht wie 54:04.960 --> 54:09.100 eine Gödelnummer aussehen, einfach eine Turing-Maschine codieren, die 54:09.100 --> 54:10.420 die leere Menge akzeptiert. 54:11.080 --> 54:16.060 Und dann haben Sie eine 1-zu-1-Beziehung zwischen 01-Worten und Turing 54:16.060 --> 54:16.540 -Maschinen. 54:19.500 --> 54:23.520 Wir vereinbaren, dass ein Wort, das keine Turing-Maschine in diesem 54:23.520 --> 54:31.340 Sinne kodiert, Y000, eine Turing-Maschine kodiert, die die leere Menge 54:31.340 --> 54:31.900 akzeptiert. 54:32.580 --> 54:37.680 So, und die universelle Turing-Maschine, die erhält jetzt als Eingabe 54:37.680 --> 54:42.060 so eine Kodierung einer speziellen Turing-Maschine, das kann man 54:42.060 --> 54:45.760 interpretieren als Programm, und dann irgendwie ein Eingabewort. 54:46.340 --> 54:52.100 Und was sie macht ist, sie simuliert diese spezielle Turing-Maschine, 54:52.440 --> 54:57.520 deren Gödelnummer sie als Eingabe bekommen hat, auf dem Eingabewort. 54:59.620 --> 55:04.540 Eine universelle Turing-Maschine erhält als Eingabe ein Paar, 55:04.980 --> 55:09.200 Gödelnummer einer Turing-Maschine, gefolgt von einem Wort W, und wir 55:09.200 --> 55:13.560 gehen jetzt immer nur noch davon aus, dass unser Eingabealphabet 0,1 55:13.560 --> 55:19.380 ist, also W ist eben auch so eine 0,1-Folge, und sie simuliert eben 55:19.380 --> 55:24.420 diese Turing-Maschine M, deren Gödelnummer sie bekommen hat, auf der 55:24.420 --> 55:25.120 Eingabe W. 55:29.260 --> 55:32.520 Hier mal einfach irgend so eine Turing-Maschine, das ist einfach ein 55:32.520 --> 55:37.360 kleines Beispiel, was keinen sonderlichen Sinn machen braucht, und wie 55:37.360 --> 55:40.940 die Codierung dieser Turing-Maschine aussieht, also wie die 55:40.940 --> 55:42.000 Gödelnummer aussieht. 55:42.120 --> 55:45.260 Hier haben wir eine Turing-Maschine mit drei Zuständen, Q1, Q2, Q3. 55:46.180 --> 55:47.960 Zwei Symbolen, 0 und 1. 55:48.140 --> 55:52.180 Jetzt die Indizierung ist, dass es A1 und das ist A2. 55:54.940 --> 55:58.760 Das Plank-Symbol wäre dann A3, kriegt den Index 3. 56:02.220 --> 56:04.780 Das Bandalphabet ist eben 0,1. 56:05.120 --> 56:08.720 Plank-Symbol, Übergangsfunktion Delta, so wie hier beschrieben. 56:09.540 --> 56:13.000 Anfangszustand Q1, akzeptierender Endzustand Q2. 56:13.180 --> 56:15.200 Und hier haben wir so ein paar konkrete Übergänge. 56:16.180 --> 56:21.300 Und wenn man die jetzt kodieren würde, dann sieht die Eingabe für die 56:21.300 --> 56:24.300 universelle Turing-Maschine folgendermaßen aus, wenn man die 56:24.300 --> 56:28.920 Gödelnummer dieser Turing-Maschine zusammen mit der Eingabe 1011 56:28.920 --> 56:30.380 dieser gäbe. 56:31.320 --> 56:35.540 Das geht los mit drei Einsen, dann kommt die Kodierung der Turing 56:35.540 --> 56:41.420 -Maschine, wo eben eine 0 dieses Q1 hier kodiert. 56:41.660 --> 56:43.540 Dann kommt eine 1 als Trend-Symbol. 56:44.180 --> 56:48.040 Dann kommen zwei Nullen, die diese 1 kodieren. 56:48.740 --> 56:53.620 Wir haben unser Bandalphabet durchnummeriert in A1, A2, A3. 56:53.720 --> 56:57.520 A1 ist die 0, A2 ist die 1, A3 ist das Plank-Symbol. 56:57.960 --> 57:01.580 Das heißt also, die 1 wird durch zwei 0 kodiert. 57:02.700 --> 57:07.340 A1 wieder als Trend-Symbol, dann kommt hier Q3, die 3 wird durch die 57:07.340 --> 57:09.360 drei Nullen kodiert. 57:09.500 --> 57:12.920 Dann kommt wieder eine 1 als Trend-Symbol, dann wird diese 0 kodiert, 57:13.060 --> 57:17.900 das ist das A1, also da kommt eine 0, dann wieder eine 1 als Trend 57:17.900 --> 57:18.300 -Symbol. 57:18.700 --> 57:22.700 Dann gehen nach rechts, das war die zweite Möglichkeit der drei 57:22.700 --> 57:26.940 Möglichkeiten, D1, D2, D3, was der Lese-Schreibkopf machen kann. 57:27.380 --> 57:33.500 Also zwei Nullen und dann sind wir mit dem ersten Code fertig. 57:34.000 --> 57:38.420 Das heißt, dann kommen zwei Einsen, um anzuzeigen, was als nächstes 57:38.420 --> 57:41.940 kommt, ist die Kodierung des zweiten Übergangs. 57:42.420 --> 57:48.940 Und dann der zweite Übergang, Delta Q3 0 gleich Q1 1 R, beginnt dann 57:48.940 --> 57:52.240 mit der Kodierung von Q3, das sind drei Nullen, dann wieder eins als 57:52.240 --> 57:55.280 Trend -Symbol, dann Kodierung von der 0, das ist eine 0, dann wieder 57:55.280 --> 57:57.400 eins als Trend-Symbol und so weiter. 57:58.400 --> 58:03.460 Und dann kommen irgendwann diese drei Einsen, die anzeigen, jetzt ist 58:03.460 --> 58:08.540 die Gödel-Nummer unserer eingegebenen Turing-Maschine fertig und was 58:08.540 --> 58:10.720 danach kommt, ist das Eingabewort. 58:12.440 --> 58:16.300 Das heißt, danach kommt dann diese 1 0 1 1, die wir hier als 58:16.300 --> 58:18.600 Eingabeball festgelegt haben. 58:19.580 --> 58:24.880 Also so sähe dann eine Eingabe für eine universelle Turing-Maschine 58:24.880 --> 58:25.360 aus. 58:25.360 --> 58:32.120 In dem Fall die Eingabe, diese Turing-Maschine mit diesem Eingabewort. 58:32.280 --> 58:35.360 Und unsere universelle Turing-Maschine kann dann mit der Information 58:35.360 --> 58:40.740 genau das machen, was diese Turing-Maschine bei dieser Eingabe tun 58:40.740 --> 58:41.080 würde. 58:41.500 --> 58:44.500 Man kann also diese Turing-Maschine auf der Eingabe 1 0 1 1 58:44.500 --> 58:45.320 simulieren. 58:49.580 --> 58:56.220 So, jetzt bezeichnen wir eine spezielle Turing-Maschine, die codiert 58:56.220 --> 59:00.700 wird durch ein Wort W aus 0 1 Sternchen, also deren Gödel-Nummer W 59:00.700 --> 59:02.680 ist, als T und W. 59:03.520 --> 59:06.280 Das ist die Turing-Maschine mit Gödel-Nummer W. 59:07.700 --> 59:11.420 Beziehungsweise, wenn das W keine Gödel-Nummer ist, die Turing 59:11.420 --> 59:13.400 -Maschine, die die Lehrermenge akzeptiert. 59:14.060 --> 59:18.640 Und L von T W ist dann die Sprache, die durch T W akzeptiert wird. 59:21.980 --> 59:30.440 Und worauf wir hinaus wollen, ist Sprachen aufzustellen, die nicht 59:30.440 --> 59:31.520 entscheidbar sind. 59:33.040 --> 59:37.260 Der erste Schritt, die erste Sprache, bei der man das machen kann, der 59:37.260 --> 59:39.760 das beweisen kann, dass sie nicht entscheidbar ist, ist die 59:39.760 --> 59:41.060 Diagonalsprache. 59:41.960 --> 59:48.020 Sie haben in der Übung das Kantor- Argument gehabt, das ist eine gute 59:48.020 --> 59:51.620 Vorbereitung für die Definition der Diagonalsprache. 59:52.860 --> 59:55.880 Für die Diagonalsprache betrachtet man folgendes. 59:55.980 --> 01:00:02.680 Man betrachtet einfach 0, 1 Worte in einer kanonischen Reihenfolge 01:00:02.680 --> 01:00:03.300 sortiert. 01:00:03.840 --> 01:00:08.180 Also sortiert nach der Länge und unter Worten gleicher Länge 01:00:10.340 --> 01:00:11.380 lexikografisch sortiert. 01:00:11.540 --> 01:00:15.040 Das heißt also, das erste ist die 0, das zweite ist die 1, das dritte 01:00:15.040 --> 01:00:20.660 ist 0, 0, das vierte ist 0, 1, dann kommt 1, 0, dann 1, 1 und so 01:00:20.660 --> 01:00:20.980 weiter. 01:00:23.420 --> 01:00:28.080 So, und wir haben also jetzt Turing-Maschinen, die durch ihre Gödel 01:00:28.080 --> 01:00:29.320 -Nummer kodiert sind. 01:00:29.440 --> 01:00:34.500 Die Turing-Maschine MJ, sagen wir, das ist die, die durch das J-Wort 01:00:34.500 --> 01:00:39.060 in dieser Sortierung der 0, 1-Worte kodiert wird. 01:00:40.480 --> 01:00:47.660 Dann kann man so eine Tabelle konstruieren, die Zeilen und die Spalten 01:00:47.660 --> 01:00:53.280 entsprechen 0, 1-Worten in dieser kanonischen Reihenfolge. 01:00:53.880 --> 01:00:58.800 Die Interpretation ist aber, die Zeilen, also die 0, 1-Worte zu den 01:00:58.800 --> 01:01:04.620 Zeilen entsprechen Eingaben und die 0, 1-Worte zu den Spalten 01:01:04.620 --> 01:01:07.200 entsprechen Gödel-Nummern. 01:01:09.440 --> 01:01:14.900 Das heißt also, wir haben Positionen i und j zwischen eins und 01:01:14.900 --> 01:01:18.980 unendlich, also nach rechts und nach unten unendliche Tabelle. 01:01:19.500 --> 01:01:28.580 Die einzelnen Positionen entsprechen solchen w, i beziehungsweise m, 01:01:28.740 --> 01:01:29.000 j. 01:01:30.420 --> 01:01:37.760 Die Zeilen solchen Eingaben wi, die Spalten solchen Turing-Maschinen 01:01:37.760 --> 01:01:38.520 m, j. 01:01:41.080 --> 01:01:46.960 Wir schreiben in die Tabelle einfach rein an der Stelle i, j ob das 01:01:46.960 --> 01:01:52.540 Wort wi von der Turing-Maschine m, j akzeptiert wird oder nicht. 01:01:53.580 --> 01:02:02.420 Also an der Position i, j steht eine 0, wenn wi nicht in der von m, j 01:02:02.420 --> 01:02:07.840 akzeptierten Sprache ist und eine 1, wenn wi in der von m, j 01:02:07.840 --> 01:02:09.360 akzeptierten Sprache ist. 01:02:09.780 --> 01:02:13.940 Und was uns interessiert, sind jetzt die Einträge auf der Diagonalen. 01:02:21.070 --> 01:02:27.730 Also für die Position i, j gilt, da steht eine 1, falls m, j wi 01:02:27.730 --> 01:02:32.550 akzeptiert und eine 0, falls m, j wi nicht akzeptiert. 01:02:33.050 --> 01:02:36.410 Und jetzt die Diagonalen angucken, dann gucken wir genau an die 01:02:36.410 --> 01:02:37.690 Positionen i, i. 01:02:39.410 --> 01:02:45.210 Diese Positionen i, i, die stehen für dasselbe Wort wi, aber 01:02:45.210 --> 01:02:51.690 einerseits als Eingabe aufgefasst, Zeile, andererseits als Gödelnummer 01:02:51.690 --> 01:02:55.070 einer Turing-Maschine aufgefasst, Spalte. 01:02:55.710 --> 01:02:59.450 Also das wi steht für das Eingabewort wi, ist aber gleichzeitig die 01:02:59.450 --> 01:03:01.150 Gödelnummer von m, i. 01:03:01.690 --> 01:03:06.690 Und wenn wir auf die Diagonale gucken, dann zeigt uns eine 1 oder 0 an 01:03:06.690 --> 01:03:15.670 so einer Stelle, ob die Turing-Maschine m, i, das Wort wi, also genau 01:03:15.670 --> 01:03:19.350 so aussieht wie die Gödelnummer dieser Turing-Maschine, akzeptiert 01:03:19.350 --> 01:03:19.870 oder nicht. 01:03:20.670 --> 01:03:26.370 Und die Diagonalsprache ist definiert als die Menge der wi, für die 01:03:26.370 --> 01:03:30.630 gilt die Turing-Maschine m, i, also die Turing-Maschine, deren 01:03:30.630 --> 01:03:36.190 Gödelnummer grad wi ist, akzeptiert die Eingabe wi nicht. 01:03:39.330 --> 01:03:45.110 Also ld, Diagonalsprache, enthält also alle wi, für die auf dieser 01:03:45.110 --> 01:03:48.530 Diagonalen an der Stelle i, i grad eine 0 steht. 01:03:52.870 --> 01:03:58.530 Diese Definition führt dann zu einem Nichtentscheidbarkeitsbeweis, der 01:03:58.530 --> 01:04:04.130 große Ähnlichkeiten zu dem Diagonal- Argument von Kantor hat. 01:04:04.890 --> 01:04:06.510 Aber gucken wir uns das jetzt einfach nochmal an. 01:04:06.770 --> 01:04:08.410 Also wie sieht unsere Tabelle aus? 01:04:09.670 --> 01:04:15.630 Wir haben unsere 0,1-Worte sortiert in lexikografischer Anordnung. 01:04:16.490 --> 01:04:21.730 Bei den Zeilen ist die Interpretation unserer 0,1-Wort ist eine 01:04:21.730 --> 01:04:26.230 Eingabe, bei den Spalten ist unsere Interpretation unserer 0,1-Wort 01:04:26.230 --> 01:04:32.330 ist eine Gödelnummer und an so einer Stelle i, j steht eine 1, wenn 01:04:32.330 --> 01:04:38.010 die Turing-Maschine mit Gödelnummer wi, j die Eingabe wi akzeptiert 01:04:38.010 --> 01:04:39.010 und 0 sonst. 01:04:39.250 --> 01:04:43.170 Und was uns interessiert für die Diagonalsprache ist nur das, was hier 01:04:43.170 --> 01:04:44.630 auf der Diagonalen steht. 01:04:45.150 --> 01:04:50.110 Also an der Stelle i, i steht eine 0, das heißt die Turing-Maschine 01:04:50.110 --> 01:04:56.110 mit Gödelnummer wi akzeptiert die Eingabe wi nicht, das heißt wi ist 01:04:56.110 --> 01:05:00.830 in der Diagonalsprache, wie die Diagonalsprache definiert ist. 01:05:01.970 --> 01:05:08.950 Und hier an der Stelle j, j steht eine 1, das heißt die Turing 01:05:08.950 --> 01:05:13.790 -Maschine mit Gödelnummer wi, j akzeptiert die Eingabe wi, j das 01:05:13.790 --> 01:05:18.750 heißt, so wie unsere Diagonalsprache definiert ist, dass wi, j nicht 01:05:18.750 --> 01:05:20.290 in der Diagonalsprache ist. 01:05:20.570 --> 01:05:23.230 Also wenn da eine 1 steht, dann ist das entsprechende Wort nicht in 01:05:23.230 --> 01:05:24.110 der Diagonalsprache. 01:05:24.390 --> 01:05:26.990 Wenn da eine 0 steht, ist es in der Diagonalsprache. 01:05:31.570 --> 01:05:36.010 Diagonalsprache ist die Menge der wi, für die gilt mi akzeptiert wi 01:05:36.570 --> 01:05:36.910 nicht. 01:05:41.170 --> 01:05:45.850 Und jetzt kann man ganz leicht zeigen, das sind nur 5 Zeilen, dass die 01:05:45.850 --> 01:05:48.110 Diagonalsprache nicht entscheidbar ist. 01:05:50.230 --> 01:05:54.170 Das ist natürlich ein Widerspruchsbeweis, man nehme an, die 01:05:54.170 --> 01:05:56.370 Diagonalsprache wäre entscheidbar. 01:05:56.490 --> 01:06:00.830 Dann gibt es eine Turing-Maschine, die stets hält und genau die Wörter 01:06:00.830 --> 01:06:02.810 aus der Diagonalsprache akzeptiert. 01:06:03.970 --> 01:06:07.170 Und diese Turing-Maschine gehört natürlich auch zu unseren Turing 01:06:07.170 --> 01:06:10.930 -Maschinen, die wir durch Gödelnummern codiert haben und die jetzt da 01:06:10.930 --> 01:06:14.590 in diesen Spalten w1 bis w irgendwas stehen. 01:06:15.370 --> 01:06:19.170 Also alle Turing-Maschinen, dazu gehört eine Gödelnummer, wenn wir 01:06:19.170 --> 01:06:23.070 diese 0,1 folgen, die eine Gödelnummer sein können oder eben eine 01:06:23.070 --> 01:06:26.210 Codierung der Turing-Maschine, die die leere Menge akzeptiert, der 01:06:26.210 --> 01:06:30.210 Reihe nach durchgehen, kommt irgendwann auch die Turing-Maschine mi, 01:06:31.090 --> 01:06:35.550 die es geben muss, wenn ld entscheidbar ist. 01:06:37.870 --> 01:06:41.450 Es geben muss, wenn ld entscheidbar ist und die eben stets hält und 01:06:41.450 --> 01:06:43.230 genau die Wörter aus ld akzeptiert. 01:06:43.750 --> 01:06:48.750 Und jetzt wenden wir diese Turing-Maschine auf die Eingabe an, die 01:06:48.750 --> 01:06:51.270 gerade der Gödelnummer dieser Turing-Maschine entspricht. 01:06:51.490 --> 01:06:54.030 Also wir wenden mi auf wi an. 01:06:54.430 --> 01:06:55.650 Da gibt es jetzt zwei Fälle. 01:06:55.650 --> 01:06:59.550 Das wi ist in der Diagonalsprache oder das wi ist nicht in der 01:06:59.550 --> 01:06:59.890 Diagonalsprache. 01:07:00.770 --> 01:07:09.030 Wenn das wi in der Diagonalsprache ist, dann wird wi deshalb von mi 01:07:09.030 --> 01:07:09.830 akzeptiert. 01:07:11.850 --> 01:07:16.870 Das ist aber ein Widerspruch dazu, dass die Diagonalsprache gerade die 01:07:16.870 --> 01:07:20.030 wi enthält, die von mi nicht akzeptiert werden. 01:07:21.610 --> 01:07:28.790 Und wenn i nicht in ld ist, dann akzeptiert mi das Wort wi wegen zwei. 01:07:30.450 --> 01:07:34.930 Das ist aber wieder ein Widerspruch zur Definition von ld. 01:07:35.770 --> 01:07:40.970 Bei ld enthält ja gerade die wi, die nicht akzeptiert werden von mi. 01:07:42.330 --> 01:07:45.510 Das heißt, wir haben da so einen Widerspruch in sich durch 01:07:45.510 --> 01:07:48.970 Selbstanwendung produziert. 01:07:49.830 --> 01:07:55.350 Das ist ein bisschen komisch, aber das ist natürlich liegt an der 01:07:55.350 --> 01:07:57.190 Definition und an dem Beweis. 01:07:57.330 --> 01:07:59.650 Das ist so ein Paradoxon, was dahinter steckt. 01:08:00.150 --> 01:08:01.750 Gucken wir uns gleich nochmal an. 01:08:02.170 --> 01:08:04.690 Aber nur der Vollständigkeit halber ist es vielleicht ein bisschen 01:08:04.690 --> 01:08:08.970 komisch, dass dieses ld gerade definiert ist, als die Menge der Worte 01:08:08.970 --> 01:08:14.010 wi, für die gilt die entsprechende Turing-Maschine mi akzeptiert wi 01:08:14.010 --> 01:08:14.430 nicht. 01:08:14.530 --> 01:08:18.330 Man hätte natürlich auch die Komplementsprache als Diagonalsprache 01:08:18.330 --> 01:08:20.310 definieren können. 01:08:20.850 --> 01:08:24.070 Das ist eher ein technischer Grund, warum man das so macht. 01:08:25.550 --> 01:08:29.350 Für die Diagonalsprache, für das Komplement der Diagonalsprache gilt 01:08:29.350 --> 01:08:32.610 natürlich genauso, dass sie nicht entscheidbar ist. 01:08:35.700 --> 01:08:40.300 Denn sie können ja einfach akzeptieren, nicht akzeptieren, für 01:08:40.300 --> 01:08:41.680 Eingaben umdrehen. 01:08:42.800 --> 01:08:46.140 Und das Prinzip, das wir hier jetzt eigentlich bei dem Beweis 01:08:46.860 --> 01:08:49.380 anwenden, ist das Prinzip, das wir ganz oft dann bei 01:08:51.760 --> 01:08:53.760 Nichtentscheidbarkeitsbeweisen anwenden, dass wir sagen, naja gut, 01:08:53.860 --> 01:08:57.740 wenn jetzt die Sprache entscheidbar wäre, dann wäre auch eine andere 01:08:57.740 --> 01:08:58.640 entscheidbar. 01:08:59.100 --> 01:09:01.820 Für die wir aber schon gezeigt haben, sie ist nicht entscheidbar. 01:09:02.340 --> 01:09:04.780 Widerspruch, also Sprache kann nicht entscheidbar sein. 01:09:05.140 --> 01:09:08.640 Das ist das Prinzip der Reduktion, wenn wir ganz, ganz, ganz oft 01:09:09.500 --> 01:09:09.940 benutzen. 01:09:10.140 --> 01:09:13.660 Also hier, um dieses Korrelat zu beweisen, nehmen wir also mal an, 01:09:14.120 --> 01:09:18.020 dass zwar ld nicht entscheidbar ist, also wir wissen, ld ist nicht 01:09:18.020 --> 01:09:21.140 entscheidbar, aber nehmen wir mal an, dass ld-Kompliment entscheidbar 01:09:21.140 --> 01:09:21.500 wäre. 01:09:22.620 --> 01:09:25.660 Falls ld-Kompliment entscheidbar ist, dann gibt es natürlich eine 01:09:25.660 --> 01:09:29.700 Turing -Maschine, die eben gerade ld-Kompliment entscheidet. 01:09:29.880 --> 01:09:33.820 Aber die können wir jetzt leicht umbauen in eine Turing-Maschine, die 01:09:33.820 --> 01:09:35.820 ld entscheidet. 01:09:36.240 --> 01:09:39.340 Wir sagen einfach, wenn diese Turing-Maschine Eingabe nicht 01:09:39.340 --> 01:09:44.400 akzeptiert, dann soll sie hierzu eine Eingabe akzeptieren und 01:09:44.400 --> 01:09:45.460 umgekehrt. 01:09:45.460 --> 01:09:50.320 Das heißt, es wäre ein klarer Widerspruch zur Unentscheidbarkeit der 01:09:50.320 --> 01:09:54.480 Diagonalsprache, wenn deren Kompliment jetzt plötzlich entscheidbar 01:09:54.480 --> 01:09:54.740 wäre. 01:09:55.040 --> 01:09:59.040 Und hier dran sehen wir schon etwas Allgemeineres, nämlich dass 01:09:59.040 --> 01:10:05.520 Entscheidbarkeit abgeschlossen ist gegenüber Komplementbildung. 01:10:06.080 --> 01:10:08.500 Wenn eine Sprache entscheidbar ist, dann auch ihr Komplement. 01:10:08.800 --> 01:10:09.580 Das muss so sein. 01:10:13.990 --> 01:10:18.010 Okay, ich habe ja eben gesagt, dass was bei der Unentscheidbarkeit der 01:10:18.010 --> 01:10:21.170 Diagonalsprache gemacht wird, das ist so ein bisschen paradox. 01:10:21.710 --> 01:10:28.250 Das ist folgende Art von Paradoxon, das dahinter steckt. 01:10:29.690 --> 01:10:30.330 Selbstbezüglichkeit. 01:10:31.410 --> 01:10:32.250 Das kennen Sie vielleicht. 01:10:32.370 --> 01:10:37.670 Der Barbier von hinter Tupfingen rasiert genau die Männer im Dorf, die 01:10:37.670 --> 01:10:39.030 sich nicht selbst rasieren. 01:10:40.390 --> 01:10:41.970 Wer rasiert den Barbier? 01:10:47.610 --> 01:10:50.730 Wie auch immer Sie das beantworten, haben wir einen Widerspruch. 01:10:52.350 --> 01:10:57.690 Oder Daniel Düsentrieb behauptet, eine allwissende Maschine erfunden 01:10:57.690 --> 01:11:02.230 zu haben und stellt eine Ja-Nein-Frage, so wie bei einer Turing 01:11:02.230 --> 01:11:05.130 -Maschine und die Antwort leuchtet auf. 01:11:06.290 --> 01:11:14.570 Jetzt kauft Dago Verdag diese Maschine, will aber nur bezahlen, wenn 01:11:14.570 --> 01:11:17.570 die Maschine auch wirklich immer korrekt antwortet. 01:11:18.770 --> 01:11:22.390 Und deshalb stellt er der Maschine die Frage, wirst du mit Nein 01:11:22.390 --> 01:11:22.670 antworten? 01:11:27.020 --> 01:11:31.980 Tja, also diese Art von Paradoxon steckt hinter der 01:11:31.980 --> 01:11:34.600 Nichtentscheidbarkeit der Diagonalsprache. 01:11:34.700 --> 01:11:38.440 Das könnte Sie jetzt natürlich dazu führen, zu sagen, naja, aber so 01:11:38.440 --> 01:11:43.760 richtig wichtige Fragen oder sinnvolle Probleme sind vielleicht doch 01:11:43.760 --> 01:11:44.640 alle berechenbar. 01:11:45.480 --> 01:11:48.760 Und das große Gegenbeispiel ist das Halteproblem. 01:11:49.140 --> 01:11:52.460 Das wissen Sie auch, das kennen Sie, Sie studieren ja Informatik. 01:11:55.040 --> 01:12:00.140 Die Frage, gegeben ein Programm und eine Eingabe, kann ich 01:12:00.140 --> 01:12:02.500 entscheiden, ob das Programm auf der Eingabe hält? 01:12:03.620 --> 01:12:04.660 Das ist das Halteproblem. 01:12:04.800 --> 01:12:05.800 Das ist ein echtes Problem. 01:12:06.100 --> 01:12:10.220 Ein echtes Problem, wenn man das entscheiden könnte, wäre sehr manches 01:12:10.220 --> 01:12:13.400 in der Informatik anders aus, als es aussieht. 01:12:13.980 --> 01:12:19.720 Und hierzu einfach mal so als grafische Vorstellung, wie sozusagen die 01:12:19.720 --> 01:12:25.720 Nichtentscheidbarkeit des Halteproblems argumentiert werden kann. 01:12:26.480 --> 01:12:33.120 Also Halteproblem, so ein Programm, das entscheiden kann, ob ein 01:12:33.120 --> 01:12:36.780 Programm auf ein vorgegebenes Programm einer vorgegebenen Eingabe 01:12:36.780 --> 01:12:40.520 hält, sähe so aus, ist wie so eine Blackbox. 01:12:40.520 --> 01:12:45.660 Da kommt eine Eingabe rein, Programm mit Eingabe, und rauskommt Ja 01:12:45.660 --> 01:12:46.200 oder Nein. 01:12:47.060 --> 01:12:50.240 Wenn wir so etwas hätten, dann könnten wir Folgendes bauen. 01:12:50.780 --> 01:12:52.840 Ein Programm Test, das sieht so aus. 01:12:53.040 --> 01:12:57.020 Da geht eine Eingabe rein, dann wird durch dieses Halt geschickt, 01:12:57.660 --> 01:12:59.080 durch dieses Programm Halt. 01:12:59.620 --> 01:13:05.620 Wenn dieses Programm Halt als Output Ja sagt, geht Test in der 01:13:05.620 --> 01:13:08.540 Endschlussschleife, hält also nicht. 01:13:08.540 --> 01:13:13.720 Und wenn Halt Nein sagt, dann stoppt Test, hält also. 01:13:15.240 --> 01:13:18.340 Und jetzt machen wir Selbstbezüglichkeit oder Anwendung auf sich 01:13:18.340 --> 01:13:18.800 selbst. 01:13:20.060 --> 01:13:28.900 Jetzt wenden wir dieses Programm auf sich selbst an, also auf Test mit 01:13:28.900 --> 01:13:29.740 einer Eingabe an. 01:13:31.020 --> 01:13:37.580 Halt kriegt diese Eingabe, wenn die Antwort ist Ja, also Test hält auf 01:13:37.580 --> 01:13:42.540 bestimmten Eingaben, die wir mitgeben, dann ist die Antwort Ja, dann 01:13:42.540 --> 01:13:45.040 geht das Ganze in der Endschlussschleife, hält nicht. 01:13:45.940 --> 01:13:51.060 Und wenn Test bei der entsprechenden Eingabe nicht hält, dann würde 01:13:51.060 --> 01:13:56.300 Halt sagen Nein, dann würde aber Test stoppen, also halten. 01:13:58.440 --> 01:14:03.780 Sie haben die gleiche Art Paradoxon oder Widerspruch wie bei dem 01:14:03.780 --> 01:14:05.340 Babier von Hintertupfingen. 01:14:06.700 --> 01:14:08.660 So und jetzt der formale Beweis dazu. 01:14:09.360 --> 01:14:12.920 Wir haben bisher nur über Sprachen und Akzeptieren von Sprachen 01:14:12.920 --> 01:14:13.520 gesprochen. 01:14:13.700 --> 01:14:16.580 Wir haben auch Realisieren von der Funktion mal betrachtet, aber 01:14:16.580 --> 01:14:20.160 eigentlich werden wir fast immer in der Vorlesung, auch wenn wir 01:14:20.160 --> 01:14:25.440 später über echte Probleme reden, ein Konzept zugrunde legen, bei dem 01:14:25.440 --> 01:14:31.040 Probleme formuliert werden als wird eine Sprache akzeptiert oder 01:14:31.040 --> 01:14:31.380 nicht. 01:14:31.780 --> 01:14:34.420 Das heißt also zum Halteproblem brauchen wir jetzt eine Sprache. 01:14:34.980 --> 01:14:38.580 Und die Sprache, die das Halteproblem beschreibt, sieht folgendermaßen 01:14:38.580 --> 01:14:38.940 aus. 01:14:39.280 --> 01:14:46.220 Das ist die Menge der Wörter WV, für die gilt, die Turingmaschine mit 01:14:46.220 --> 01:14:49.700 Gödelnummer W hält auf der Eingabe V. 01:14:50.540 --> 01:14:56.320 Sind also kombinierte Worte WV und da sind in der Sprache zum 01:14:56.320 --> 01:15:00.560 Halteproblem gerade die kombinierten Worte drin, für die gilt, die 01:15:00.560 --> 01:15:05.860 Turingmaschine zum ersten Teil des Wortes hält auf der Eingabe, die so 01:15:05.860 --> 01:15:08.180 aussieht wie der zweite Teil des Wortes. 01:15:08.780 --> 01:15:12.340 Dann kann man die Nichtentscheidbarkeit dieser Sprache leicht 01:15:12.340 --> 01:15:19.080 beweisen, also Interpretation ist, diese Sprache entscheiden heißt das 01:15:19.080 --> 01:15:23.780 Problem, aber eine Turingmaschine auf einer Eingabe stoppt ist nicht 01:15:23.780 --> 01:15:24.480 entscheidbar. 01:15:25.900 --> 01:15:34.800 Wieder Prinzip der Reduktion, also wir führen die Annahme, die Sprache 01:15:34.800 --> 01:15:39.780 zum Halteproblem wäre entscheidbar, zu einem Widerspruch, in dem wir 01:15:40.580 --> 01:15:44.780 folgern, dann wäre auch eine der Sprachen, von denen wir schon wissen, 01:15:44.940 --> 01:15:47.940 dass sie nicht entscheidbar sind, entscheidbar. 01:15:49.040 --> 01:15:53.020 Und zwar benutzen wir hier die Komplementsprache der Diagonalsprache. 01:15:53.620 --> 01:15:58.140 Also angenommen, es existiert eine stets haltende Turingmaschine, die 01:15:58.140 --> 01:16:01.120 gerade die Sprache zum Halteproblem entscheiden kann. 01:16:02.100 --> 01:16:06.060 Also wenn das hier nicht stimmt, also H entscheidbar ist, dann muss es 01:16:06.060 --> 01:16:06.600 sowas geben. 01:16:07.700 --> 01:16:11.200 Daraus konstruieren wir jetzt eine stets haltende Turingmaschine, die 01:16:11.200 --> 01:16:14.880 die Komplementsprache der Diagonalsprache entscheidet und das wäre ein 01:16:14.880 --> 01:16:17.700 Widerspruch zu dem Corolla, was wir gerade hatten. 01:16:18.980 --> 01:16:23.440 So, sei jetzt W eine Eingabe, für die wir eben entscheiden wollen, ob 01:16:23.440 --> 01:16:25.900 W in dem Komplement der Diagonalsprache ist. 01:16:26.300 --> 01:16:32.420 Dann könnten wir mit dieser stets haltenden Turingmaschine zu H 01:16:32.420 --> 01:16:33.500 folgendes machen. 01:16:33.820 --> 01:16:39.080 Wir berechnen erstmal das I, sodass die Eingabe gerade das I-te Wort 01:16:39.080 --> 01:16:41.380 in unserer Sortierung der 0,1-Worte ist. 01:16:42.240 --> 01:16:46.520 Wir betrachten die durch W I kodierte Turingmaschine, MI heißt sie, 01:16:47.120 --> 01:16:53.440 und wir wenden H auf Kodierung von MI gefolgt von W I an. 01:16:56.700 --> 01:16:57.860 So, was passiert dann? 01:16:59.680 --> 01:17:03.580 Naja gut, also das MI W I wird entweder akzeptiert oder nicht 01:17:03.580 --> 01:17:04.160 akzeptiert. 01:17:04.660 --> 01:17:08.140 Falls MI W I nicht akzeptiert wird, was heißt das? 01:17:09.620 --> 01:17:13.120 Das heißt, dann hält MI nicht auf W I. 01:17:15.020 --> 01:17:20.880 Nach Definition von der Sprache des Halteproblems ist also das W I in 01:17:20.880 --> 01:17:25.940 der Diagonalsprache und damit nicht im Komplement der Diagonalsprache. 01:17:27.920 --> 01:17:35.480 Und andererseits, falls MI W I akzeptiert wird durch die 01:17:35.480 --> 01:17:41.580 Turingmaschine zum Halteproblem, dann hält MI auf W I, dann können wir 01:17:41.580 --> 01:17:47.160 aber auf der universellen Turingmaschine die Berechnung von MI auf W I 01:17:47.160 --> 01:17:48.500 vollständig simulieren. 01:17:49.320 --> 01:17:53.820 Das heißt also, wir haben diese Annahme wir haben so eine stets 01:17:53.820 --> 01:17:58.980 haltende Turingmaschine für die Sprache H zu einem Widerspruch dazu 01:17:58.980 --> 01:18:03.780 geführt, dass die Komplementsprache der Diagonalsprache nicht 01:18:03.780 --> 01:18:04.680 entscheidbar ist. 01:18:04.820 --> 01:18:08.400 Indem wir gesagt haben, die könnte man dann aber auch benutzen, um LD 01:18:08.400 --> 01:18:09.720 Komplement zu entscheiden. 01:18:12.560 --> 01:18:16.040 Da müssen Sie sich dran gewöhnen, das ist ein bisschen schwere Kost, 01:18:16.780 --> 01:18:20.340 aber diese Beweise, diese Nichtentscheidbarkeitsbeweise sind 01:18:20.340 --> 01:18:25.720 typischerweise ganz kurz, wenige Argumente, aber Sie müssen sozusagen 01:18:25.720 --> 01:18:32.620 dieses Prinzip der Reduktion, angenommen die Sprache von der ich 01:18:32.620 --> 01:18:38.020 beweisen will, sie ist nicht entscheidbar, wäre entscheidbar, 01:18:40.220 --> 01:18:43.560 zurückgeführt auf, dann ist eine andere Sprache, von der wir schon 01:18:43.560 --> 01:18:46.640 bewiesen haben, sie ist nicht entscheidbar, entscheidbar, also diese 01:18:46.640 --> 01:18:50.220 Art von Widerspruchsbeweis die müssen Sie, ich sag mal so, 01:18:50.580 --> 01:18:51.120 verinnerlichen. 01:18:51.740 --> 01:18:52.900 Das ist eigentlich alles. 01:18:54.180 --> 01:18:56.280 So, und das ist jetzt auch alles für heute.