WEBVTT 00:11.130 --> 00:13.930 Dann, Endspurt, letzte Vorlesung. 00:14.030 --> 00:15.190 Was haben wir heute noch vor? 00:16.450 --> 00:20.250 Heute werden wir auf alle Fälle noch das Kapitel Touringmaschinen zu 00:20.250 --> 00:23.210 Ende bringen und je nachdem, ob wir danach noch ein bisschen Zeit 00:23.210 --> 00:28.550 haben oder nicht, werden wir noch so ein, zwei kleine Dinge zum Thema 00:28.550 --> 00:29.690 Relationen besprechen. 00:30.290 --> 00:32.670 Das sehen wir dann, je nachdem, wie wir mit der Zeit durchkommen. 00:35.450 --> 00:38.510 Wir waren letztes Mal stehen geblieben bei der Platzkomplexität. 00:38.510 --> 00:41.530 Wir hatten uns zuerst angeschaut, die Zeitkomplexität zu einer 00:41.530 --> 00:42.310 Touringmaschine. 00:43.030 --> 00:46.050 Also, wie viele Zeitschritte brauche ich bis zu einer 00:46.050 --> 00:49.110 Endkonfiguration, wenn ich ein Eingabewort W habe? 00:49.730 --> 00:57.410 Was ist die maximale Laufzeit für ein beliebiges Wort der Länge N? 00:57.830 --> 01:03.050 Und das Gleiche machen wir halt mit der Anzahl der besuchten Zellen 01:03.050 --> 01:03.990 auf dem Band. 01:03.990 --> 01:07.610 Also die maximale Anzahl an Zellen, auf die ich einmal den Kopf 01:07.610 --> 01:12.970 bewege, auch wieder in Abhängigkeit erstmal von einem Wort W und dann 01:12.970 --> 01:16.750 das Maximum über alle Wörter einer bestimmten Länge N. 01:18.870 --> 01:27.370 Gut, also, auf wie viele Felder wird der Kopf während der Eingabe nach 01:27.370 --> 01:31.470 der Eingabe des Wortes W bis zum Halten mindestens einmal besucht? 01:34.050 --> 01:40.990 Das heißt also, die mindeste Raumkomplexität, die ich brauche, ist 01:40.990 --> 01:45.070 mindestens die Länge des Eingabewortes plus dann noch zusätzlich, was 01:45.070 --> 01:47.410 ich alles weitere benötige. 01:48.130 --> 01:51.310 Also, wie gesagt, gehen Sie ruhig rüber, wenn Sie da schlecht wären. 01:54.050 --> 01:56.930 Wenn man sich das jetzt für die Palindromerkennung anschaut, da 01:56.930 --> 01:58.450 brauche ich ein zusätzliches Feld. 01:58.590 --> 02:02.410 Das ist, wenn ich einmal nach rechts rüber düse, dann düse ich einmal 02:02.410 --> 02:06.330 über das letzte Zeichen ganz am Anfang des Wortes hinüber. 02:07.590 --> 02:17.410 Genau, also Palindromerkennung brauchen wir halt eins mehr als das 02:17.410 --> 02:20.630 Eingabewort, das wir hatten und ansonsten bleiben wir innerhalb der 02:20.630 --> 02:22.930 Grenzen des ersten Eingabewortes. 02:25.570 --> 02:28.570 Genauso kann man sich überlegen, was ist der Zusammenhang mit der 02:28.570 --> 02:29.630 Zeitkomplexität? 02:29.630 --> 02:38.810 Wenn jetzt also so die Turingmaschine E nur T-Zeitschritte macht, dann 02:38.810 --> 02:43.730 kann ich auch höchstens 1 plus Time W-Felder besuchen, weil am Anfang 02:43.730 --> 02:47.730 stehe ich auf einem Feld und ich kann maximal nach jedem Schritt den 02:47.730 --> 02:48.790 Kopf noch einen bewegen. 02:48.950 --> 02:51.310 Das heißt, nach dem letzten Schritt darf ich den Kopf noch einmal 02:51.310 --> 02:58.410 bewegen und dann habe ich also maximal diese Zeitkomplexität von 1 02:58.410 --> 02:58.830 plus. 03:02.830 --> 03:07.970 Daraus kann man halt ableiten, dass also der Zeitbedarf so etwas wie 03:07.970 --> 03:12.810 eine obere Schranke des Platzbedarfes ist, also mehr geht nicht. 03:13.350 --> 03:16.030 Das heißt also insbesondere, wenn ich was mit polynomialer Laufzeit 03:16.030 --> 03:19.510 habe, dann habe ich auch einen polynomiellen Platzbedarf. 03:21.650 --> 03:24.970 Umgekehrt funktioniert das halt leider nicht. 03:25.090 --> 03:29.210 Ich kann natürlich etwas mit polynomiellen Platzbedarf haben, aber 03:29.210 --> 03:33.890 trotzdem mit exponentieller Zeitkomplexität, indem ich einfach ganz 03:33.890 --> 03:40.950 häufig über das Wort drüber gehe und da Zeichen innerhalb des ersten 03:40.950 --> 03:42.550 Wortes ersetze und so weiter. 03:45.690 --> 03:51.870 Dementsprechend, je nachdem wie häufig ich so ein Feld anfasse, ändert 03:51.870 --> 03:55.150 sich zwar nicht die Raumkomplexität, wenn es immer dieselben Felder 03:55.150 --> 03:59.330 sind, aber die Zeitkomplexität kann trotzdem sehr lang sein. 04:03.360 --> 04:08.880 Jetzt kann man halt das Ganze in Komplexitätsklassen zusammenfassen 04:08.880 --> 04:15.460 für Turing-Maschinen, so ähnlich wie wir das bei der Laufzeit von 04:15.460 --> 04:16.560 Algorithmen gemacht haben. 04:16.620 --> 04:20.560 Da haben wir auch Komplexitätsklassen mithilfe des O und des Theta und 04:20.560 --> 04:26.240 des Omega-Kalküls gebildet und jetzt machen wir das Ganze für Turing 04:26.240 --> 04:31.420 -Maschinen und haben dann aber deutlich gröbere Klassen, in die wir 04:31.420 --> 04:32.080 eingrenzen. 04:32.960 --> 04:36.260 Wir schauen uns also an, können wir eine Schranke, eine obere 04:36.260 --> 04:42.160 Schranke, für Zeit- und Raumkomplexität oder beides angeben und dann 04:42.160 --> 04:45.880 kann man das machen, zum Beispiel für Turing-Maschinen und kann sich 04:45.880 --> 04:50.400 überlegen, welche formalen Sprachen gibt es, die von einer Turing 04:50.400 --> 04:54.140 -Maschine entschieden werden können und bei denen halt die 04:54.140 --> 04:57.380 Zeitkomplexität innerhalb einer bestimmten Klasse ist und bei der die 04:57.380 --> 05:00.400 Raumkomplexität innerhalb einer bestimmten Klasse ist. 05:00.800 --> 05:04.560 Also welche formalen Sprachen können entschieden werden in zum 05:04.560 --> 05:12.260 Beispiel O von n hoch 3 und brauchen dabei Raum maximal sowas wie O 05:12.260 --> 05:13.680 von n hoch 3 halbe log n. 05:14.480 --> 05:17.080 Und dann wie immer, wie wir das bei Algorithmen hatten, n die Länge 05:17.080 --> 05:21.000 der Eingabe, also bei uns n die Länge des Eingabewortes. 05:21.900 --> 05:25.040 Wichtig ist hier, es geht um das Entscheiden. 05:25.820 --> 05:29.900 Das heißt, diese Turing-Maschinen müssen halten, weil sonst kann ich 05:29.900 --> 05:32.420 die Sprache nicht entscheiden, das kann ich nur machen, wenn die 05:32.420 --> 05:33.540 Turing -Maschine hält. 05:34.040 --> 05:37.100 Im anderen Fall hatten wir unter Umständen von Aufzählbarkeit 05:37.100 --> 05:42.340 gesprochen und deswegen war halt die Vorbemerkung, dass wir immer noch 05:42.340 --> 05:45.000 in diesem Abschnitt sind, wo wir uns nur mit Turing-Maschinen 05:45.000 --> 05:47.780 beschäftigen, die auch wirklich immer halten. 05:49.800 --> 05:54.420 Und dann kann man halt Komplexitätsklassen aufbauen und dann hat man 05:54.420 --> 05:58.800 halt diese beiden wichtigen Komplexitätsklassen P und P-Space. 05:59.480 --> 06:03.060 Und man spricht jetzt halt von P, wenn man die Menge aller formalen 06:03.060 --> 06:06.620 Sprachen sich anschaut, die jetzt von einer Turing-Maschine in 06:06.620 --> 06:09.620 polynomialer Zeit entschieden werden können. 06:11.400 --> 06:13.820 Und genauso macht man das bei P-Space. 06:13.820 --> 06:17.800 Das sind alle formalen Sprachen, die von einer Turing-Maschine 06:17.800 --> 06:22.420 entschieden werden können, deren Raumkomplexität polynomial ist. 06:23.460 --> 06:26.840 Wenn man jetzt dieses Palindrom nimmt, das Palindrom ist 06:26.840 --> 06:33.420 offensichtlich in P und man kann auch andere Turing-Maschinen bauen, 06:33.560 --> 06:36.920 die zum Beispiel die Äquivalenz regulärer Ausdrücke überprüfen, die 06:36.920 --> 06:40.660 wären dann in P-Space, die kann man in P-Space einordnen. 06:41.580 --> 06:42.220 Wichtig. 06:43.280 --> 06:48.080 Früher haben wir die Laufzeit von Algorithmen besprochen. 06:48.980 --> 06:54.800 Hier haben wir jetzt Zeit- und Raumkomplexitätsklassen, die zwar was 06:54.800 --> 06:57.940 mit Turing-Maschinen zu tun haben, die aber bezogen werden auf 06:57.940 --> 06:58.540 Sprachen. 06:59.380 --> 07:03.140 Wir teilen also nicht Turing-Maschinen in diese Komplexitätsklassen 07:03.140 --> 07:07.480 ein, sondern wir teilen Sprachen in die Komplexitätsklassen ein. 07:07.480 --> 07:12.400 Nur die Einteilung erfolgt dessen, ob es eine Turing-Maschine gibt, 07:12.540 --> 07:14.820 die das halt kann oder eben nicht. 07:17.220 --> 07:20.980 Wir hatten schon gesehen, wenn man polynomielle Laufzeit hat, dann hat 07:20.980 --> 07:25.180 man offensichtlich nur polynomiellen Platzbedarf. 07:25.680 --> 07:30.060 Das heißt also, die Menge aller Sprachen, die in P liegen, das ist 07:30.060 --> 07:31.860 eine Teilmenge von P-Space. 07:35.430 --> 07:39.210 Aber umgekehrt muss man vorsichtig sein. 07:39.510 --> 07:43.690 Es ist halt die Frage, ob das geht, weil also eine Turing-Maschine, 07:44.430 --> 07:48.690 wie wir uns überlegt haben, mit polynomielem Platzbedarf kann durchaus 07:48.690 --> 07:50.290 exponentiell viele Schritte machen. 07:50.430 --> 07:51.990 Also solche Turing-Maschinen gibt es. 07:52.770 --> 07:55.450 Jetzt ist das die Frage, wir brauchen jetzt hier aber Turing 07:55.450 --> 08:01.330 -Maschinen, die Sprachen entscheiden. 08:01.330 --> 08:02.610 Das ist das Erste. 08:03.350 --> 08:06.210 Und zweitens nicht irgendwelche Turing-Maschinen, sondern wir gucken 08:06.210 --> 08:10.130 uns ja da Mengen von Sprachen an, für die es eine Turing-Maschine 08:10.130 --> 08:14.010 gibt, die das in polynomieler Zeit oder in polynomieler 08:14.010 --> 08:16.490 Raumkomplexität entscheiden können. 08:17.710 --> 08:21.290 Nur weil ich, sagen wir mal, für eine Sprache bisher keine Turing 08:21.290 --> 08:25.890 -Maschine gefunden habe, die das kann, heißt das ja noch lange nicht, 08:25.990 --> 08:28.010 dass so eine Turing-Maschine nicht existiert. 08:28.830 --> 08:31.890 Das heißt, da ist es jetzt also extrem schwierig, die umgekehrte 08:31.890 --> 08:39.070 Beweisführung zu führen, weil man da den allgemeinen Fall 08:39.070 --> 08:42.410 berücksichtigen müsste, eine arbiträre Turing-Maschine für diese 08:42.410 --> 08:46.530 Sprache, ob jede Sprache, die diese Turing-Maschine entscheidet, jetzt 08:46.530 --> 08:50.410 in P-Space ist oder eben nicht in den P-Space und in P ist oder eben 08:50.410 --> 08:55.810 nicht in P. Deswegen, es kann sein, selbst wenn ich jetzt halt Turing 08:55.810 --> 09:01.170 -Maschinen habe, die exponentielle Laufzeit haben, aber nur 09:01.170 --> 09:04.510 polynomiellen Platzbedarf, kann es trotzdem sein, dass P-Space 09:04.510 --> 09:05.730 Teilmenge von P ist. 09:06.370 --> 09:08.630 Es kann ja sein, dass es eine andere Turing-Maschine gibt, die das 09:08.630 --> 09:12.550 gleiche macht, die die gleichen Sprachen erkennt, aber halt schneller 09:12.550 --> 09:15.030 als die, die ich bisher kenne. 09:16.370 --> 09:19.730 Deswegen ist es halt wichtig, es geht bei P und P-Space um die 09:19.730 --> 09:22.830 Sprachen, die da drin liegen und nicht um die Turing-Maschinen. 09:24.670 --> 09:27.530 Und das weiß man halt im Augenblick noch nicht. 09:27.930 --> 09:31.610 Ist also P gleich P-Space oder ist P ungleich P-Space? 09:34.070 --> 09:39.290 Die eine Teilmengenrelation, die man jetzt für den Beweis für 09:39.290 --> 09:42.270 Gleichheit oder auch für Ungleichheit bräuchte, von der weiß man, dass 09:42.270 --> 09:48.210 es gilt, aber die umgekehrte Teilmengenrelation, die weiß man halt, 09:48.310 --> 09:49.150 die kennt man nicht. 09:50.750 --> 09:53.470 Okay, also zum Thema Zeit und Komplexität. 09:53.610 --> 09:56.010 Sie sollten halt wissen, was ist Zeitkomplexität, was ist 09:56.010 --> 10:01.250 Raumkomplexität, dieses Kleintime, Großtime, Kleinspace, Großspace 10:01.250 --> 10:01.570 kennen. 10:02.010 --> 10:06.350 Sie sollten wissen, was es mit P und P-Space auf sich hat, dass es 10:06.350 --> 10:08.950 dabei um Mengen von Sprachen geht. 10:10.070 --> 10:14.030 Und halt hier im Hinterkopf wissen, wenn Sie sich als theoretischer 10:14.030 --> 10:17.670 Informatiker einen Namen machen wollen, könnten Sie zum Beispiel das 10:17.670 --> 10:18.110 beweisen. 10:18.110 --> 10:21.410 Und da gibt es durchaus Leute, die da immer kontinuierlich dran 10:21.410 --> 10:21.790 arbeiten. 10:22.930 --> 10:25.730 Und dann sollten, wenn man halt so eine Turing-Maschine vor sich hat 10:25.730 --> 10:29.810 oder auch selber eine Turing-Maschine konstruiert hat, sollte man sich 10:29.810 --> 10:34.070 immer im Klaren sein, dass man weiß, in welcher Zeit und welcher 10:34.070 --> 10:38.470 Raumkomplexität läuft die Turing-Maschine und in welche der beiden 10:38.470 --> 10:45.870 Klassen würde eine Sprache vielleicht reinfallen können, die jetzt von 10:45.870 --> 10:47.910 dieser Turing-Maschine zum Beispiel erkannt wird. 10:50.030 --> 10:51.750 Jetzt schalten wir wieder um. 10:52.230 --> 10:56.610 Ab sofort kümmern wir uns auch wieder um Turing-Maschinen, die nicht 10:56.610 --> 10:56.990 halten. 10:57.470 --> 10:59.990 Das heißt, wir kümmern uns jetzt nicht nur um Turing-Maschinen, die 10:59.990 --> 11:03.950 Sprachen entscheiden, sondern um Turing-Maschinen, die halt auch nur 11:03.950 --> 11:07.490 Sprachen aufzählen oder irgendwas anderes machen und nicht 11:07.490 --> 11:13.130 notwendigerweise halten, sondern für immer und ewig vorangehen können. 11:14.730 --> 11:22.450 Und jetzt kommt etwas sehr Schönes, was man jetzt zeigen kann, wenn 11:22.450 --> 11:26.370 man sich jetzt also um Laufzeitskomplexität und Raumkomplexität nicht 11:26.370 --> 11:32.270 kümmert, dann kann man eine Turing-Maschine bauen, die alle anderen 11:32.270 --> 11:34.530 Turing -Maschinen ausführt. 11:35.950 --> 11:38.910 Jetzt kann man sich so überlegen, so eine Turing-Maschine operiert ja 11:38.910 --> 11:42.830 relativ einfach, da gibt es so einen Satz von Regeln, da gibt es diese 11:42.830 --> 11:48.470 partiellen Funktionen, die muss ich ja im Prinzip nur immer 11:48.470 --> 11:52.050 implementieren, berechnen und dann kann ich eine Turing-Maschine 11:52.050 --> 11:53.230 ausführen. 11:53.610 --> 11:57.530 Also kann ich ja natürlich auch eine Turing-Maschine ausführen, die 11:57.530 --> 12:01.110 diese Funktionen berechnet, die halt immer ausrechnet, was ist die 12:01.110 --> 12:04.170 neue Bandbeschriftung, in welche Richtung habe ich den Kopf bewegt, 12:04.770 --> 12:06.310 geht es weiter, geht es nicht weiter. 12:07.870 --> 12:11.990 Und damit man das jetzt machen kann, braucht man halt irgendwie eine 12:11.990 --> 12:17.030 Kodierung, eine Beschreibung einer beliebigen Turing-Maschine, die ich 12:17.030 --> 12:20.950 dann auf das Band dieser universellen Turing-Maschine schreibe und 12:20.950 --> 12:24.370 dann liest die universelle Turing-Maschine diese Beschreibung ein, 12:25.310 --> 12:29.930 liest zusätzlich dann noch ein Eingabewort ein und dann simuliert es 12:29.930 --> 12:32.830 diese Turing-Maschine, die ich da aufs Band geschrieben hatte und 12:32.830 --> 12:37.490 führt das aus, was diese Turing-Maschine, die ich beschrieben habe, 12:37.570 --> 12:41.270 normalerweise ausführen würde und sagt mir dann hinterher, wenn sie 12:41.270 --> 12:44.930 denn hält, was ist die Endbeschriftung des Bandes und die 12:44.930 --> 12:45.930 Endkonfiguration. 12:46.890 --> 12:49.550 Um das machen zu können, muss man natürlich jetzt erstmal irgendwie 12:49.550 --> 12:54.230 eine geeignete Beschreibung der Turing-Maschine hinbekommen. 12:55.050 --> 12:58.870 Und das kann man sich überlegen, kann man relativ einfach machen, dass 12:58.870 --> 13:04.310 man so eine Turing-Maschine als Wort aus verschiedenen Zeichen 13:04.310 --> 13:04.950 hinschreibt. 13:05.510 --> 13:08.330 Wenn Sie jetzt mit Programmiersprachen denken, dann ist das so etwas 13:08.330 --> 13:10.030 ähnliches wie Objektrealisierung. 13:10.170 --> 13:14.130 Dann stellen Sie sich halt eine Turing-Maschine vor als ein Objekt und 13:14.130 --> 13:18.890 die Attribute des Objektes sind eben gerade die Definitionen des 13:18.890 --> 13:25.850 Bandalphabetes, der Beschriftung des Bandes und die einzelnen 13:25.850 --> 13:30.090 Funktionen, die Kopfbewegungsfunktion, die Zustandsübergangsfunktion 13:30.090 --> 13:36.330 und die Ausgabefunktion und müssen das jetzt serialisieren, also als 13:36.330 --> 13:38.190 Wort seriell hinschreiben. 13:38.850 --> 13:42.170 Dann nehmen wir uns halt ein Alphabet her, da tun wir halt rein, 13:42.290 --> 13:45.010 Klammer auf, Klammer zu, 0 und 1. 13:46.890 --> 13:50.110 Theoretisch würde sogar reichen 0 und 1, aber wir wollen es uns 13:50.110 --> 13:54.590 einfach machen, machen wir halt Klammer auf, Klammer zu, 0 und 1. 13:54.930 --> 14:00.110 Wenn man es ganz kompakt halten wollte, würde 1 auch reichen, weil man 14:00.110 --> 14:04.170 nämlich dann immer noch das Blank-Symbol mit hinzunehmen kann und also 14:04.170 --> 14:06.010 bestimmte Felder nicht beschriftet hat. 14:10.430 --> 14:16.470 Was wir jetzt letztendlich machen, geht in die Richtung der 14:16.470 --> 14:17.210 Gödelisierung. 14:17.930 --> 14:22.990 Also wir serialisieren diese Turing-Maschine und wollen am Ende 14:22.990 --> 14:30.370 zeigen, dass es bestimmte Probleme gibt, die ich nicht berechnen kann. 14:30.370 --> 14:33.970 Dass es insbesondere Entscheidungsprobleme gibt, die ich nicht 14:33.970 --> 14:36.270 algorithmisch berechnen kann. 14:40.370 --> 14:43.010 Angenommen, ich habe jetzt so eine Turing-Maschine, Zustandsmenge, 14:43.090 --> 14:47.510 Anfangszustand, Bandalphabet, dann leeres Blank-Symbol gehört auch 14:47.510 --> 14:51.070 immer dazu und dann meine drei Funktionen, dann muss ich halt als 14:51.070 --> 14:52.690 erstes die Zustände codieren. 14:53.330 --> 14:57.050 Kann ich ab von 0 an durchnummerieren? 14:59.750 --> 15:04.150 Kann ich dann jede Zahl, jede natürliche Zahl im Binärcode darstellen? 15:04.310 --> 15:07.410 Komme ich also mit 0 oder 1 zurecht? 15:07.670 --> 15:09.810 Kann ich binär codieren? 15:10.730 --> 15:15.870 Was ist, wenn ich jetzt die einzelnen Zustände voneinander abtrennen 15:15.870 --> 15:17.590 will, wenn ich die aufs Band draufschreibe? 15:18.450 --> 15:19.630 Eckige Klammern drum. 15:19.770 --> 15:21.550 Habe ich einen Trenner. 15:22.350 --> 15:25.930 Kann ich also dann sagen, der erste Zustand, wenn ich halt maximal 15:25.930 --> 15:34.730 acht Zustände habe, wenn ich maximal zwei hoch vier Zustände habe, 15:35.230 --> 15:40.430 richt halt hier mal die 0, dann 001 und so weiter und so fort. 15:46.130 --> 15:49.650 Dann kann ich auch noch bedenken, okay, ich kann mir, muss mir jetzt 15:49.650 --> 15:51.630 das Eingabealphabet genauso codieren. 15:51.690 --> 15:53.850 Das Eingabealphabet ist Gott sei Dank auch endlich. 15:55.490 --> 16:00.030 Nummeriere die Symbole in dem Eingabealphabet, nicht Eingabe, in dem 16:00.030 --> 16:02.330 Bandalphabet irgendwie der Reihe nach durch. 16:02.950 --> 16:06.270 Schreibt das Ganze wieder im Binärcode hin, das Leerzeichen, das Blank 16:06.270 --> 16:10.110 -Symbol habe ich immer, das kriegt halt den Code 0 und alle anderen 16:10.110 --> 16:13.550 kriegen dann durchnummeriert den jeweiligen Code und schreibe da 16:13.550 --> 16:15.150 wieder Klammern drum. 16:18.060 --> 16:21.460 Dann Kopfbewegung hat halt drei verschiedene Funktionswerte. 16:22.300 --> 16:26.620 Minus 1, 0, plus 1 kann ich mir auch im Binärcode hinschreiben. 16:28.920 --> 16:33.600 Reichen dann zwei Bits für, mache ich wieder eckige Klammern drum. 16:36.120 --> 16:39.700 Muss ich jetzt noch mich drum kümmern, dass ich die einzelnen 16:39.700 --> 16:42.480 Funktionswerte der drei Funktionen codiere. 16:43.040 --> 16:46.180 Und das kann ich ja wiederum machen mit der Codierung der Zustände, 16:46.360 --> 16:50.340 mit der Codierung der Alphabetzeichen und mit der Codierung des 16:50.340 --> 16:52.500 Ergebnisses der Kopfbewegungsfunktion. 16:53.340 --> 16:58.180 Ich muss halt immer hinschreiben dann, wenn ich jetzt für meine drei 16:58.180 --> 17:07.300 Funktionen das habe, erst den Funktionswert, dann den Wert, also erst 17:07.300 --> 17:10.840 das Argument der Funktion, dann den Wert der Funktion für das 17:10.840 --> 17:16.740 jeweilige Paar aus Zustand und Eingabe Alphabetzeichen und kann dann 17:16.740 --> 17:17.900 einfach den Wert hinschreiben. 17:18.520 --> 17:23.920 Und da ich ja die vorher schon durchnummeriert habe, die Eingabe, die 17:23.920 --> 17:27.980 Bandalphabetzeichen, die Zustände, brauche ich auch gar nicht mehr die 17:27.980 --> 17:29.880 Argumente der Funktionen hinzuschreiben. 17:30.300 --> 17:33.560 Sondern ich sage einfach, okay, in der Reihenfolge, wie die vorkommen, 17:33.660 --> 17:36.500 habe ich mir halt ein System, wie ich die mal miteinander kombiniere. 17:36.920 --> 17:41.120 Dann habe ich eine Reihenfolge aller möglichen Argumente für die drei 17:41.120 --> 17:44.640 Funktionen und dann brauche ich nur in derselben Reihenfolge halt 17:44.640 --> 17:47.500 immer die drei Funktionswerte hinzuschreiben. 17:48.280 --> 17:52.240 Und muss das Ganze dann außen nochmal mit externen Klammern versehen, 17:52.320 --> 17:57.020 damit ich weiß, dieser Teil ist dafür zuständig, dass ich hier die 17:57.020 --> 17:59.480 bestimmten Funktionen kodiere. 18:03.280 --> 18:06.880 Und dann habe ich die Codes der einzelnen Teile, die ich für die 18:06.880 --> 18:10.380 Turing -Maschine habe und die muss ich dann einfach hintereinander auf 18:10.380 --> 18:11.180 das Band schreiben. 18:12.740 --> 18:16.380 Jetzt kann ich das zum Beispiel einfach schön nach einer Konvention 18:16.380 --> 18:19.600 klammern, damit ich immer weiß, wo fängt welcher Teil an, wo fängt 18:19.600 --> 18:21.080 welcher Teil auf. 18:21.600 --> 18:24.620 Oder ich kann auch solche anderen Dinge machen, wie, dass ich als 18:24.620 --> 18:28.320 erstes erstmal kodiere, wie viele Zustände habe ich. 18:28.880 --> 18:32.520 Dann kodiere ich, wie viele Zeichen in meinem Alphabet habe ich. 18:33.360 --> 18:35.740 Das rahme ich halt dann noch durch Klammern ein. 18:37.120 --> 18:40.600 Und ab da brauche ich dann eigentlich gar keine Klammern mehr, weil ab 18:40.600 --> 18:45.660 da ist die Länge der einzelnen Felder dann schon ab da bestimmt. 18:45.800 --> 18:50.760 Ab da weiß ich, wie viel Platz, wie viele Zeichen auf dem Band für die 18:50.760 --> 18:53.600 einzelnen Teile, für die Kodierung des Alphabets, für die Kodierung 18:53.600 --> 18:58.180 der Zustände und der Funktionen überhaupt notwendig sind. 18:58.560 --> 19:00.040 Könnte ich mir auch die Klammern sparen. 19:00.440 --> 19:04.000 Oder ich lasse halt die Klammern da, dann ist es einfacher lesbar. 19:04.620 --> 19:08.780 Aber man sieht also, auf diese Weise kann man auf relativ einfache Art 19:08.780 --> 19:13.860 und Weise eine beliebige Turing-Maschine, die ich mir ausgedacht habe, 19:14.420 --> 19:18.460 über diesem Alphabet auf das Band einer anderen Turing-Maschine 19:18.460 --> 19:19.200 draufschreiben. 19:20.420 --> 19:24.100 Wenn ich eine Turing-Maschine T habe und die kodiere ich nach dieser 19:24.100 --> 19:26.620 Art und Weise, dann nenne ich halt die Kodierung dieser Turing 19:26.620 --> 19:27.540 -Maschine T W. 19:28.220 --> 19:31.220 Das Wort, das ich aus dieser Turing-Maschine gemacht habe. 19:32.600 --> 19:34.700 Jetzt kann man verschiedene Sachen damit machen. 19:35.420 --> 19:39.260 Das Erste, was man machen kann, ist, man kann sich ein beliebiges Wort 19:39.260 --> 19:44.240 W über diesem Alphabet Klammer 01 anschauen und man kann erstmal 19:44.240 --> 19:49.320 analysieren, ist das ein Wort, das eine Turing-Maschine beschreibt, es 19:49.320 --> 19:53.200 ist also eine gültige Kodierung einer Turing-Maschine oder ist es das 19:53.200 --> 19:53.540 nicht. 19:55.440 --> 19:58.380 Das ist etwas, was man relativ leicht machen kann. 19:58.380 --> 20:03.020 Und dann kann man eben diese besagte universelle Turing-Maschine 20:03.020 --> 20:05.460 bauen. 20:06.380 --> 20:10.640 Diese universelle Turing-Maschine, da schreibe ich zwei Wörter auf das 20:10.640 --> 20:11.600 Band als Eingabe. 20:12.480 --> 20:18.100 Das erste Wort W1 kann die Kodierung einer beliebigen Turing-Maschine 20:18.100 --> 20:24.260 sein und das Wort W2 kann dann die Eingabe für diese Turing-Maschine, 20:24.260 --> 20:30.100 die ich mit dem Wort W1 kodiert habe, darstellen. 20:30.720 --> 20:33.960 Und die universelle Turing-Maschine kann als erstes erstmal 20:33.960 --> 20:40.260 überprüfen, ist W1 eine gültige Kodierung einer Turing-Maschine? 20:40.760 --> 20:46.720 Dann überprüft es, ist W2 auch eine gültige Kodierung einer Eingabe 20:46.720 --> 20:47.780 für diese Turing-Maschine? 20:47.780 --> 20:53.840 Also besteht es auch nur aus Zeichen, die in dem Alphabet der Turing 20:53.840 --> 20:56.120 -Maschine, die durch W1 beschrieben wird, vorkommen. 20:56.780 --> 21:01.620 Und wenn das so ist, dann führt es das aus. 21:02.060 --> 21:05.340 Wenn es nicht so ist, dann macht es halt nichts, aber wenn das beides 21:05.340 --> 21:09.400 zutrifft, dann simuliert es jetzt halt Schritt für Schritt die Turing 21:09.400 --> 21:12.680 -Maschine, die durch W1 beschrieben wird und die als Eingabe W2 21:12.680 --> 21:13.400 bekommen hat. 21:14.300 --> 21:20.400 Und die hält halt dann, wenn die Turing-Maschine T, die durch W1 21:20.400 --> 21:23.940 beschrieben wird, für Eingabe W2 hält und ansonsten hält sie nicht und 21:23.940 --> 21:28.380 produziert halt fortlaufend die Konfiguration, die Folgekonfiguration 21:28.380 --> 21:29.420 von dieser Turing-Maschine. 21:33.580 --> 21:38.820 Und was man sich jetzt fragen kann, ist für eine beliebige Turing 21:38.820 --> 21:46.080 -Maschine, wenn ich da ein Wort aus dem Alphabet der Turing-Maschine 21:46.080 --> 21:51.500 auf das Band schreibe, hält die oder hält die nicht? 21:56.150 --> 22:00.190 Und die Frage lautet, die man sich stellt, die Frage lautet, kann ich 22:00.190 --> 22:01.990 sowas berechnen? 22:03.490 --> 22:07.730 Und um sich das mal anzuschauen, kann man dieses Halteproblem noch ein 22:07.730 --> 22:09.270 bisschen schärfer formulieren. 22:09.270 --> 22:13.290 Und das ist so, wie es hier in der Vorlesung hingeschrieben wird. 22:13.750 --> 22:16.810 Und wenn Sie in der Literatur schauen, was ich Ihnen dringend rate, 22:16.910 --> 22:20.110 dass Sie auch in die Literatur reinschauen, finden Sie manchmal für 22:20.110 --> 22:23.110 dieses Halteproblem, so wie es hier hingeschrieben ist, den Begriff 22:23.110 --> 22:25.510 des spezifischen Halteproblems. 22:25.910 --> 22:31.130 Und das spezifische Halteproblem besagt halt, es ist eine Menge, es 22:31.130 --> 22:37.010 ist eine Menge aller derjenigen Wörter w über diesem Alphabet 0, 1, 22:37.270 --> 22:43.190 eckige Klammer auf und zu, für die das Wort zum einen die kultige 22:43.190 --> 22:49.570 Kodierung einer Turing-Maschine ist und die, wenn sie sich selber ihre 22:49.570 --> 22:53.570 eigene Kodierung als Eingabewort bekommt, hält. 22:54.690 --> 23:00.410 Das heißt, es ist also eine Turing-Maschine, die, wenn ich sie kodiere 23:00.410 --> 23:04.310 und diese Kodierung auf das Band schreibe und dann diese Turing 23:04.310 --> 23:09.030 -Maschine auf ihrer eigenen Kodierung loslaufen lasse, irgendwann nach 23:09.030 --> 23:10.170 endlicher Zeit hält. 23:12.930 --> 23:16.290 Und der Satz ist jetzt, die Überhauptung ist, dass dieses 23:16.290 --> 23:22.170 Halteproblem, diese Sprache H, diese formale Sprache H, unentscheidbar 23:22.170 --> 23:22.470 ist. 23:23.170 --> 23:27.310 Wir erinnern uns, entscheidbar heißt, dass es eine Turing-Maschine 23:27.310 --> 23:34.370 gibt, die für jedes Wort aus der Sprache, wenn ich es auf das Band 23:34.370 --> 23:38.430 schreibe, in einem akzeptierenden Zustand hält und für jedes Wort, das 23:38.430 --> 23:43.370 nicht in der Sprache drin ist, in einem nicht akzeptierenden Zustand 23:43.370 --> 23:43.670 hält. 23:44.250 --> 23:45.730 Aber sie hält immer. 23:47.530 --> 23:50.770 Und diese Sprache, diese formale Sprache ist jetzt, soll jetzt das 23:50.770 --> 23:54.930 Beispiel sein für eine Sprache, die eben nicht entscheidbar ist, für 23:54.930 --> 23:58.390 die ich eben keine Turing-Maschine finde, die das so macht. 24:01.070 --> 24:04.370 Die Konsequenz daraus ist, und das muss man sich klar machen, das 24:04.370 --> 24:08.270 klingt jetzt erstmal trivial und unentscheidbar, aber die Konsequenz 24:08.270 --> 24:12.470 daraus ist, dass man damit relativ leicht zeigen kann, dass es 24:12.470 --> 24:15.990 Probleme gibt, die man algorithmisch nicht lösen kann. 24:16.730 --> 24:22.550 Dass es also Probleme gibt, für die Sie kein Programm schreiben 24:22.550 --> 24:26.170 können, sodass Ihr Rechner dieses Problem löst, dass Ihr Rechner 24:26.170 --> 24:28.870 dieses Problem berechnen kann. 24:29.690 --> 24:32.610 Und dieses Halteproblem klingt ja jetzt relativ einfach. 24:32.770 --> 24:35.490 Man muss erstmal gucken, ist das eine Kodierung einer Turing-Maschine 24:35.490 --> 24:39.230 und dann muss man die Turing-Maschine analysieren und gucken, ob diese 24:39.230 --> 24:42.470 Turing -Maschine halt für jedes beliebige Wort, nicht nur für jedes 24:42.470 --> 24:46.050 beliebige Wort, nur für dieses eine spezielle Wort überhaupt hält. 24:46.850 --> 24:51.170 Und schon das ist etwas, was wir nicht berechnen können, für das wir 24:51.170 --> 24:55.590 keinen Algorithmus angeben können, der das löst. 24:57.350 --> 25:02.290 Wenn Sie sich erinnern, wir hatten irgendwann mal in der Vorlesung mal 25:02.290 --> 25:03.030 drüber gesprochen, 25:06.170 --> 25:11.690 über die Physiker, die mal den Rechencluster von der Universität lange 25:11.690 --> 25:15.390 Zeit belegt hatten und keiner durfte rechnen, weil die ihre supergroße 25:15.390 --> 25:19.490 Simulation haben laufen lassen und das dauerte zwei Wochen und dann 25:19.490 --> 25:23.310 stellten sich irgendwann heraus, also wir kriegen da kein vernünftiges 25:23.310 --> 25:26.370 Ergebnis, diese Simulation konvergiert nicht, da kommt nur Quatsch 25:26.370 --> 25:29.550 raus und hört nicht auf und wir kommen nicht mal in die Nähe einer 25:29.550 --> 25:32.590 Lösung, bis dann irgendeiner auf die Idee gekommen ist, sich das 25:32.590 --> 25:35.850 genauer anzuschauen und festgestellt hat, ja, das Problem können wir 25:35.850 --> 25:36.510 nicht lösen. 25:38.950 --> 25:43.250 Und das ist durchaus etwas, was man sich immer im Hinterkopf behalten 25:43.250 --> 25:48.730 muss, wenn man von irgendjemandem ein Problem gestellt bekommt, wenn 25:48.730 --> 25:51.450 man sich selber ein Problem gestellt bekommt oder von externen 25:51.450 --> 25:55.210 Problemen gestellt bekommt, dass es durchaus mal sein kann, dass sich 25:55.210 --> 25:56.790 das Problem gar nicht lösen kann. 25:57.510 --> 26:03.250 Das wird man nicht immer beweisen können, aber es gibt auch so ein 26:03.250 --> 26:09.990 paar offensichtliche Probleme, für die man das beweisen kann und die 26:09.990 --> 26:11.750 gar nicht mal so praxisfern sind. 26:12.270 --> 26:15.010 Ich meine, Sie haben ja alle jetzt die Programmieren-Vorlesung 26:15.010 --> 26:19.710 kennengelernt, dass Sie ein bisschen schon mal programmieren können 26:19.710 --> 26:22.910 und Sie können sich jetzt vorstellen, an der Universität interessiert 26:22.910 --> 26:26.630 es einem häufig auch, ob Programme zum Beispiel korrekt sind. 26:27.870 --> 26:30.710 Und da haben Sie jetzt so etwas wie das Vorkalkül kennengelernt, da 26:30.710 --> 26:33.590 haben Sie festgestellt, das ist nicht wirklich sonderlich praktikabel, 26:34.130 --> 26:37.890 um wirklich zu beweisen, dass ein Programm, ein Algorithmus genau das 26:37.890 --> 26:39.690 macht, was er soll. 26:39.690 --> 26:42.730 Bloß die Programme, die Sie schreiben, sind ja eigentlich mehr als so 26:42.730 --> 26:44.150 simple Algorithmen. 26:44.490 --> 26:47.870 Die gehen ja manchmal über diese Einschränkungen, die wir dem Begriff 26:47.870 --> 26:50.330 Algorithmus erst mal aufgelegt haben, darüber hinaus. 26:51.270 --> 26:54.470 Und dann lernen Sie irgendwann später mal in der Software-Technik so 26:54.470 --> 26:59.430 Standard -Techniken, um potenzielle Fehler in einem Programm finden zu 26:59.430 --> 26:59.670 können. 27:00.910 --> 27:04.110 Und da sind dann so typische Sachen drin, so einfache Sachen. 27:04.210 --> 27:07.510 Ich gucke mal, werden Variablen deklariert, die nirgendwo verwendet 27:07.510 --> 27:07.770 werden? 27:07.770 --> 27:11.050 Dann weise ich mal den Benutzer darauf hin, ob er da vielleicht 27:11.050 --> 27:13.510 irgendwie einen Fehler gemacht hat, einen Denkfehler. 27:14.190 --> 27:16.910 Im einfachsten Fall hat er halt mal ein paar Variablen zu viel 27:16.910 --> 27:22.790 deklariert, im schlimmsten Fall hat er mal irgendwo einen Denkfehler 27:22.790 --> 27:23.170 gemacht. 27:23.830 --> 27:26.250 Und man kann ihn da so ein bisschen drauf hin stupsen, dass er nochmal 27:26.250 --> 27:26.570 guckt. 27:27.390 --> 27:32.050 Eine andere Standard-Technik, zu überprüfen, ob ein Programm 27:32.050 --> 27:35.010 vielleicht Probleme enthalten könnte, sind die sogenannten 27:35.010 --> 27:36.110 Abdeckungstests. 27:37.070 --> 27:42.050 Bei diesen Abdeckungstests wollen Sie überprüfen, ob überhaupt 27:42.050 --> 27:45.210 sämtliche Programmzeilen mal ausgeführt werden. 27:46.210 --> 27:48.390 Das hängt natürlich von der Eingabe ab, die Sie haben. 27:48.750 --> 27:50.750 Das hängt davon ab, welche Eingabe Sie reingeben. 27:51.830 --> 27:56.590 Und dann wollen Sie halt gucken, gibt es Programmteile, irgendwelche 27:56.590 --> 28:00.930 Zweige in IF-Schleifen, irgendwelche Schleifen, irgendwelche 28:00.930 --> 28:04.210 Funktionen, die überhaupt nie aufgerufen werden und überhaupt nie 28:04.210 --> 28:04.990 verwendet werden. 28:05.530 --> 28:07.010 Egal bei welcher Eingabe. 28:07.410 --> 28:09.870 Und das ist meistens dann ein Hinweis darauf, dass da wohl irgendwo 28:09.870 --> 28:12.430 ein Denkfehler zu sein scheint, weil warum hat der da Code 28:12.430 --> 28:15.250 hingeschrieben für einen Fall, der eigentlich nie sein darf. 28:16.730 --> 28:22.890 Und das ist so ein beliebtes Analysewerkzeug, Überlappungstests, 28:23.510 --> 28:26.410 Abdeckungstests laufen zu lassen. 28:26.410 --> 28:29.690 Und das funktioniert meistens so, ich generiere mir halt zufällige, 28:29.850 --> 28:32.650 gültige Eingaben und lasse das Programm durchlaufen und gucke mal, 28:32.730 --> 28:34.530 welche Codezeilen werden alle ausgeführt. 28:35.030 --> 28:37.390 Und wenn ich das häufig genug mache, gibt es vielleicht Codezeilen, 28:37.490 --> 28:38.570 die nicht ausgeführt werden. 28:39.550 --> 28:42.310 Und jetzt könnten Sie bei einer Softwarefirma arbeiten, die halt 28:42.310 --> 28:46.950 Software für so Fehlersuche in Programmen macht. 28:46.950 --> 28:50.470 Und dann kommt Ihr findiger Chef und sagt, das ist doch völliger 28:50.470 --> 28:57.090 Quark, dass man da zufällige Werte draufschießt und dann immer das 28:57.090 --> 29:01.190 Programm durchlaufen lässt und dann durch rumstochern und ausprobieren 29:01.190 --> 29:04.090 guckt, ob es vielleicht Programmteile gibt, die nie ausgeführt werden. 29:04.510 --> 29:06.490 Vielleicht habe ich ja nur die falschen Eingaben generiert. 29:06.930 --> 29:10.130 Es wäre doch viel schicker, wenn man ähnlich sowas wie einen Compiler, 29:10.250 --> 29:13.530 ein anderes Programm hat, das analysiert das Programm und guckt, gibt 29:13.530 --> 29:16.630 es da Programmteile, die gar nicht benötigt werden. 29:18.070 --> 29:21.070 Und wenn dann jemals Sie so einen Chef haben, der zu Ihnen kommt und 29:21.070 --> 29:23.870 sagt, hier, das schreiben wir jetzt, das wäre doch das super 29:23.870 --> 29:28.570 Softwareanalyse -Tool, das würde jeder haben, dann wissen Sie, dass 29:28.570 --> 29:32.330 Sie sich gar nicht mehr an die Arbeit zu machen brauchen, weil man 29:32.330 --> 29:36.190 kann auch zeigen, dass das etwas ist, was eben nicht entscheidbar ist. 29:36.190 --> 29:43.550 Es ist nicht entscheidbar, ob bestimmte Teile des Programms in einem 29:43.550 --> 29:47.750 allgemeinen Programm, insbesondere in so einer allgemeinen Turing 29:47.750 --> 29:50.870 -Maschine, jemals ausgeführt werden oder nicht. 29:51.270 --> 29:55.190 Das ist auch eines dieser typischen Probleme, die nicht entscheidbar 29:55.190 --> 29:55.350 sind. 29:55.490 --> 29:58.790 Das heißt, es wäre völlig vergebene Liebesmühle, jetzt zu versuchen, 29:58.890 --> 30:00.030 so ein Programm zu entwickeln. 30:00.030 --> 30:01.430 Es geht einfach nicht. 30:02.830 --> 30:07.530 Das heißt, das ist mit eines der aller, allerwichtigsten Dinge, die 30:07.530 --> 30:10.530 Sie aus dieser Vorlesung mitnehmen müssen. 30:10.750 --> 30:14.110 Es gibt Probleme, die Sie nicht algorithmisch lösen können. 30:14.950 --> 30:19.330 Nicht alles, was wir gerne berechnen und ausführen lassen wollen, 30:19.890 --> 30:22.430 können wir auch notwendigerweise mit einem Rechner machen. 30:22.530 --> 30:24.370 Der Rechner ist da eingeschränkt. 30:25.150 --> 30:30.070 Und wenn Sie später mal irgendwann nach dem Master weitermachen wollen 30:30.070 --> 30:35.210 und ganz tief in die Informatik einsteigen wollen, dann gibt es da 30:35.210 --> 30:39.670 tatsächlich sogar ein Feld, ein Forschungsfeld, das sich damit 30:39.670 --> 30:42.510 beschäftigt, wie wir dieses Problem loswerden können. 30:42.870 --> 30:47.070 Was kann man machen, dass man also auch die Probleme berechnen kann, 30:47.490 --> 30:52.830 die wir im Augenblick nicht berechnen können, die wir nicht lösen 30:52.830 --> 30:53.070 können. 30:53.070 --> 30:55.050 Und dann ist die offensichtliche Antwort, naja, mit einer Turing 30:55.050 --> 30:56.070 -Maschine geht es nicht. 30:56.150 --> 30:58.210 Wir brauchen was anderes als eine Turing-Maschine. 30:58.850 --> 31:01.670 Und dann kommen Sie in den Bereich des sogenannten Super-Turing 31:01.670 --> 31:02.430 -Computings. 31:07.360 --> 31:11.500 Das klingt abstrus, aber es ist gar nicht mal so abstrus. 31:11.620 --> 31:13.700 Da, wenn Sie mal hin und wieder selbst so in die 31:13.700 --> 31:17.360 populärwissenschaftliche Literatur reinschauen, da fallen auch solche 31:17.360 --> 31:19.480 Dinge drunter wie analoge Rechner. 31:21.000 --> 31:24.280 Weil mit dem Digitalrechner sind wir naturgemäß beschränkt in der 31:24.280 --> 31:27.640 Genauigkeit, mit der wir mit reellen Zahlen zum Beispiel umgehen 31:27.640 --> 31:29.520 können, selbst mit rationalen Zahlen. 31:31.080 --> 31:34.900 Und um davon wegzukommen, gibt es halt das Konzept des analogen 31:34.900 --> 31:38.580 Rechners, der theoretisch hoffentlich mit beliebiger Genauigkeit 31:38.580 --> 31:39.220 rechnen kann. 31:39.560 --> 31:42.040 Und das ist so eine der Beschränkungen, die wir halt überkommen 31:42.040 --> 31:45.100 müssen, damit wir von diesem Problem wegkommen. 31:47.040 --> 31:50.340 Es ist natürlich die interessante Frage, wie kann man sowas beweisen? 31:50.480 --> 31:56.060 Wie kann man beweisen, dass es keine Turing-Maschine gibt, die dieses 31:56.060 --> 31:59.060 spezifische alte Problem entscheidet? 32:00.040 --> 32:01.600 Und jetzt kommt das Interessante. 32:01.700 --> 32:06.600 Das Ganze kann man zurückführen auf eine Idee von Kantor. 32:07.280 --> 32:13.020 Und das ist eine Idee, die Sie wahrscheinlich schon in höherer 32:13.020 --> 32:17.320 Mathematik oder gegebenenfalls sogar in der Schule, in den 32:17.320 --> 32:21.260 Mathekursen, in der Oberstufe kennengelernt haben. 32:21.960 --> 32:25.900 Und die Idee, die dahinter steckt, ist die gleiche Idee wie bei der 32:25.900 --> 32:27.820 Aufzählung der rationalen Zahlen. 32:28.640 --> 32:31.240 Sie werden sich vielleicht erinnern, man hat mal die Unterscheidung 32:31.240 --> 32:36.020 gemacht zwischen abzählbaren und nicht überabzählbaren Mengen. 32:36.020 --> 32:38.300 Sie werden vielleicht noch wissen, ja, die Menge der rationalen 32:38.300 --> 32:39.560 Zahlen, die ist abzählbar. 32:39.980 --> 32:43.780 Die Menge der reellen Zahlen ist überabzählbar. 32:44.780 --> 32:48.660 Und um zu zeigen, dass die Menge der rationalen Zahlen abzählbar war, 32:49.200 --> 32:52.060 hatten Sie so ein einfaches Verfahren kennengelernt, in dem Sie 32:52.060 --> 32:57.000 sämtliche rationalen Zahlen einfach der Reihe nach aufzählen können. 32:57.180 --> 33:00.680 Verfahren, mit dem Sie die rationalen Zahlen, die es gibt, der Reihe 33:00.680 --> 33:02.160 nach hinschreiben können. 33:02.160 --> 33:05.120 Und die Idee dabei war ja so eine rationale Zahl. 33:05.300 --> 33:09.140 Die Division war ja natürlich in Zahlen. 33:09.620 --> 33:10.940 Also mache ich mir so eine Matrix. 33:11.540 --> 33:16.000 Oben die natürlichen Zahlen von 1 bis, auf der senkrechten die 33:16.000 --> 33:17.720 natürlichen Zahlen von 1 bis. 33:18.560 --> 33:22.880 Und in jede Zelle dieser Matrix schreibe ich halt die rationale Zahl 33:22.880 --> 33:26.560 rein, die sich ergibt durch Zahl, die in der Spalte steht, geteilt 33:26.560 --> 33:27.960 durch Zahl, die in der Zeile steht. 33:27.960 --> 33:33.700 Und dann gehe ich so diagonal durch diese Matrix durch und habe damit 33:33.700 --> 33:38.400 einen linearen Pfad, der letztendlich alle Werte in dieser Matrix 33:38.400 --> 33:39.700 durchlaufen wird. 33:39.780 --> 33:42.620 Und auf diesem linearen Pfad habe ich halt die Anordnung, die 33:42.620 --> 33:44.320 Reihenfolge der rationalen Zahlen. 33:46.300 --> 33:49.100 Das kann man jetzt erweitern auf beliebige Funktionen. 33:49.660 --> 33:56.220 Also die Idee dieser Diagonalisierung ist, oben in die Zeile, da 33:56.220 --> 33:59.600 schreibe ich halt die Namen von Werten hin. 34:03.860 --> 34:08.360 Und um über die Spalten und die Zeilen schreibe ich die Namen von 34:08.360 --> 34:09.220 Funktionen hin. 34:10.060 --> 34:13.400 Und diese Funktionen können halt aufgezählt werden, können der Reihe 34:13.400 --> 34:14.540 nach aufgezählt werden. 34:14.700 --> 34:19.920 Und oben die Zahlen können auch der Reihe nach aufgezählt werden, sind 34:19.920 --> 34:23.740 indiziert über die natürlichen Zahlen. 34:24.520 --> 34:28.920 Und in den Eintrag der Spalte schreibe ich halt immerhin den 34:28.920 --> 34:33.740 Funktionswert von der iden Funktion auf das j-Wort angewandt. 34:34.620 --> 34:36.140 So wie das hier drin steht. 34:37.940 --> 34:41.480 Und da das Verfahren Diagonalisierung heißt, scheint wohl die 34:41.480 --> 34:43.600 Diagonale relativ interessant zu sein. 34:46.450 --> 34:48.250 Die Diagonale sieht so aus. 34:48.330 --> 34:49.990 Das sind die Werte der Diagonalen. 34:49.990 --> 34:54.470 Da steht halt drauf, für den Wert w0 kommt halt der Funktionswert f0 34:54.470 --> 34:55.130 von w0. 34:55.550 --> 35:00.150 Für den Wert w1 kommt halt der Funktionswert f1 von w1 und so weiter 35:00.150 --> 35:00.770 und so fort. 35:01.430 --> 35:04.670 Jetzt kann ich diese Diagonale als Zeile hinschreiben. 35:05.530 --> 35:08.990 Das heißt, diese Zeile selber ist ja auch wieder eine Funktion. 35:09.230 --> 35:11.510 Nennen wir diese Funktion d wie Diagonale. 35:12.770 --> 35:19.210 Das kann durchaus dann eine Funktion sein, die halt irgendwo auch in 35:19.210 --> 35:20.230 dieser Matrix vorkommt. 35:20.330 --> 35:23.850 Das ist halt die Funktion, die halt dem Wort w0 den gleichen Wert 35:23.850 --> 35:29.130 zuweist wie f0 und dem Wort w1 den gleichen Wert zuweist wie f1 und so 35:29.130 --> 35:30.050 weiter und so fort. 35:31.690 --> 35:38.770 Und jetzt konstruiere ich die sogenannte verdorbene Diagonale. 35:38.770 --> 35:42.290 Ich konstruiere eine zweite Funktion, die nenne ich dquer. 35:43.130 --> 35:48.090 Und diese Funktion dquer, die soll halt gerade so aussehen, dass sie 35:48.090 --> 35:51.650 der Wert fi von wi quer ist. 35:52.350 --> 35:57.270 Das soll heißen, dass diese Funktion den Wert 1 bekommt, falls die 35:57.270 --> 36:01.050 ursprüngliche Funktion, also falls die d-Funktion, den Wert 0 hat. 36:01.310 --> 36:05.430 Also falls fi von wi gleich 0 ist und ansonsten 1. 36:05.430 --> 36:09.270 Ist so ein bisschen sowas ähnliches wie das negierte. 36:09.990 --> 36:13.090 Negiert wäre es natürlich nur, wenn ich Funktionswerte von 0 bis 1 36:13.090 --> 36:13.330 hätte. 36:13.430 --> 36:16.950 Jetzt sind es beliebige Funktionswerte, die ich dann halt damit 36:16.950 --> 36:17.910 entsprechend umkehre. 36:20.680 --> 36:22.400 Und jetzt kommt das Interessante. 36:22.560 --> 36:29.520 Diese Funktion dquer, die unterscheidet sich von jeder Zeile fi der 36:29.520 --> 36:29.940 Tabelle. 36:31.340 --> 36:32.640 Naja, warum? 36:33.140 --> 36:40.940 Weil sie an der Stelle da, wo sie gerade die Diagonale ist. 36:41.060 --> 36:46.960 Also angenommen, diese Funktion dquer wäre irgendein fj in dieser 36:46.960 --> 36:49.260 Liste von Funktionen. 36:49.260 --> 37:01.040 Dann müsste ja gerade das Wort fj von wy das Gegenteil sein von fj von 37:01.040 --> 37:01.280 wy. 37:01.980 --> 37:03.680 Das heißt, das funktioniert nicht. 37:04.000 --> 37:11.000 Diese Funktion dquer kann es nirgendwo in dieser Matrix geben. 37:13.860 --> 37:17.200 Und damit kann man eben gerade diesen Satz, dass es keine Turing 37:17.200 --> 37:21.780 -Maschine gibt, die diese Sprache h, das Halteproblem entscheidet. 37:23.020 --> 37:26.060 Also insbesondere nochmal Hinweis, wenn ich entscheide, muss ich 37:26.060 --> 37:27.820 insbesondere auch immer halten. 37:28.100 --> 37:31.220 Entweder in einem akzeptierenden oder in einem nicht akzeptierenden 37:31.220 --> 37:31.740 Zustand. 37:32.520 --> 37:37.360 Und das macht man eben mithilfe dieser Diagonalisierung. 37:37.360 --> 37:41.500 Und was man sagt ist, ich stelle mir vor, diese Wörter, die oben in 37:41.500 --> 37:46.120 der Zeile stehen, das seien halt alle möglichen Kodierungen von Turing 37:46.120 --> 37:49.580 -Maschinen, die ich halt der Reihe nach aufzähle. 37:49.760 --> 37:54.940 Und da die Mengen, die man hat, immer endlich und aufzählbar sind, 37:55.920 --> 37:59.920 endliche Mengen sind immer aufzählbar, ist demnach auch die Menge der 37:59.920 --> 38:03.180 Wörter, der Kodierungen von Turing-Maschinen auch aufzählbar. 38:03.280 --> 38:05.280 Die kann ich oben in die Zeile reinschreiben. 38:07.640 --> 38:10.000 Und oben in die Spalten reinschreiben. 38:10.100 --> 38:14.240 Und in die Zeilen schreibe ich dann halt diese Funktionen rein, die 38:14.240 --> 38:20.700 ich mir so definiere, fi von wj, die soll halt gerade 1 sein, falls 38:20.700 --> 38:26.020 die Turing-Maschine, die durch das Wort wi kodiert wird, für die 38:26.020 --> 38:27.920 Eingabe wj hält. 38:29.020 --> 38:32.200 Und ansonsten sei der Funktionswert 0. 38:32.780 --> 38:37.880 Das heißt, für jede mögliche Turing-Maschine, die es gibt, das sind 38:37.880 --> 38:40.200 nämlich alle die Turing-Maschinen, die ich durch eine Kodierung 38:40.200 --> 38:44.920 beschreiben kann, habe ich dann eine Zeile in dieser Tabelle. 38:46.400 --> 38:49.020 Und jetzt macht man halt Beweis durch Gegenbeweis. 38:50.380 --> 38:54.120 Angenommen, es gebe eine Turing-Maschine, die dieses Halteproblem 38:54.120 --> 38:56.220 entscheidet, nennen wir sie thalt. 38:58.460 --> 39:07.140 Dann existiert auch eine Turing-Maschine tmdiagquär für die verdorbene 39:07.140 --> 39:07.920 Diagonale. 39:09.700 --> 39:14.880 Aber die verdorbene Diagonale, diese Diagonale tdiagquär, gibt es 39:14.880 --> 39:15.140 nicht. 39:16.580 --> 39:19.600 Jetzt ist natürlich die Frage, warum gibt es denn bitte schön diese 39:19.600 --> 39:24.000 tdiagquär, wenn es denn thalt gibt. 39:24.880 --> 39:27.300 Das kann man sich relativ leicht klar machen. 39:27.760 --> 39:30.900 Angenommen, ich hätte so eine Turing-Maschine thalt. 39:31.720 --> 39:35.980 Wenn ich diese Turing-Maschine thalt hätte, dann könnte ich gerade 39:35.980 --> 39:41.000 diese diagonalen Turing-Maschine tquär konstruieren. 39:42.200 --> 39:43.300 Was muss ich denn dafür machen? 39:43.300 --> 39:50.580 Die Diagonale ist nämlich gerade immer, hält der Wert, hält diese 39:50.580 --> 39:53.740 Turing -Maschine für sich selber als Eingabe oder nicht. 39:54.900 --> 40:00.820 Und angenommen, ich hätte die, dann gibt es ja diese Diagonale D 40:00.820 --> 40:06.040 irgendwo, eine Turing-Maschine, die halt gerade diese Diagonale 40:06.040 --> 40:06.800 realisiert. 40:07.900 --> 40:11.220 Und wenn es so eine Turing-Maschine gibt, die die Diagonale 40:11.220 --> 40:15.920 realisiert, dann kann ich ganz einfach so eine Turing-Maschine 40:15.920 --> 40:17.340 tdiagquär machen. 40:17.820 --> 40:23.420 Weil das Einzige, was ich machen muss, ist, dass wenn die Turing 40:23.420 --> 40:29.240 -Maschine wy für sich selber als Eingabe hält, dann muss ich das Ganze 40:29.240 --> 40:33.100 also invertieren, dann darf sie also nicht halten für sich selber als 40:33.100 --> 40:33.520 Eingabe. 40:33.520 --> 40:37.120 Dann muss ich sozusagen bei dem Ja-Fall, wenn ich hingehe in einen 40:37.120 --> 40:42.980 akzeptierenden, in irgendeinem akzehaltenden Zustand, muss ich einfach 40:42.980 --> 40:45.260 in diese Endlosschleife reinfallen. 40:46.740 --> 40:50.900 Und wenn ich weiß, dass diese Turing-Maschine nicht hält für sich 40:50.900 --> 40:54.220 selber als Eingabe, wenn also das Ergebnis der Überrechnung Nein wäre, 40:55.100 --> 40:57.840 dann müsste ich eben gerade die Turing-Maschine halten lassen. 41:00.760 --> 41:05.480 Und damit wäre das eben gerade die Turing-Maschine, die dieses 41:05.480 --> 41:11.440 tdiagquär realisiert, aber tdiagquär darf nicht existieren. 41:12.480 --> 41:16.400 Das heißt insbesondere darf eben nicht die Turing-Maschine existieren, 41:16.600 --> 41:19.240 die diese Diagonale realisiert. 41:19.760 --> 41:23.540 Und damit gibt es eben diese Turing-Maschine nicht. 41:23.540 --> 41:28.680 Von diesem Halteproblem kann man jetzt halt verschiedene Variationen 41:28.680 --> 41:29.120 ableiten. 41:29.260 --> 41:33.520 Man kann halt ableiten, kann ich entscheiden, ob eine Turing-Maschine 41:33.520 --> 41:38.340 hält, wenn das Band zu Beginn völlig leer ist? 41:39.540 --> 41:40.900 Ebenfalls unentscheidbar. 41:41.480 --> 41:44.740 Ich kann nicht entscheiden, ob zwei Turing-Maschinen immer genau 41:44.740 --> 41:48.100 dieselbe Berechnung durchführen für jede Eingabe. 41:50.380 --> 41:55.760 Ich kann nicht entscheiden, das ist diese Erreichbarkeit, Abdeckung 41:55.760 --> 41:56.460 von Kotstücken. 41:56.580 --> 41:59.280 Ich kann nicht entscheiden, wird jeder Zustand der Turing-Maschine 41:59.280 --> 42:04.740 jemals gebraucht, also jemals erreicht, jemals durchlaufen und dann 42:04.740 --> 42:05.900 entsprechend ganz andere. 42:06.400 --> 42:09.340 Und bei all den Dingen kann man immer sagen, statt Turing-Maschine 42:09.340 --> 42:12.660 nehmen Sie jedes beliebige Computerprogramm, das Sie bisher 42:12.660 --> 42:13.400 geschrieben haben. 42:13.780 --> 42:16.260 Alles genau dasselbe. 42:17.220 --> 42:23.180 Das heißt, nochmal, es gibt ganz viele Probleme, die Sie nicht 42:23.180 --> 42:24.080 berechnen können. 42:24.180 --> 42:27.140 Da können Sie noch der beste Algorithmiker und der schlauste 42:27.140 --> 42:28.040 Programmierer sein. 42:28.640 --> 42:33.540 Es gibt genügend Dinge, die nicht berechenbar sind. 42:34.800 --> 42:37.780 Wir kommen jetzt nochmal zurück zu der Turing-Maschine, die wir 42:37.780 --> 42:38.960 letztes Mal gesehen hatten. 42:38.960 --> 42:44.640 Die Busy Beaver-Maschine, Busy Beaver 3 hatten wir da gesehen, den 42:44.640 --> 42:45.680 fleißigen Beaver. 42:46.720 --> 42:50.220 Nochmal zur Erinnerung, das Ganze hatte ein Bandalphabet, das bestand 42:50.220 --> 42:53.120 nur aus dem leeren Zeichen und der 1. 42:53.700 --> 42:57.160 Und die Turing-Maschine hatte 3 plus 1 Zustände, da hatten wir schon 42:57.160 --> 43:00.680 diskutiert, diesen plus 1 Zustand, den braucht man eigentlich gar 43:00.680 --> 43:00.820 nicht. 43:00.900 --> 43:06.760 Der diente nur dazu, um explizit das Halt darzustellen. 43:06.760 --> 43:10.980 Aber durch die Benutzung dieser partiellen Funktionen braucht man den 43:10.980 --> 43:11.720 eigentlich gar nicht. 43:13.160 --> 43:16.160 Einer der Zustände ist logischerweise der Anfangszustand. 43:17.820 --> 43:21.500 Und dieser vierte Zustand ist dann halt der Haltezustand. 43:22.160 --> 43:25.680 Und das Einzige, was diese Turing-Maschine rausschreiben konnte, waren 43:25.680 --> 43:27.040 Einsen. 43:27.040 --> 43:31.000 Und wenn man jetzt halt diese Turing-Maschine auf einem leeren Band 43:31.000 --> 43:39.080 losfällt, loslaufen lässt, dann erhält sie nach endlich vielen 43:39.080 --> 43:39.400 Schritten. 43:39.560 --> 43:45.700 Also eine Busy Beaver-Maschine und die Busy Beaver 3 hält immer, wenn 43:45.700 --> 43:49.140 man das leere Wort als Eingabe nimmt. 43:51.060 --> 43:55.680 Und wir hatten gesagt, das ist die Turing-Maschine mit 3 plus 1 43:55.680 --> 43:59.940 Zuständen, die, wenn man das leere Wort als Eingabe auf das Alphabet 43:59.940 --> 44:04.020 draufschreibt, am meisten Einsen produziert. 44:04.760 --> 44:07.800 Und das kann man halt vereinfachen oder verallgemeinern auf die 44:07.800 --> 44:09.360 sogenannte N-Beaver-Maschine. 44:10.060 --> 44:12.880 Eine N-Beaver-Maschine hat halt auch dieses Alphabet, da kommen nur 44:12.880 --> 44:14.780 Einsen letztendlich drin vor. 44:14.780 --> 44:18.480 Die hat N plus 1 Zustände, wobei dieser eine plus 1 Zustand ist halt 44:18.480 --> 44:22.540 der sogenannte Haltezustand. 44:25.200 --> 44:28.340 Gibt halt einen Anfangszustand logischerweise und wenn man die 44:28.340 --> 44:32.020 startet, dann hält sie auch nach endlich vielen Schritten. 44:32.140 --> 44:35.760 Also das ist wichtig, eine N-Beaver-Maschine hält immer und sie 44:35.760 --> 44:37.740 schreibt, kann halt nur Einsen rausschreiben. 44:40.100 --> 44:44.280 Und jetzt gibt es spezielle N-Beaver-Maschinen, das sind dann die 44:44.280 --> 44:46.760 sogenannten Busy-Beaver-Maschinen. 44:47.500 --> 44:52.120 Und diese Busy-Beaver-Maschinen, eine N-Busy-Beaver-Maschine, das ist 44:52.120 --> 44:56.520 die N-Beaver-Maschine, die eben am meisten Einsen aufs Band 44:56.520 --> 44:59.300 draufgeschrieben hat, wenn sie denn mal hält. 45:00.500 --> 45:03.580 Und jetzt kann man sich entsprechend auch eine Funktion definieren. 45:03.760 --> 45:05.700 Das nennt man dann die Busy-Beaver-Funktion. 45:05.700 --> 45:12.680 Die kriegt halt dieses N der N-Beaver-Maschinen rein und sagt halt, 45:12.940 --> 45:17.120 was ist denn die Anzahl der Einsen, die maximale Anzahl der Einsen, 45:17.260 --> 45:22.400 die eine N-Beaver-Maschine am Ende auf dem Band hinterlässt. 45:24.280 --> 45:27.680 Und eine dieser Turing-Maschinen, das muss nicht eine geben, kann ja 45:27.680 --> 45:31.800 mehrere Beaver-Maschinen geben, die das machen, die eine, die halt die 45:31.800 --> 45:37.020 maximale Anzahl an Einsen hinterlässt, die nennt man halt dann die N 45:37.020 --> 45:37.760 -Beaver -Maschine. 45:37.900 --> 45:42.460 Die N-Beaver-Maschine hinterlässt halt, also ein fleißiger Beaver, ein 45:42.460 --> 45:49.760 Busy -Beaver hinterlässt halt BB von N Einsen auf dem Band, nachdem es 45:49.760 --> 45:50.420 gehalten hat. 45:53.980 --> 45:56.520 Jetzt ist erst mal die Frage, was ist denn so interessant an der 45:56.520 --> 45:56.980 Funktion? 45:56.980 --> 46:00.600 Das ist halt wieder irgendeine Funktion, relativ abstrakt. 46:01.440 --> 46:03.500 Jetzt kann man sich mal ein paar Funktionswerte anschauen. 46:04.160 --> 46:05.540 Und das Ganze sind Schranken. 46:06.020 --> 46:07.340 Das sind sowas wie untere Schranken. 46:08.580 --> 46:11.620 Also für eine Eins-Beaver-Maschine kann man relativ leicht zeigen, na 46:11.620 --> 46:16.200 gut, da kann man nur eine Eins rausgeben, weil wenn sie halten muss, 46:18.060 --> 46:19.600 muss dann irgendwann halt mal Schluss sein. 46:20.420 --> 46:23.480 Da kann man nur eine Eins rausschreiben und dann halten, sonst kriegt 46:23.480 --> 46:26.020 man es nicht hin, dass die Beaver-Maschine immer auf alle Fälle hält. 46:27.440 --> 46:32.200 Für N gleich zwei kann man halt Busy-Beaver-Maschinen konstruieren, 46:32.820 --> 46:36.320 oder Beaver-Maschinen konstruieren, die mindestens vier Einsen 46:36.320 --> 46:37.120 hinterlassen. 46:37.860 --> 46:42.300 Für vier kann man Sachen hinterlassen, die sechs Einsen hinterlassen. 46:43.160 --> 46:44.420 Das ist ja noch relativ harmlos. 46:44.760 --> 46:48.440 Das ist jetzt immer noch völlig langweilig und uninteressant. 46:50.020 --> 47:00.860 Bei vier mindestens 13 immer noch gehen. 47:02.340 --> 47:07.980 Bei fünf weiß man dann schon nicht mehr so genau, also mindestens 4098 47:07.980 --> 47:08.820 kriegt man hin. 47:09.120 --> 47:09.860 Das weiß man schon. 47:11.300 --> 47:14.120 Und bei sechs hat man wirklich nur eine untere Schranke. 47:16.340 --> 47:17.760 Und dann wird es interessant. 47:18.560 --> 47:22.520 Also man weiß, bei sechs ist die untere Schranke, also echt untere 47:22.520 --> 47:26.140 Schranke eben gerade diese, keine Ahnung, wie ich die Zahl aussprechen 47:26.140 --> 47:32.360 soll, 3,514 mal 10 und 18.276 Einsen, die hinterlassen werden. 47:33.500 --> 47:37.300 Das heißt, da scheint das Ding irgendwie abzuheben. 47:38.580 --> 47:39.660 Da geht es dann los. 47:42.440 --> 47:46.520 Die Frage ist, wie stark hebt diese Funktion dann ab? 47:46.600 --> 47:47.740 Wie stark steigt sie an? 47:48.620 --> 47:51.520 Und da ist jetzt eben gerade das Interessante an dieser Busy Beaver 47:51.520 --> 47:51.980 Funktion. 47:53.040 --> 47:57.780 Wenn ich eine total berechenbare Funktion habe, wenn das also eine 47:57.780 --> 48:03.800 Funktion ist, wo ich für jeden beliebige, die von den natürlichen 48:03.800 --> 48:06.240 Zahlen auf die natürlichen Zahlen abbildet und wo ich für jede 48:06.240 --> 48:10.400 beliebige natürliche Zahl den Funktionswert berechnen kann. 48:10.980 --> 48:17.240 Sprich, ich kann eine Turing-Maschine bauen, die dann jede beliebige 48:17.240 --> 48:22.080 natürliche Zahl als Eingabe bekommt und dann in endlicher Zeit diese 48:22.080 --> 48:23.140 Funktion berechnet. 48:23.800 --> 48:28.160 Wenn ich mir diese Funktion anschaue, dann kann ich für jede dieser 48:28.160 --> 48:34.840 Funktionen ein N0 finden, so dass ab diesem N0 der Wert der BB 48:34.840 --> 48:39.840 -Funktion größer ist als der Wert dieser total berechenbaren Funktion. 48:41.540 --> 48:52.820 Das heißt insbesondere, dass diese Funktion schneller wächst als jede 48:52.820 --> 48:55.240 andere total berechenbare Funktion. 48:55.240 --> 49:00.740 Also die BB-Funktion wächst schneller als jede andere Funktion, die 49:00.740 --> 49:04.820 ich mit einer Turing-Maschine berechnen kann. 49:06.660 --> 49:09.860 Dann kann man da jetzt ein Korollar machen, weil das ist ein 49:09.860 --> 49:11.400 einfacher, logischer Schluss. 49:11.500 --> 49:16.040 Also angenommen, der Satz gilt für jede total berechenbare Funktion, F 49:16.040 --> 49:22.460 gibt es halt einen Wert N0, ab dem BBn echt größer diesem 49:22.460 --> 49:23.820 Funktionswert ist. 49:25.100 --> 49:34.460 Wenn jetzt BB von N eine total berechenbare Funktion wäre, dann wäre 49:34.460 --> 49:35.400 der Satz hier falsch. 49:36.740 --> 49:41.180 Weil für die BB-Funktion müsste da größer gleich stehen und nicht 49:41.180 --> 49:41.680 größer. 49:41.680 --> 49:44.280 Natürlich ist der Wert der BB-Funktion gleich dem Wert der BB 49:44.280 --> 49:44.660 -Funktion. 49:45.060 --> 49:49.160 Da steht aber nicht größer gleich F von N, da steht echt größer von F 49:49.160 --> 49:49.540 von N. 49:50.460 --> 49:53.720 Und daraus folgt dann logischerweise, gut, dann kann BB von N keine 49:53.720 --> 49:57.500 total berechenbare Funktion sein, wenn dieser Satz da oben gilt. 49:58.180 --> 50:02.320 Das heißt also, die Busy Beaver-Funktion wächst super rasant schnell 50:02.320 --> 50:04.880 und ich kann sie nicht berechnen. 50:05.660 --> 50:10.480 Das ist also ein Beispiel einer Funktion, wo es nicht um 50:10.480 --> 50:13.040 Entscheidbarkeit geht, sondern ob es darum geht, ob ich sowas mit 50:13.040 --> 50:14.640 einer Turing-Maschine auch berechnen kann. 50:16.060 --> 50:21.040 Finde ich halt ganz lustig, weil man kann jetzt zum Beispiel zeigen, 50:21.100 --> 50:24.100 die Ackermann-Funktion ist gegen die BB-Funktion weisen Knabe. 50:24.900 --> 50:26.820 Die Ackermann-Funktion kann ich nämlich berechnen. 50:26.880 --> 50:28.300 Da habe ich einen Algorithmus, der die berechnet. 50:28.400 --> 50:29.200 Haben wir uns angeschaut. 50:29.280 --> 50:31.500 Und die Ackermann-Funktion, die ist schon verdammt schnell gewachsen. 50:33.020 --> 50:39.780 Die BB-Funktion, die übertrumpft die Ackermann-Funktion bei weitem. 50:41.400 --> 50:41.900 Gut. 50:42.740 --> 50:43.840 Also, was nehmen Sie mit? 50:44.760 --> 50:46.630 Auf alle Fälle, was ist das Halteproblem? 50:47.240 --> 50:50.480 Da haben viele Probleme mit zu sagen, was ist das Halteproblem? 50:50.580 --> 50:52.460 Das Halteproblem ist nämlich eine Menge. 50:54.580 --> 50:56.800 Das heißt zwar Halteproblem, aber es ist eine Menge. 50:57.420 --> 50:59.400 Eine Menge von Wörtern. 51:01.340 --> 51:03.480 Und damit eine formale Sprache. 51:03.920 --> 51:06.260 Und diese formale Sprache ist eben nicht entscheidbar. 51:07.120 --> 51:09.180 Und da gibt es viele andere, die da auch können. 51:09.560 --> 51:12.200 Und es gibt auch Funktionen, die Sie nicht berechnen können. 51:12.920 --> 51:14.740 Von denen wir aber so ein paar Eigenschaften wissen. 51:14.880 --> 51:18.180 Nämlich, dass sie schneller wachsen als jede andere berechenbare 51:18.180 --> 51:18.720 Funktion. 51:19.060 --> 51:21.380 Also als jede andere Funktion, die Sie berechnen können. 51:21.840 --> 51:23.740 Es gibt also Funktionen, die wir nicht berechnen können. 51:24.220 --> 51:27.220 Und schneller wachsen als jedes andere, was wir berechnen können. 51:28.880 --> 51:35.320 Jetzt gibt es bei Turing-Maschinen jede Menge Leute, die sich da in 51:35.320 --> 51:37.240 der theoretischen Informatik mit beschäftigen. 51:37.340 --> 51:39.780 Und wie das so ist bei theoretischen Informatikern, manchmal werden 51:39.780 --> 51:40.640 sie ein bisschen schrullig. 51:42.840 --> 51:47.220 Zum Beispiel gibt es an der University of Washington, ich glaube in 51:47.220 --> 51:52.200 Seattle, jemanden, der sich dann mit mechanischen Turing-Maschinen 51:52.200 --> 51:52.880 beschäftigt. 51:52.880 --> 51:57.160 Wo es dann sozusagen eine Dampf-Turing-Maschine gibt. 51:57.500 --> 51:59.880 Kann man sich leicht vorstellen, das ist relativ einfach. 52:01.040 --> 52:03.720 Man muss ja nur einen Kopf haben, den man links und rechts bewegt. 52:03.800 --> 52:06.700 Man muss endliche Dinge einlesen können. 52:07.620 --> 52:09.920 Und streng genommen kann man ja alles mit 0.1 kodieren. 52:10.080 --> 52:11.980 Also kann man das auch jederzeit ein bisschen umkodieren. 52:12.760 --> 52:17.200 Und dann kann man halt dementsprechend damit, mithilfe so einer 52:17.200 --> 52:20.780 Dampfmaschine, so etwas bauen. 52:20.780 --> 52:23.620 Und das ist halt der Stolz des Herrn Russo. 52:24.560 --> 52:27.160 Der geht ein bisschen unpfleglich mit seinen Studenten rum. 52:28.560 --> 52:30.920 Hat ihn natürlich von Studenten bauen lassen, weil das macht so ein 52:30.920 --> 52:31.920 richtiger Professor so. 52:32.420 --> 52:36.940 Und hin und wieder, jetzt wo sie steht, dürfen halt Studenten hin und 52:36.940 --> 52:39.980 wieder das Ding putzen. 52:41.360 --> 52:44.140 Und dann kriegt man halt Probleme irgendwann, weil wenn das Ding 52:44.140 --> 52:45.880 kohlegetrieben ist, ist es halt nicht so blöd. 52:46.360 --> 52:47.580 Heutzutage ist es halt ein bisschen blöd. 52:47.580 --> 52:50.720 Heutzutage kann man es nicht mal mehr mit einem Diesel machen. 52:53.380 --> 52:55.660 Und hin und wieder kommt es zu unschönen Unfällen. 52:58.000 --> 53:02.060 Das ist nochmal die Zusammenfassung des gesamten Kapitels. 53:04.080 --> 53:08.600 Um Ihnen jetzt nochmal klar zu machen, was eine Turing-Maschine 53:08.600 --> 53:12.560 wirklich alles kann, nämlich alles, und dass eine Turing-Maschine 53:12.560 --> 53:19.260 gleichzeitig relativ einfach ist, habe ich Ihnen einen kleinen 53:19.260 --> 53:21.400 wissenschaftlichen Beitrag rausgesucht. 53:22.220 --> 53:26.100 Das ist von einer Konferenz an der Carnegie Mellon University. 53:26.320 --> 53:28.660 Die ist vielleicht dem Namen nach ein Begriff. 53:28.760 --> 53:31.920 Die ist nicht so groß wie das MIT, wird aber auch meistens immer unter 53:31.920 --> 53:35.720 den Top-3-Informatik-Universitäten in den USA geränkt. 53:36.240 --> 53:39.060 Die haben halt auch hin und wieder interessante Kolloquien und 53:39.060 --> 53:41.040 Konferenzen. 53:41.040 --> 53:46.060 Und eine davon ist eben diese SIGBOVIC, das ist die Special Interest 53:46.060 --> 53:51.280 Group BOVIC, in der fortgeschrittene Themen der theoretischen 53:51.280 --> 53:53.700 Informatik behandelt werden. 53:54.360 --> 53:59.140 Und eine der Fragestellungen war zum Beispiel, womit kann ich alles 53:59.140 --> 54:00.220 eine Turing-Maschine machen? 54:00.360 --> 54:03.040 Und zum Beispiel können Sie mit PowerPoint eine Turing-Maschine 54:03.040 --> 54:03.760 realisieren. 54:05.260 --> 54:09.420 Das heißt also, PowerPoint kann eine Turing-Maschine realisieren und 54:09.420 --> 54:12.820 wenn PowerPoint eine Turing-Maschine realisieren kann, kann PowerPoint 54:12.820 --> 54:17.520 alles das, was Sie mit einem Rechner machen können. 54:17.900 --> 54:21.720 Das heißt also, Microsoft PowerPoint ist allmächtig. 54:23.180 --> 54:27.780 Das ist insofern dann interessant, weil PowerPoint finden Sie zum 54:27.780 --> 54:36.820 Beispiel auch im App Store von Apple oder halt im Play Store oder als 54:36.820 --> 54:39.740 es noch Microsoft Phones gab, gab es auch so einen Microsoft Phone 54:39.740 --> 54:40.500 Store. 54:41.580 --> 54:44.160 Und interessanterweise ist ja eine der Bedingungen, wenn man so 54:44.160 --> 54:48.240 durchliest, was man so alles an Programmen so in so einem Store 54:48.240 --> 54:52.480 veröffentlichen kann, ist eine der Bedingungen, Sie dürfen nicht 54:52.480 --> 54:55.180 Sachen veröffentlichen, mit denen Sie andere Programme schreiben 54:55.180 --> 54:59.420 können, sondern der Anwendungsfall dieses Programms, der muss klar 54:59.420 --> 55:00.040 begrenzt sein. 55:00.100 --> 55:01.840 Es darf kein allmächtiges Programm sein. 55:02.920 --> 55:05.980 Natürlich blöd, wenn Microsoft das zum einen aufstellt und zum anderen 55:05.980 --> 55:09.980 natürlich ein Programm veröffentlicht, das doch dann am Ende beweisbar 55:09.980 --> 55:10.560 alles kann. 55:11.280 --> 55:15.160 Und das schauen wir uns jetzt einfach mal an, wie das funktioniert. 56:30.670 --> 56:34.190 Hallo, mein Name ist Tom und in dieser Präsentation werde ich meine 56:34.190 --> 56:37.510 Forschung über das Löschen von komputativen Problemen mit PowerPoint 56:37.510 --> 56:37.510 vorstellen. 56:37.510 --> 56:40.290 I will explore to what extent PowerPoint can replace conventional 56:40.290 --> 56:43.750 programming languages as well as the benefits and limitations of using 56:43.750 --> 56:45.230 PowerPoint for such purposes. 56:46.050 --> 56:47.490 But first a quick disclaimer. 56:48.030 --> 56:50.310 This presentation is not sponsored or endorsed by any real or 56:50.310 --> 56:52.350 hypothetical corporation located in Redmond, Washington. 56:52.790 --> 56:54.950 The views and opinions expressed are those of the author and do not 56:54.950 --> 56:57.510 necessarily reflect those of any such corporation should one exist. 56:57.990 --> 57:00.290 Only trained PowerPoint professionals should attempt to reproduce the 57:00.290 --> 57:02.670 results of this research and the author will not be held responsible 57:02.670 --> 57:05.190 for any material, physical or emotional damages caused by such 57:05.190 --> 57:05.630 attempts. 57:06.230 --> 57:09.050 So with that out of the way, we can proceed to the background. 57:10.490 --> 57:13.770 So as you may know, PowerPoint has hyperlinks and animations which can 57:13.770 --> 57:15.770 be used to add interactivity to your presentations. 57:16.410 --> 57:20.890 So we have links here and we also have animations which are 57:20.890 --> 57:23.850 particularly interesting because you can trigger them in different 57:23.850 --> 57:24.330 orders. 57:25.610 --> 57:29.330 So you can use these to make interesting things like applications, 57:29.630 --> 57:32.290 games, you know, typical things that you'd make in a slideshow editor. 57:32.290 --> 57:37.290 But until recently, it has been unproven as to whether you can do all 57:37.290 --> 57:39.870 things using PowerPoint, whether you can solve every computational 57:39.870 --> 57:42.250 problem with a dedicated PowerPoint file. 57:42.570 --> 57:45.510 And this is largely because in order to prove such a claim, you would 57:45.510 --> 57:49.490 need to create a Turing machine that runs in PowerPoint or you'd have 57:49.490 --> 57:52.270 to be able to show that every Turing machine can be run within 57:52.270 --> 57:52.670 PowerPoint. 57:53.330 --> 57:57.410 So without further ado, the palindrome recognizing Turing machine. 58:00.190 --> 58:04.390 So here we have a Turing machine that decides the language palindrome 58:04.390 --> 58:05.510 to even length. 58:06.090 --> 58:11.010 So you can see that like a normal Turing machine, we can move this 58:11.010 --> 58:11.350 tape. 58:11.490 --> 58:13.350 This is implemented completely with animations. 58:13.870 --> 58:16.050 There are no macros or anything else. 58:17.090 --> 58:19.250 So I can write the tape, of course. 58:19.330 --> 58:21.050 We'll give it a simple input like this. 58:21.430 --> 58:24.090 And of course, I can also execute the Turing machine. 58:24.550 --> 58:27.110 So here we have the Turing machine's current state. 58:27.110 --> 58:30.990 And in order to continue execution, unfortunately, this doesn't happen 58:30.990 --> 58:31.230 automatically. 58:32.210 --> 58:33.390 It needs a little bit of encouragement. 58:33.870 --> 58:36.350 The user has to click on each orange region. 58:37.570 --> 58:40.210 Now you might be concerned today that I'm making decisions whenever 58:40.210 --> 58:41.010 I'm clicking on this. 58:41.270 --> 58:44.810 But the way that this PowerPoint is set up, every other area is 58:44.810 --> 58:45.170 blocked. 58:45.290 --> 58:48.550 So I can click randomly essentially and the PowerPoint will just 58:48.550 --> 58:50.130 advance its computation. 58:50.950 --> 58:53.490 So that was the input 1-1. 58:53.870 --> 58:55.570 So this should end up being accepted. 58:55.570 --> 59:00.650 And we can see that it does indeed end on an accepting state. 59:01.130 --> 59:04.050 And I can rerun that with another input and it would reject 59:04.050 --> 59:05.690 accordingly, depending on what it is. 59:06.450 --> 59:10.390 So this is nice, but what we'd really like to be able to do is run any 59:10.390 --> 59:12.030 Turing machine in PowerPoint. 59:13.290 --> 59:17.250 Fortunately, this is easy because the PowerPoint Turing machine is 59:17.250 --> 59:19.090 programmed entirely using punch cards. 59:19.510 --> 59:22.630 So for example, this card says that whenever the Turing machine is in 59:22.630 --> 59:25.970 state 0 and it reads a 1, then it should write a blank, move to the 59:25.970 --> 59:27.310 right, and then move to state 2. 59:27.630 --> 59:30.510 But if we change where these holes are located, we can make the Turing 59:30.510 --> 59:33.630 machine do something else and essentially imitate any transition 59:33.630 --> 59:35.790 function of any other Turing machine. 59:36.250 --> 59:42.730 All of this is accomplished using over 1,600 animations and around 700 59:42.730 --> 59:43.270 attributes. 59:46.610 --> 59:49.830 The PowerPoint Turing machine offers a number of advantages over 59:49.830 --> 59:51.130 alternative programming languages. 59:51.130 --> 59:56.310 Offering cross-platform support running on both mobile devices and 59:56.310 --> 59:59.170 both commercially relevant desktop operating systems. 01:00:00.790 --> 01:00:04.830 In addition, its drag-and-drop programming means there's no text and 01:00:04.830 --> 01:00:05.910 no syntax errors. 01:00:06.430 --> 01:00:09.490 But most importantly, you can use themes, word art, and transitions 01:00:09.490 --> 01:00:12.190 that PowerPoint is infamous for in your code. 01:00:13.170 --> 01:00:17.050 It requires asymptotically fewer auto-shapes than when implemented in 01:00:17.050 --> 01:00:21.030 alternative slideshow editors, definitively proving PowerPoint to be 01:00:21.030 --> 01:00:23.450 exponentially more capable than competing software. 01:00:25.490 --> 01:00:29.210 But perhaps most notably, the PowerPoint Turing machine shows that the 01:00:29.210 --> 01:00:33.830 PowerPoint iOS app is in violation of Apple's App Store guidelines and 01:00:33.830 --> 01:00:37.890 shows that PowerPoint can emulate alternative apps and execute 01:00:37.890 --> 01:00:38.810 arbitrary code. 01:00:40.130 --> 01:00:43.570 In the future, I'd like to research making PowerPoint code more 01:00:43.570 --> 01:00:48.190 scalable and optimized, so that one day every application you run on 01:00:48.190 --> 01:00:50.510 your computer can be run within PowerPoint. 01:01:01.900 --> 01:01:04.100 Okay, also so viel noch dazu. 01:01:06.800 --> 01:01:11.560 Zeigt mal wieder, was für geniale Software uns da von Microsoft zur 01:01:11.560 --> 01:01:12.500 Verfügung gestellt wird. 01:01:12.580 --> 01:01:14.440 Das sind wahrscheinlich Dinge, die Sie selber noch nicht mal 01:01:14.440 --> 01:01:16.640 realisiert haben oder Sie haben es gut versteckt. 01:01:18.040 --> 01:01:24.260 An diesem Punkt sind wir jetzt angekommen, an einem Punkt, wo ich nur 01:01:24.260 --> 01:01:29.000 sagen kann, das ist alles, was ich Ihnen jetzt zum Thema Grundbegriffe 01:01:29.000 --> 01:01:30.920 der Informatik sagen kann. 01:01:31.980 --> 01:01:36.920 Damit ist Grundbegriffe der Informatik für Sie vorbei und erschöpft. 01:01:38.440 --> 01:01:43.000 Sie werden im Skriptum noch zwei weitere Kapitel finden, die aber dann 01:01:43.000 --> 01:01:45.340 dementsprechend auch nicht relevant sind, weil wir sie hier in der 01:01:45.340 --> 01:01:46.560 Vorlesung nicht behandelt haben. 01:01:48.220 --> 01:01:53.640 Dafür haben Sie stattdessen halt eine Probeklausur gehabt, das 01:01:53.640 --> 01:01:57.020 hoffentlich für Sie ein bisschen nützlicher ist, als wenn wir jetzt 01:01:57.020 --> 01:02:00.960 noch was zum Thema Relationen und noch mal was zum Thema MIMA sagen. 01:02:01.480 --> 01:02:05.220 Das, was Sie sozusagen verpassen, kriegen Sie in den weiteren 01:02:05.220 --> 01:02:08.940 Semestern sowieso noch mal ausführlich vorbereitet. 01:02:09.040 --> 01:02:10.560 Deswegen verpassen Sie da nichts. 01:02:10.560 --> 01:02:15.140 An dieser Stelle bleibt mir Ihnen jetzt nur noch viel Erfolg für die 01:02:15.140 --> 01:02:16.960 Vorbereitung auf die Klausur zu wünschen. 01:02:17.760 --> 01:02:20.120 Ich hoffe, Sie haben sich inzwischen alle angemeldet. 01:02:20.200 --> 01:02:21.760 Wenn nicht, melden Sie sich an. 01:02:23.080 --> 01:02:26.300 Wenn Sie sich noch abmelden wollen, brauchen Sie keine Panik zu 01:02:26.300 --> 01:02:26.660 bekommen. 01:02:27.260 --> 01:02:30.640 Die Abmeldung ist noch bis Mitternacht am Tag vor der Klausur im 01:02:30.640 --> 01:02:31.760 Campus -System möglich. 01:02:31.760 --> 01:02:38.040 Und ansonsten können Sie sich jederzeit auch im Hörsaal noch am Tag 01:02:38.040 --> 01:02:41.960 der Klausur, bevor die Klausur losgeht, abmelden. 01:02:44.020 --> 01:02:49.820 Achten Sie ein bisschen auf das Ilias, weil wenn wir jetzt näher 01:02:49.820 --> 01:02:54.460 kommen an die Klausur, so ein paar Tage vor der Klausur werden wir im 01:02:54.460 --> 01:02:57.780 Ilias dann veröffentlichen, in welchem Hörsaal Sie sitzen, wer in 01:02:57.780 --> 01:02:59.220 welchem Hörsaal sitzt. 01:02:59.220 --> 01:03:00.860 Das schauen Sie dann im Ilias nach. 01:03:00.920 --> 01:03:02.200 Wir schicken dann auch E-Mails rum. 01:03:02.740 --> 01:03:05.740 Und dann gehen Sie halt am Tag der Klausur mit so ein bisschen 01:03:05.740 --> 01:03:10.640 Zeitpuffer zu Ihrem Hörsaal, wo Sie zugeordnet wurden. 01:03:11.020 --> 01:03:14.180 Dann werden Sie da eine Liste finden, auf der steht dann drauf, auf 01:03:14.180 --> 01:03:16.340 welchem Platz Sie zugeordnet wurden. 01:03:16.440 --> 01:03:20.040 Und dann suchen Sie sich Ihren Platz und schreiben dann so, wie wir 01:03:20.040 --> 01:03:22.020 Ihnen das schon vorgestellt haben, die Klausur. 01:03:22.940 --> 01:03:26.160 Und bis dahin unterschätzen Sie nicht den Aufwand für die 01:03:26.160 --> 01:03:26.360 Vorbereitung. 01:03:26.360 --> 01:03:31.600 Es sind sehr viele unterschiedliche Themen, die zwar alle nicht ganz 01:03:31.600 --> 01:03:34.680 groß in die Tiefe gehen, aber es ist trotzdem vom Umfang her relativ 01:03:34.680 --> 01:03:36.220 viel Stoff, den Sie im Kopf haben müssen. 01:03:36.720 --> 01:03:37.980 Denken Sie auch an die Grundlagen. 01:03:38.080 --> 01:03:40.460 Sie haben festgestellt, diese ganzen Grundlagen, die wir am Anfang 01:03:40.460 --> 01:03:43.260 gemacht haben, die kommen immer wieder und wieder, die sollten Sie 01:03:43.260 --> 01:03:47.080 nicht aus den Augen verlieren und auch wissen, was Sie damit dann in 01:03:47.080 --> 01:03:49.600 den fortgeschritteneren Themen auch wirklich machen können. 01:03:50.320 --> 01:03:52.940 Und lesen Sie nicht nur die Folien und das Skriptum. 01:03:53.400 --> 01:03:57.540 Gucken Sie schöne PowerPoint-Präsentationen, die Sie da in Videos auf 01:03:57.540 --> 01:04:02.040 YouTube finden, zu dem Thema und schauen Sie auch mal in die Literatur 01:04:02.040 --> 01:04:05.540 rein, die ich Ihnen ganz am Anfang in der ersten Vorlesung auch mal 01:04:05.540 --> 01:04:06.140 empfohlen habe. 01:04:06.240 --> 01:04:09.340 Das bekommen Sie alles in der Bibliothek. 01:04:10.340 --> 01:04:13.500 Das hilft Ihnen sicherlich dann auch nochmal bei der Vorbereitung auf 01:04:13.500 --> 01:04:16.360 die Klausur, wenn Sie da ein bisschen einen anderen Winkel, einen 01:04:16.360 --> 01:04:17.300 anderen Zugang bekommen. 01:04:18.460 --> 01:04:20.880 Damit sind Sie dann hiermit an dieser Stelle entlassen. 01:04:21.220 --> 01:04:24.940 Einen Teil von Ihnen sehe ich dann am Tag der Klausur wieder. 01:04:25.180 --> 01:04:28.740 Bis dahin alles Gute und viel Spaß bei der Vorbereitung.