WEBVTT

00:01.890 --> 00:03.050
So, schönen guten Morgen.

00:03.150 --> 00:05.330
Ich begrüße Sie zur Vorlesung der Grundlagen der Informatik II.

00:05.470 --> 00:06.950
Tut mir leid, dass es ein bisschen verspätet ist heute.

00:07.090 --> 00:11.870
Ich war fast hier und stand dann auf einmal in einem Stau vor Ampeln,

00:12.010 --> 00:13.090
die fast nur noch rot waren.

00:13.190 --> 00:15.070
Tut mir leid, da bin ich aufgehalten worden.

00:16.690 --> 00:21.890
Letztes Mal haben wir uns mit Berechenbarkeit beschäftigt.

00:22.510 --> 00:24.170
Ich hatte das Kapitel 4 beendet.

00:24.250 --> 00:28.330
Wir hatten dann uns angeguckt, was eigentlich das heißt, dass eine

00:28.330 --> 00:30.010
Funktion berechenbar ist.

00:30.010 --> 00:32.190
Ich hatte Ihnen dazu ein bisschen was erzählt.

00:32.370 --> 00:35.550
Nochmal erinnert an das, was eigentlich Algorithmen darstellen.

00:36.390 --> 00:38.590
Was ein Algorithmus eigentlich ist.

00:39.010 --> 00:40.770
Allgemeinheit, Determiniertheit, Endlichkeit.

00:41.010 --> 00:44.650
Das Wesentliche, ein endlich beschriebenes Verfahren, das für jede

00:44.650 --> 00:46.650
zulässige Eingabe hält.

00:47.290 --> 00:50.010
Ich habe Ihnen eine ganze Reihe Beispiele nochmal dargestellt.

00:50.730 --> 00:52.990
Vor allen Dingen auch gezeigt, dass nicht immer alles deterministisch

00:52.990 --> 00:56.130
sein muss, sondern dass man auch randomisierte Verfahren einsetzt mit

00:56.130 --> 00:57.050
sehr großem Erfolg.

00:57.050 --> 01:00.170
Ganz wichtige Klasse von Algorithmen.

01:01.290 --> 01:04.850
Wir hatten dann gesehen, wie man Algorithmen zunächst mal intuitiv

01:04.850 --> 01:05.390
beschreibt.

01:05.530 --> 01:10.490
Wie man sie dann zum Begriff der Berechenbarkeit kommt.

01:10.730 --> 01:12.950
Wir haben uns überlegt, ob Funktionen immer berechenbar sind oder

01:12.950 --> 01:13.270
nicht.

01:13.390 --> 01:16.150
Wir haben festgestellt, es gibt viel mehr nicht berechenbare

01:16.150 --> 01:18.050
Funktionen als berechenbare Funktionen.

01:18.110 --> 01:21.590
Das war dieses Diagonalisierungsverfahren, wo wir annahmen, dass die

01:21.590 --> 01:23.550
Anzahl berechenbar wäre...

01:23.550 --> 01:27.530
Quatsch, dass die Anzahl der berechenbaren Funktionen abzählbar wäre.

01:27.650 --> 01:33.710
Wir stellen fest, dass es auf jeden Fall sehr viel mehr nicht

01:33.710 --> 01:36.410
berechenbare Funktionen gibt als berechenbare Funktionen.

01:36.450 --> 01:38.610
Wir haben uns dann mit Entscheidbarkeit beschäftigt.

01:39.130 --> 01:43.850
Dass man für jede Eingabe oder für jedes Element eine Menge M1

01:43.850 --> 01:47.850
feststellen kann, ob sie eventuell zu einer Teilmenge M2 gehört oder

01:47.850 --> 01:48.110
nicht.

01:48.690 --> 01:51.450
Wir hatten uns dann ein paar Beispiele betrachtet.

01:51.450 --> 01:56.430
Wir hatten die Aufzählbarkeit, das ist also die Abzählbarkeit plus

01:56.430 --> 01:59.410
Berechenbarkeit angeschaut.

01:59.450 --> 02:02.550
Ich hatte Ihnen die Struktur dieser Mengen, die wir jetzt hier

02:02.550 --> 02:03.990
definiert haben, kurz dargestellt.

02:04.270 --> 02:06.450
Entscheidbare, dann Aufzählbare, dann Abzählbare Mengen.

02:07.910 --> 02:11.710
Und dann kamen wir zur Turing-Berechenbarkeit, das heißt Funktionen

02:11.710 --> 02:15.070
jetzt formal beschrieben als berechenbar, dadurch, dass sie von einer

02:15.070 --> 02:17.150
Turing -Maschine ausgeführt werden können.

02:17.650 --> 02:20.490
Wir hatten das dann formal angefangen zu definieren.

02:20.490 --> 02:24.630
Das war das letzte Mal, wo wir gesagt haben, wir haben eine Eingabe

02:24.630 --> 02:27.330
auf dem Eingabe- und Arbeitsband.

02:28.170 --> 02:32.050
Wir fangen an zu rechnen, sind in der Anfangskonfiguration und wenn

02:32.050 --> 02:34.950
wir dann zu einem Ende kommen, das heißt wir können nicht weitermachen

02:34.950 --> 02:44.930
und sind in einem Endzustand, dann ist das, was auf dem Band steht,

02:45.010 --> 02:46.370
das Ergebnis der Berechnung.

02:46.370 --> 02:50.790
Und in dem Sinne ist dann eine Funktion Turing-Berechenbar, wenn wir

02:50.790 --> 02:56.190
eben genau für jedes Argument dieser Funktion das gewünschte Ergebnis

02:56.190 --> 02:58.030
auf dem Band produzieren können.

02:58.870 --> 03:03.450
Und jetzt kommen wir hier zur ersten neuen Folie für heute.

03:03.890 --> 03:07.030
Ein Beispiel, das ein bisschen über das hinausgeht, was wir bisher

03:07.030 --> 03:08.010
schon betrachtet haben.

03:08.310 --> 03:10.690
Eine Eigenschaft, die Sie eigentlich noch gar nicht kennen, da steht

03:10.690 --> 03:12.370
etwas unter ein 1-Komplement.

03:12.370 --> 03:15.810
Ein 1-Komplement hat etwas zu tun mit Zahlendarstellungen.

03:16.310 --> 03:21.170
Wenn Sie negative Zahlen darstellen, dann müssen Sie ein 1-Komplement

03:21.170 --> 03:21.590
bilden.

03:21.670 --> 03:25.230
Das werden Sie in ein paar vorliegenden Stunden kennenlernen, wenn wir

03:25.230 --> 03:26.470
uns mit Zahlendarstellungen beschäftigen.

03:26.970 --> 03:30.990
Hier geht es eigentlich nur darum, dass wir eine Zahl, zum Beispiel 0,

03:31.130 --> 03:36.030
1, 1, 0, 0 usw., wenn wir die ins 1-Komplement versetzen wollen, dann

03:36.030 --> 03:38.750
schreiben wir hier einfach 1, 0, 0, 1, 1.

03:38.750 --> 03:43.910
Wir wollen also einfach nur jedes Bit kippen und genau das Gegenteil

03:43.910 --> 03:44.630
dorthin schreiben.

03:45.650 --> 03:48.330
Und das ist jetzt ein 1-Komplement.

03:48.550 --> 03:53.750
Ist zwar nicht so definiert, ist aber tatsächlich so zu berechnen.

03:54.810 --> 04:01.030
Formal definiert kann man es auch so rekursiv, dass man sagt, das 1

04:01.030 --> 04:04.130
-Komplement des leeren Wortes ist natürlich nur das leere Wort, das

04:04.130 --> 04:04.490
ist klar.

04:04.490 --> 04:09.170
Wenn das ein Wort mit einer 0 anfängt, dann wird einfach die 0 in eine

04:09.170 --> 04:09.870
1 verwandelt.

04:09.970 --> 04:13.050
Wenn das mit einer 1 anfängt, wird die 1 in eine 0 verwandelt und dann

04:13.050 --> 04:14.690
wird die gleiche Funktion auf den Rest angewandt.

04:15.470 --> 04:20.810
Eine einfache rekursive Definition dieses 1-Komplements und eine

04:20.810 --> 04:24.470
einfache Turing-Maschine, die das macht, ist ja wirklich sehr, sehr

04:24.470 --> 04:24.930
einfach.

04:24.930 --> 04:30.990
Wenn ich eine 1 sehe, ich bin im Anfangszustand, ich sehe eine 0 auf

04:30.990 --> 04:33.930
dem Eingabeband, dann muss ich halt daraus eine 1 machen.

04:34.450 --> 04:37.170
Ich gehe weiter nach rechts, wenn ich eine 1 sehe, dann mache ich

04:37.170 --> 04:37.870
daraus eine 0.

04:38.170 --> 04:41.250
Gehe weiter nach rechts, wenn ich einen Stern sehe, hier rechts

04:41.250 --> 04:45.130
daneben ein Stern, dann lasse ich den Stern stehen, gehe anschließend

04:45.130 --> 04:46.430
nach links und höre auf.

04:46.570 --> 04:47.970
Gehe in einen neuen Zustand, S1.

04:48.070 --> 04:50.310
Aus dem Zustand S1 kann ich nicht weitermachen, das heißt, ich bin

04:50.310 --> 04:52.870
fertig mit der Bearbeitung und kann aufhören.

04:52.870 --> 04:57.730
Eine sehr einfache Maschine, um einen Wert, ein Argument umzuwandeln

04:57.730 --> 05:02.150
in ein Ergebnis, das in diesem Fall das 1-Komplement dieses Wertes

05:02.150 --> 05:02.430
ist.

05:03.390 --> 05:07.770
Das war ein kurzes Beispiel und es ist klar, wenn ich von Turing

05:07.770 --> 05:10.750
-Berechenbaren Funktionen rede, dann kann ich natürlich alles, was wir

05:10.750 --> 05:14.010
vorher über Intuitiv-Berechenbare Funktionen definiert haben, jetzt

05:14.010 --> 05:20.950
als Turing-Berechenbar definieren, also mit dem Präfix Turing

05:20.950 --> 05:21.410
versehen.

05:21.490 --> 05:25.390
Wir können also von Turing-aufzählbaren Mengen reden, in dem

05:25.390 --> 05:32.130
Augenblick, wo die Funktion, die sie aufzählt, Turing-Berechenbar ist,

05:32.270 --> 05:36.570
genauso Turing-Entscheidbar, wenn die Entscheidungsfunktion Turing

05:36.570 --> 05:37.330
-Berechenbar ist.

05:37.390 --> 05:41.170
Das ist also alles kanonisch, dass man das dann so formal definieren

05:41.170 --> 05:41.490
kann.

05:41.490 --> 05:45.930
Und jetzt haben wir eben den Begriff Berechenbarkeit spezialisiert auf

05:45.930 --> 05:49.670
einen Begriff, der sich bezieht auf ein ganz spezielles

05:49.670 --> 05:51.490
Maschinenmodell, nämlich die Turing-Maschine.

05:54.450 --> 05:59.570
Und das ist klar, dass hier das Gleiche gilt, was wir vorher schon

05:59.570 --> 06:00.090
gesagt haben.

06:00.170 --> 06:03.590
Vorher hatten wir gesagt, dass aufzählbare Mengen eigentlich auch semi

06:03.590 --> 06:04.550
-entscheidbar heißen.

06:04.550 --> 06:07.930
Das gilt natürlich für Turing-aufzählbare Maschinen genauso.

06:08.730 --> 06:16.930
Die wird genau die Elemente von M akzeptieren, also für Elemente aus

06:16.930 --> 06:19.790
der Menge M, die Turing-aufzählbar ist, wird die Maschine anhalten und

06:19.790 --> 06:20.130
stoppen.

06:20.610 --> 06:24.010
Und für Elemente, die nicht in der Menge sind, wird sie eventuell

06:24.010 --> 06:24.850
nicht anhalten.

06:24.950 --> 06:27.230
Deswegen heißen die dann semi-entscheidbar.

06:27.290 --> 06:30.650
Ich kann nur feststellen, dass ein Element drin ist, aber nicht, ob es

06:30.650 --> 06:31.330
draußen ist.

06:33.170 --> 06:37.990
Jetzt will ich eines vorstellen, was ganz wichtig ist.

06:38.390 --> 06:42.750
Sie kennen von Ihren Rechnern, die Sie in der Hand haben oder in der

06:42.750 --> 06:47.270
Tasche oder auch ansonsten benutzen, dass Sie diese Rechner nicht nur

06:47.270 --> 06:49.590
für eine Funktion verwenden können, sondern Sie können natürlich viele

06:49.590 --> 06:51.310
Funktionen berechnen mit einem Rechner.

06:51.770 --> 06:54.990
Natürlich sagen wir, weil wir ein Programm einfach schreiben können,

06:55.310 --> 06:57.970
das eine spezielle Funktion dann ausführt.

06:58.750 --> 07:02.270
Und die Frage ist, ich habe hier nur eine Turing-Maschine.

07:02.930 --> 07:05.690
Kann ich eventuell eine Turing-Maschine angeben, mit der ich andere

07:05.690 --> 07:07.430
Turing -Maschinen simulieren kann?

07:08.170 --> 07:10.750
Also zunächst mal berechnet jede Turing-Maschine nur eine Funktion.

07:11.030 --> 07:14.590
Und die Idee ist, dass wir jetzt einfach überlegen, wie kann ich eine

07:14.590 --> 07:19.690
Turing -Maschine angeben, die im Prinzip jede andere berechnen kann?

07:20.850 --> 07:22.210
Das sieht zunächst mal seltsam aus.

07:22.230 --> 07:23.210
Wie soll das funktionieren?

07:23.650 --> 07:25.010
Wie machen wir das im normalen Rechner?

07:25.130 --> 07:26.450
Da laden wir ein Programm rein.

07:26.450 --> 07:30.170
Wir beschreiben die Funktion, die berechnet werden soll durch ein

07:30.170 --> 07:30.650
Programm.

07:31.530 --> 07:35.890
Und schreiben die in den Speicher im Prinzip rein und holen es dann

07:35.890 --> 07:39.290
aus dem Speicher, die Beschreibung dieses Programms raus.

07:39.610 --> 07:43.110
Und führen genau das vorher beschriebene, eingegebene Programm aus.

07:44.190 --> 07:47.390
Wie sieht der Speicher aus bei einer Turing-Maschine?

07:47.470 --> 07:50.430
Es ist ein langes Band, von dem können wir an irgendwelchen Stellen

07:50.430 --> 07:51.150
etwas lesen.

07:51.150 --> 07:55.790
Auf diesem Band kann also im Prinzip die Beschreibung einer Turing

07:55.790 --> 07:56.830
-Maschine draufstehen.

07:57.270 --> 07:59.170
Das ist unser Speicher, den wir haben.

07:59.270 --> 08:01.790
Wir schreiben eine Beschreibung einer Turing-Maschine darauf.

08:01.910 --> 08:04.990
Wir schreiben die Eingabe für die Turing-Maschine darauf.

08:06.790 --> 08:09.490
Also die Turing-Maschine, die Eingabe.

08:10.390 --> 08:13.630
Das heißt, ich muss hier irgendwo eine Turing-Maschine reinschreiben.

08:13.750 --> 08:15.750
Ich muss irgendwo ein Wort reinschreiben.

08:15.850 --> 08:16.550
Das ist die Eingabe.

08:16.550 --> 08:20.790
Und dann muss ich auf dem restlichen Arbeitsband die Wirkungsweise der

08:20.790 --> 08:26.670
beschriebenen Turing-Maschine T auf diesem Wort, der Eingabe W,

08:26.990 --> 08:27.650
simulieren.

08:29.590 --> 08:31.870
Und das ist die ganz einfache Idee.

08:32.450 --> 08:34.330
Sieht einfach aus.

08:34.530 --> 08:37.690
Das umzusetzen ist ein bisschen Codierungsaufwand.

08:37.790 --> 08:39.650
Und das will ich ein bisschen andeuten, wie man das macht.

08:40.010 --> 08:42.550
Gehe nicht in alle Einzelheiten rein, aber ich beschreibe das etwas.

08:43.130 --> 08:50.010
Also, wir haben das Band, auf das wir die Arbeitsweise, also dieses U

08:50.010 --> 08:54.590
ist unsere universelle Turing-Maschine, und wir schreiben die

08:54.590 --> 08:57.430
Beschreibung von T auf das Band.

08:57.550 --> 08:59.150
Das wird die Arbeitsweise von T beschrieben.

08:59.210 --> 09:01.410
Was brauche ich, um die Arbeitsweise einer Turing-Maschine zu

09:01.410 --> 09:01.790
beschreiben?

09:02.310 --> 09:04.910
Da muss ich im Prinzip nur die Turing-Tabelle auf das Band schreiben.

09:05.710 --> 09:08.310
Nur in Anführungszeichen, in einer geeigneten Codierung.

09:08.470 --> 09:10.850
Ich muss mir ein Alphabet definieren, mit dem ich das machen kann.

09:10.850 --> 09:13.970
Eine Art Codierung, wie ich das da reinschreiben kann.

09:14.310 --> 09:16.510
Und dann brauche ich noch die Initialkonfiguration.

09:17.710 --> 09:20.410
Initialkonfiguration ist also im Wesentlichen der Anfangszustand, S0,

09:20.750 --> 09:22.730
und meine Eingabe vor Ort.

09:24.390 --> 09:27.210
Und Sie sehen, ich habe das getrennt dann durch ein Leerzeichen.

09:28.050 --> 09:31.210
Und dann habe ich also hier genau das Programm stehen auf dem Band,

09:31.330 --> 09:32.530
und das muss ich anschließend ausführen.

09:34.170 --> 09:38.030
Und ich muss also dann auf dem Arbeitsband hier in diesem rechten

09:38.030 --> 09:43.690
Bereich, diese Initialkonfiguration, die muss ich im Prinzip ersetzen

09:43.690 --> 09:47.190
durch eine Folgekonfiguration, die durch eine Folgekonfiguration usw.

09:47.790 --> 09:52.030
Und die Folgekonfiguration kann ich erzeugen durch Ausnutzung dessen,

09:52.070 --> 09:55.930
was hier auf dem Band vorne drauf steht, wo die Tabelle dieser Turing

09:55.930 --> 09:57.530
-Maschine abgelegt ist.

09:58.350 --> 10:01.850
Und wenn also die Turing-Maschine in der Lage ist, diese

10:01.850 --> 10:05.170
Folgekonfiguration zu erzeugen, dann kann sie auch genau die

10:05.170 --> 10:08.470
Arbeitsweise der Turing-Maschine simulieren, weil sie dann genauso in

10:08.470 --> 10:15.630
eine Endkonfiguration kommen wird wie diese Turing-Maschine T.

10:16.130 --> 10:20.390
Also ich müsste in der Lage sein, diese bediebige Turing-Maschine zu

10:20.390 --> 10:20.910
simulieren.

10:22.130 --> 10:26.470
Und jetzt ganz kurz, ich nehme an, dass ich hierfür ein festes

10:26.470 --> 10:29.610
Bandalphabet habe, einfach nur 0, 1 und Stern, das ist ein sehr

10:29.610 --> 10:31.810
einfaches Alphabet, da muss ich sehen, wie ich das darin kodieren

10:31.810 --> 10:32.110
kann.

10:32.890 --> 10:36.830
Ich gehe davon aus, dass ich eine Zustandsmenge immer durch Zahlen

10:36.830 --> 10:42.090
kodiere, von 0 bis N oder 1 bis N, das ist relativ egal.

10:43.310 --> 10:46.230
Und wenn ich irgendeine Turing-Maschine habe, dann hat die irgendeine

10:46.230 --> 10:50.410
feste Anzahl von Zuständen, die kann ich einfach durchzählen, kann ich

10:50.410 --> 10:51.850
damit beschreiben.

10:52.450 --> 10:54.430
Ich benenne die einfach durch Zahlen, die Zustände.

10:55.270 --> 10:58.070
Der Anfangszustand ist einheitlich für alle Turing-Maschinen und dann

10:58.070 --> 11:04.530
habe ich außerdem eine einheitliche Menge potenzieller Endzustände,

11:04.610 --> 11:08.990
die kann ich auch benennen und habe dadurch eine Möglichkeit, meine

11:08.990 --> 11:10.630
Zustände zu charakterisieren.

11:10.630 --> 11:14.450
Und dann muss ich dies alles kodieren, wie mache ich das?

11:15.010 --> 11:18.670
Wenn ich also sage, ich möchte die Tabelle kodieren, was steht in der

11:18.670 --> 11:19.290
Tabelle drin?

11:19.410 --> 11:23.650
In der Tabelle stehen diese einzelnen Definitionen drin.

11:24.170 --> 11:31.390
Wenn ich in einem Zustand SJ bin und eine Eingabe BI lese, dann will

11:31.390 --> 11:37.030
ich in einen Zustand SK gehen, ein Zeichen BR schreiben und eine

11:37.030 --> 11:38.650
Aktion XM ausführen.

11:39.750 --> 11:41.770
Und wie kann ich das kodieren?

11:41.910 --> 11:44.030
Dann nehme ich eine sogenannte unäre Kodierung.

11:44.850 --> 11:47.770
Ich schreibe einfach erstmal eine Null hin.

11:48.450 --> 11:52.970
Wenn ich also SJ, also den J-Zustand darstellen möchte, den kodieren

11:52.970 --> 11:55.670
möchte, schreibe ich einfach hinter eine Null J1.

11:56.410 --> 11:59.390
Das ist eine unäre Kodierung mit einem Zeichen, einfach so viele

11:59.390 --> 12:02.930
Striche gemacht, entsprechend der Zahl, die ich darstellen möchte.

12:03.510 --> 12:07.270
Danach steht das I-Zeichen, ich habe also wieder eine Null und dann

12:07.270 --> 12:09.370
I1, dann habe ich wieder eine Null.

12:09.470 --> 12:12.410
Dann habe ich K1, um den Zustand SK zu kodieren.

12:12.950 --> 12:16.050
Danach kommt das Zeichen BR, da müssen also R1 stehen.

12:16.470 --> 12:21.870
Und danach nehme ich hier also die Aktion XM, da habe ich sogar noch

12:21.870 --> 12:23.710
1, 2, 3, die ich kodieren muss.

12:23.910 --> 12:27.030
Also kann ich hier 1, 2 oder 3 Striche machen.

12:27.090 --> 12:28.450
Da stehen viel zu viele, aber das ist egal.

12:28.450 --> 12:31.790
Ich habe einfach hier angedeutet, die Zahl, die ich kodieren möchte,

12:32.550 --> 12:36.310
die Zahlen repräsentieren Zustände oder Eingabesymbole oder Ähnliches.

12:36.410 --> 12:38.510
An der Position weiß ich, was gerade kodiert wird.

12:39.370 --> 12:42.570
Ich schreibe einfach jeweils so viele Einsen hin, wie ich dort gerade

12:42.570 --> 12:43.570
kodieren muss.

12:43.810 --> 12:46.150
Und auf die Art und Weise kann ich also jetzt einen solchen Übergang

12:46.150 --> 12:46.570
darstellen.

12:46.710 --> 12:51.270
Ich weiß, dieses hier insgesamt entspricht genau dem, was ich hier

12:51.270 --> 12:52.410
oben eingerahmt habe.

12:52.930 --> 12:55.490
Die muss ich dann geeignet voneinander trennen, muss dann noch einen

12:55.490 --> 12:58.550
weiteren Null hinschreiben und dann weiß ich, jetzt kommt also kein

12:58.550 --> 13:00.390
solcher Übergang, sondern dann kommt irgendetwas anderes.

13:01.170 --> 13:04.390
Und auf die Art und Weise kann ich die Tabelle einfach hinschreiben

13:04.390 --> 13:04.830
aufs Band.

13:05.530 --> 13:08.490
Dann muss es natürlich eine Lage sein, wenn ich das interpretiere, das

13:08.490 --> 13:11.490
zu erkennen, dass dort diese bestimmten Zahlen kodiert sind.

13:11.570 --> 13:14.610
Ich muss also eine ziemlich große Menge an internen Zuständen haben,

13:14.790 --> 13:16.270
um das alles darstellen zu können.

13:16.570 --> 13:17.490
Das kann man aber machen.

13:20.670 --> 13:24.370
Dann wird also entsprechend die Konfiguration der Turing-Maschine

13:24.370 --> 13:27.810
daneben auf das Band geschrieben, wie ich gerade eben gesagt habe.

13:28.430 --> 13:32.010
Ich muss die Bandinschrift in aktuellem Zustand durch Nullen trennen,

13:32.050 --> 13:35.330
damit ich weiß, jetzt ist also die Beschreibung der Tabelle vorbei.

13:35.530 --> 13:37.210
Jetzt kommt also die Anfangskonfiguration.

13:38.410 --> 13:41.250
Ich muss dann angeben, wo auf dieser...

13:41.250 --> 13:45.290
Wenn wir das hier nochmal andeuten, ich habe hier die Beschreibung

13:45.290 --> 13:46.710
unserer Turing-Maschine.

13:46.870 --> 13:49.270
Da steht die jetzt, das ist die Kodierung der Turing-Maschine.

13:49.670 --> 13:51.890
Dann steht hier die Anfangskonfiguration.

13:52.090 --> 13:56.250
Ich sage, die sind getrennt durch entsprechende Nullen.

13:56.250 --> 14:08.970
Ich habe hier die aktuelle Bandinschrift und dann sind hier irgendwo

14:08.970 --> 14:10.250
drei Nullen.

14:10.990 --> 14:12.110
Dann kommt hier ein weiteres Zeichen.

14:12.230 --> 14:16.350
Da steht also ein gewisses Wort U, da steht ein Wort V.

14:16.890 --> 14:21.690
Und das erste Zeichen hier von diesem Wort V, das ich hier gerade

14:21.690 --> 14:23.690
hinschreiben wollte, das erste Zeichen davon.

14:24.510 --> 14:31.110
Hier ist irgendein Zeichen B-I und da steht dann mein V.

14:31.690 --> 14:35.130
Da, dieses Zeichen B-I, ist das aktuelle Zeichen unter dem Lesekopf.

14:35.790 --> 14:39.670
Und damit habe ich die aktuelle Konfiguration hingeschrieben.

14:40.410 --> 14:41.830
Der Zustand muss auch kodiert sein.

14:42.090 --> 14:43.730
Und ich habe eine Konfiguration.

14:43.970 --> 14:45.950
Jetzt muss ich nur dafür sorgen, dass ich in der Lage bin, das zu

14:45.950 --> 14:48.410
interpretieren, wie man das macht, schreibe ich Ihnen nicht

14:48.410 --> 14:49.030
ausführlich hin.

14:49.090 --> 14:50.530
Das kann man nachlesen.

14:50.530 --> 14:55.630
Und jetzt muss ich sukzessive die einzelnen Konfigurationen meiner

14:55.630 --> 14:56.850
Turing -Maschine simulieren.

14:56.950 --> 15:01.090
Ich habe also zu Anfang hier diese Konfiguration auf dem Band stehen.

15:01.730 --> 15:04.810
Rechts neben der Tabelle, mit der die Turing-Maschine beschrieben

15:04.810 --> 15:05.110
wird.

15:05.530 --> 15:09.610
Und dann werden sukzessive die nächsten Konfigurationen erzeugt.

15:09.610 --> 15:15.790
Es wird also das Eins-Strich erzeugt.

15:16.150 --> 15:21.750
Und dann entsprechend hier die nächste Konfiguration.

15:21.970 --> 15:23.730
Entsprechend auch die nächste Konfiguration.

15:24.530 --> 15:27.410
Und irgendwann bin ich dann fertig.

15:28.190 --> 15:34.230
Die Maschine hält in dem Augenblick, in dem die simulierte Turing

15:34.230 --> 15:37.110
-Maschine eine Endkonfiguration erreicht hat.

15:37.110 --> 15:39.590
Beziehungsweise danach geht die universelle Turing-Maschine auch in

15:39.590 --> 15:40.310
einen Endzustand.

15:40.830 --> 15:41.750
Das war jetzt sehr schnell.

15:42.230 --> 15:45.330
Was Sie sich merken müssen ist, ich kann jede Turing-Maschine

15:45.330 --> 15:48.530
beschreiben und diese Beschreibung auf ein Band schreiben.

15:48.990 --> 15:50.550
Wie man das kodiert, habe ich angedeutet.

15:50.770 --> 15:54.730
Und damit kann ich alles das, was eine Turing-Maschine kann, auf einer

15:54.730 --> 15:57.350
einzigen universellen Turing-Maschine kodieren.

15:57.770 --> 16:02.530
Und damit habe ich ein Modell, ein Gerät, mit dem ich jede Funktion

16:02.530 --> 16:05.710
berechnen kann, die durch eine Turing-Maschine berechenbar ist.

16:05.710 --> 16:09.870
Also jede berechenbare Funktion kann ich mit einer einzigen, sehr

16:09.870 --> 16:11.710
einfachen Maschine berechnen.

16:12.570 --> 16:14.910
Das ist schon mal eine ziemlich interessante Erkenntnis.

16:15.390 --> 16:18.650
Ich brauche nur eine einzige Maschine, wie so eine Turing-Maschine.

16:18.830 --> 16:20.290
Die brauche ich nur hinzuschreiben.

16:21.350 --> 16:23.970
Die sieht relativ kompliziert aus in den ganzen Übergangsfunktionen,

16:24.010 --> 16:26.750
weil ich in der Lage sein muss, das Ganze zu interpretieren von

16:26.750 --> 16:29.730
Tabellen und hinschreiben von Konfigurationen usw.

16:30.110 --> 16:32.090
Das muss ich alles machen können.

16:32.090 --> 16:36.670
Aber das ist eine Maschine, die im Prinzip ein Universalrechner ist,

16:36.850 --> 16:43.530
so wie ihr Smartphone oder irgendein Rechner, den Sie benutzen, auch

16:43.530 --> 16:46.350
ein Universalrechner ist, weil Sie dort Programme reinladen können.

16:48.270 --> 16:52.250
Also ich kann diese Turing-Maschine alle auf die Art und Weise

16:52.250 --> 16:55.550
simulieren und habe also hier diese Kodierungen.

16:55.550 --> 17:00.030
Jetzt habe ich also für jede Turing-Maschine so eine Beschreibung, die

17:00.030 --> 17:03.250
ich auf ein Band einer Turing-Maschine schreiben kann.

17:04.130 --> 17:07.190
Ich könnte es auch anders hinmalen, nicht so, sondern um anzudeuten,

17:07.310 --> 17:09.710
dass das irgendein Band-Inschrift ist.

17:10.030 --> 17:12.930
Ich habe also hier so eine lange Beschreibung einer Turing-Maschine.

17:14.050 --> 17:16.710
Jetzt kann ich mir natürlich diese ganzen Beschreibungen anschauen und

17:16.710 --> 17:20.310
ich kann die anordnen, nach ihrer Länge, kann die lexikografisch

17:20.310 --> 17:23.910
anordnen, irgendwie kann ich sie in eine Reihenfolge bringen.

17:23.910 --> 17:27.170
Und dann habe ich eine Anordnung aller Turing-Maschinen.

17:28.930 --> 17:33.690
Ich hatte ja schon gesagt, die Menge aller berechenbaren Funktionen

17:33.690 --> 17:37.710
ist abzählbar, weil sie alle durch endliche Texte beschrieben sind.

17:38.550 --> 17:43.750
Ich kann also auch die Turing-Maschinen alle in eine feste Reihenfolge

17:43.750 --> 17:44.050
bringen.

17:45.010 --> 17:46.130
Sie sind auch abzählbar.

17:46.830 --> 17:49.530
Ich kann meine Wörter alle in eine feste Reihenfolge bringen.

17:49.530 --> 17:54.570
Und dann kann ich natürlich einfach die anordnen, lexikografisch, die

17:54.570 --> 17:57.910
möglichen Turing-Maschinen mit allen möglichen Eingaben.

17:58.210 --> 18:02.150
Und so kann ich also alles das, was eine universelle Turing-Maschine

18:02.150 --> 18:06.090
machen soll, kann ich auf diese Art und Weise hier so systematisch

18:06.090 --> 18:08.210
anordnen und könnte die der Reihe nach alle abarbeiten.

18:08.310 --> 18:11.690
Das wird natürlich beliebig lange dauern, aber darauf kommt es jetzt

18:11.690 --> 18:12.030
nicht an.

18:12.030 --> 18:15.390
Die Frage ist, was kann ich damit eigentlich jetzt für Erkenntnisse

18:15.390 --> 18:19.030
gewinnen über diese berechenbaren Funktionen.

18:20.490 --> 18:26.310
Und zunächst mal kann ich eine Erkenntnis gewinnen, die ganz ähnlich

18:26.310 --> 18:29.110
ist zu dem, was wir vorher schon mal betrachtet hatten.

18:30.110 --> 18:36.570
Wir hatten gesagt, mit so einem Diagonalisierungsverfahren, dass es

18:36.570 --> 18:42.270
überabzählbar viele berechenbare Funktionen gibt.

18:42.270 --> 18:51.370
Quatsch, dass die Menge der berechenbaren Funktionen abzählbar ist.

18:53.750 --> 19:04.550
Wir hatten gesagt, dass die Menge aller Funktionen überabzählbar ist.

19:04.570 --> 19:07.750
Das heißt, ich kann eine Funktion definieren, die in der Menge der

19:07.750 --> 19:09.790
berechenbaren Funktionen nicht auftaucht.

19:10.530 --> 19:15.690
Ganz ähnlich zeigen wir jetzt, dass es eine Sprache gibt, die wir

19:15.690 --> 19:16.750
definieren können.

19:16.750 --> 19:21.810
Und Sie sehen, die ist ganz ähnlich wie die Funktion, die wir neulich

19:21.810 --> 19:22.590
definiert haben.

19:22.710 --> 19:24.610
Das war die Diagonalisierungsfunktion.

19:25.290 --> 19:27.110
Hier haben wir so etwas ganz Ähnliches.

19:27.850 --> 19:37.190
Wir definieren einfach eine Sprache N-A für Not Acceptable, so dass

19:37.190 --> 19:46.270
wir sagen, das Wort W-I in dieser Aufzählung W-1, W-2, W-3, W-4, das

19:46.270 --> 19:50.670
war unsere Aufzählung der ganzen Wörter.

19:51.870 --> 19:58.070
Das Wort W-I ist in der Sprache L-N-A genau dann, wenn dieses Wort von

19:58.070 --> 20:02.250
der Eaton Turing Maschine nicht erkannt wird.

20:03.810 --> 20:07.970
Dazu brauche ich also eine Nummerierung der Turing Maschinen.

20:08.030 --> 20:10.050
Da haben wir gesagt, wir können die lexikografisch anordnen.

20:10.490 --> 20:12.110
Wir finden dann die Eaton Turing Maschine.

20:12.590 --> 20:16.470
Wir haben das Eaton-Wort, dazu finden wir also zum Eaton-Wort die

20:16.470 --> 20:21.070
Eaton Turing Maschine und können feststellen, ob das Eaton-Wort oder

20:21.070 --> 20:24.170
wir definieren einfach, wenn das Eaton-Wort in der Sprache der Turing

20:24.170 --> 20:29.210
Maschine ist, dann ist es nicht in der Sprache L-N-A und umgekehrt.

20:29.990 --> 20:33.990
Und damit haben wir genau wieder so ein Diagonalisierungsverfahren,

20:34.190 --> 20:37.570
wie vorher auch bei diesem Beweis, dass die Menge der Funktionen

20:37.570 --> 20:44.890
überabziehbar ist und damit haben wir hier wieder diesen Widerspruch.

20:45.070 --> 20:52.350
Wenn wir annehmen, es gäbe eine Turing Maschine, die diese Sprache L-N

20:52.350 --> 20:57.710
-A akzeptieren kann, dann gibt es natürlich, wenn es eine solche

20:57.710 --> 21:05.130
Turing Maschine gäbe, dann wäre diese Turing Maschine in dieser Reihe

21:05.130 --> 21:11.410
der Turing Maschinen T1, T2, T3, T4 usw.

21:11.770 --> 21:16.430
Irgendwann wäre hier eine Maschine T gleich irgendein TJ, oder in dem

21:16.430 --> 21:20.790
Fall ein TJ, wäre da irgendwann da drin.

21:20.790 --> 21:32.570
Und dann hätte ich also hier diese Turing Maschine T wäre also eine

21:32.570 --> 21:34.150
Turing Maschine mit einem Index J.

21:34.710 --> 21:39.550
Und dann weiß ich, dieses Wort W-J ist aus der Sprache L-N-A, genau

21:39.550 --> 21:48.310
dann, wenn das W-J aus L von T ist.

21:48.310 --> 21:51.490
T ist diese Turing Maschine, die die Sprache L-N-A akzeptiert.

21:53.110 --> 21:58.530
Diese Sprache L von T ist aber eine Sprache L von TJ.

21:59.810 --> 22:07.270
Und damit ist das Element W-J, also wenn das Wort W-J aus L von TJ

22:07.270 --> 22:11.390
ist, dann ist es nach Definition, die hier oben steht, nicht aus L-N

22:11.390 --> 22:11.630
-A.

22:11.630 --> 22:14.570
Und das heißt, das W-J ist aus L-N-A genau, wenn es nicht drin ist,

22:14.650 --> 22:16.390
das ist ein Widerspruch, das kann also nicht sein.

22:16.450 --> 22:18.910
Das ist dieses einfache Diagonalisierungsschluss, wie wir es vorher

22:18.910 --> 22:19.650
auch gemacht haben.

22:20.210 --> 22:24.190
Also das kann man sich relativ schnell überlegen, wenn, oder da wir

22:24.190 --> 22:29.630
diese Wörter und die Turing Maschinen alle so anordnen, in einer

22:29.630 --> 22:35.430
Reihenfolge, lexikografische Reihenfolge, finden wir zu jeder Turing

22:35.430 --> 22:40.030
Maschine einen Index, der Beschreibung, die genau zu dieser Turing

22:40.030 --> 22:43.950
Maschine passt, und dann haben wir eben hier genau diesen Widerspruch,

22:44.090 --> 22:48.550
dass dann das entsprechend mit diesem Index versehene Wort zur Sprache

22:48.550 --> 22:53.670
gehört, genau dann, wenn es halt nach Definition nicht dazu gehören

22:53.670 --> 22:54.010
kann.

22:54.310 --> 22:55.590
Dann ist diese Annahme also falsch.

22:55.890 --> 22:59.190
Also, wir haben eine Sprache gefunden, von der wir wissen, die nicht

22:59.190 --> 23:04.050
außerhalb der Menge von Sprachen, die von Turing Maschinen akzeptiert

23:04.050 --> 23:04.550
werden können.

23:05.250 --> 23:10.470
Das ist natürlich ein sehr nicht konstruktiver Beweis.

23:11.150 --> 23:13.870
Es gibt also Sprachen, die nicht in L0 enthalten sind.

23:14.450 --> 23:19.890
Und damit haben wir uns überlegt, dass das eine Teilmenge aller

23:19.890 --> 23:20.870
möglichen Sprachen ist.

23:20.910 --> 23:22.230
Das wussten wir eigentlich schon vorher.

23:22.290 --> 23:26.710
Wir hatten gesagt, die Menge L0, der auch von Typ 0 Grammatiken

23:26.710 --> 23:31.610
erzeugt werden kann, oder es gibt Sprachen, die nicht durch solche

23:31.610 --> 23:32.930
Grammatiken beschreibbar sind.

23:33.730 --> 23:36.150
Und nun ist die Frage, wie kann man Turing Maschinen eigentlich

23:36.150 --> 23:37.630
systematisch konstruieren?

23:38.050 --> 23:40.910
Wenn wir Programme schreiben, haben wir da systematische

23:40.910 --> 23:41.770
Vorgehensweisen.

23:42.470 --> 23:45.890
Ich kann im Prinzip das, was wir in höhere Programmiersprachen auch

23:45.890 --> 23:46.950
hier simulieren.

23:47.630 --> 23:51.350
Ich könnte also sagen, ich schreibe mir eine Turing Maschine, die

23:51.350 --> 23:54.550
berechnet eine Addition, eine die schreibt eine Multiplikation, einen

23:54.550 --> 23:55.050
Vergleich.

23:55.650 --> 23:59.770
Oder ich kann irgendwelche weiteren Strukturen definieren über Turing

23:59.770 --> 24:03.190
Maschinen und kann die einfach alle dann geeignet zusammensetzen.

24:03.630 --> 24:06.090
Und dann könnte man also sagen, ich habe eine Turing Maschine für eine

24:06.090 --> 24:10.790
Folge von Anweisungen, ich setze die entsprechend nacheinander, ich

24:10.790 --> 24:13.810
kann eine Wiederholung von Turing Maschinen machen, ich kann eine

24:13.810 --> 24:17.110
Verzweigung machen, auf die Art und Weise könnte ich sagen, ich kann

24:17.110 --> 24:21.270
systematisch eine komplexere Turing Maschinen Struktur definieren und

24:21.270 --> 24:23.350
habe dann so etwas ähnliches wie eine höhere Programmiersprache.

24:23.350 --> 24:29.950
Das ist aber etwas abstrakt eigentlich, dass ich sage, ich könnte im

24:29.950 --> 24:33.030
Prinzip Turing Maschinen ähnlich definieren, wie ich ein

24:33.030 --> 24:34.650
höhersprachliches Programm definiere.

24:35.130 --> 24:37.310
Natürlich machen wir dann lieber gleich ein höhersprachliches

24:37.310 --> 24:41.710
Programm, aber es ist wichtig zu wissen, auch andersrum, ich kann das,

24:41.790 --> 24:45.130
was ein höhersprachliches Programm machen kann, auch im Endeffekt

24:45.130 --> 24:48.310
simulieren durch eine Turing Maschine.

24:48.310 --> 24:52.830
Und das ist das, was wir gerade eben uns überlegt haben, ich kann jede

24:52.830 --> 24:55.530
Turing Maschine entsprechend auf einer einzigen simulieren.

24:57.230 --> 25:01.270
Das, was wir damit eigentlich herausfinden, ist, dass zunächst einmal

25:01.270 --> 25:05.190
jede Turing berechenbare Funktion sicherlich die Anforderungen erfüllt

25:05.190 --> 25:07.170
an eine intuitiv berechenbare Funktion.

25:07.270 --> 25:09.810
Was wir da beschrieben hatten, ist alles durch diese Turing

25:09.810 --> 25:12.050
berechenbaren Funktionen erfüllt.

25:12.050 --> 25:16.550
Wenn wir uns also alle intuitiv berechenbaren Funktionen anschauen,

25:16.630 --> 25:19.130
sind die Turing Maschinen ein Teil davon.

25:20.170 --> 25:24.070
Es war tatsächlich die Turing Maschine das erste formale Modell zur

25:24.070 --> 25:26.390
Charakterisierung intuitiv berechenbarer Funktionen.

25:26.870 --> 25:30.810
Nun ist die Frage, könnte ich solche berechenbaren Funktionen auch

25:30.810 --> 25:32.050
anders charakterisieren?

25:33.490 --> 25:36.030
Tatsächlich gibt es viele solche Kalküle.

25:36.850 --> 25:43.830
Es gibt aber eine sogenannte These, die Church These, die sagt, jede

25:43.830 --> 25:47.170
im intuitiven Sinne berechenbare Funktion ist auf Turing berechenbar.

25:47.330 --> 25:54.450
Also es gibt verschiedenste Sachen, es gibt den Lambda-Kalkül, es gibt

25:54.450 --> 25:59.790
sogenannte Postsysteme, hat mit Briefträgern nichts zu tun, sondern

25:59.790 --> 26:01.870
das sind Ersetzungssysteme.

26:01.870 --> 26:07.110
Es gibt eine ganze Reihe von Maschinenmodellen, mit denen man auf

26:07.110 --> 26:11.150
unterschiedliche Art und Weise Berechenbarkeit charakterisiert hat.

26:11.730 --> 26:15.110
Das ist in den 30er Jahren passiert, des vorigen Jahrhunderts.

26:15.530 --> 26:21.210
Und da hat man sich dann überlegt, kann ich das, was ich mit dem einen

26:21.210 --> 26:23.590
Modell machen kann, auch mit dem anderen Modell darstellen.

26:23.590 --> 26:27.490
Und dann haben wir festgestellt, alle diese Modelle, die irgendwie die

26:27.490 --> 26:31.070
intuitive Berechenbarkeit charakterisieren sollen, die sind im Prinzip

26:31.070 --> 26:32.210
ineinander überführbar.

26:33.470 --> 26:37.490
Und daraus kommt dann diese Church These, Church war auch einer dieser

26:37.490 --> 26:42.130
Logiker, der sagt, jede im intuitiven Sinne berechenbare Funktion ist

26:42.130 --> 26:43.090
auf Turing berechenbar.

26:43.370 --> 26:44.730
Das kann man natürlich nicht beweisen.

26:45.810 --> 26:49.770
Ich kann ja nur wieder ein neues Modell finden und sagen, kann ich

26:49.770 --> 26:54.510
dieses neue Modell auch über die Turing-Maschine wieder äquivalent

26:54.510 --> 26:55.450
darstellen.

26:56.130 --> 26:59.330
Aber ich kann nichts beweisen über eine intuitiv berechenbare

26:59.330 --> 27:03.130
Funktion, weil diese intuitive Charakterisierung nicht formal ist.

27:03.930 --> 27:07.210
Alle diese Modelle sind formal, aber sind deswegen auch im Prinzip

27:07.210 --> 27:09.730
eingeschränkt, weil sie eine spezielle Sicht auf die berechenbaren

27:09.730 --> 27:10.410
Funktionen bieten.

27:10.810 --> 27:12.870
Sie sind aber im Prinzip alle äquivalent.

27:12.870 --> 27:15.590
Das ist also eine wichtige Erkenntnis.

27:16.130 --> 27:21.950
Ich habe also damit, je nachdem, welche Art von Berechenbarkeit mich

27:21.950 --> 27:26.530
interessiert, kann ich mich auf ein bestimmtes Modell verlassen.

27:26.990 --> 27:30.270
Ich weiß, das ist egal, ob ich eine Turing-Maschine verwende oder

27:30.270 --> 27:33.490
meinetwegen den Lambda-Kalkül, ich habe die gleiche Klasse von

27:33.490 --> 27:34.570
Funktionen.

27:34.990 --> 27:38.970
Aber je nach meiner Fragestellung kann ich einfach das mir passende

27:38.970 --> 27:39.850
Modell verwenden.

27:39.850 --> 27:43.210
Das hatten wir früher schon mal gesehen, als wir gesehen hatten, die

27:43.210 --> 27:47.830
Beschreibung der durch endliche Automaten beschreibbaren Funktionen.

27:47.850 --> 27:50.870
Das konnte ich auch durch reguläre Ausdrücke machen oder durch

27:50.870 --> 27:51.450
Grammatiken.

27:52.590 --> 27:55.210
Wir können also in diesem Sinne auf einer höheren, also einer

27:55.210 --> 27:58.530
wenigstens größeren Klasse, alle diese verschiedenen Systeme

27:58.530 --> 28:00.290
äquivalent verwenden.

28:00.770 --> 28:05.690
Man geht sogar davon aus, dass man mit Turing-Maschinen auch die

28:05.690 --> 28:11.430
Rechenzeit im Prinzip vollständig erfasst, bis auf polynomielle

28:11.430 --> 28:12.770
Unterschiede.

28:13.230 --> 28:18.950
Das heißt, wenn ein Problem effizient polynomiell lösbar ist.

28:18.950 --> 28:29.510
Polynomiell lösbar heißt, ich habe irgendwie die Zeit für solch eine

28:29.510 --> 28:37.590
Funktion oder für ein Problem P auf Problemgrößen der Größe N wäre

28:37.590 --> 28:42.610
dann im Prinzip aus O von N hoch irgendein K.

28:43.510 --> 28:47.010
Das wäre eine polynomiell berechenbare Funktion, linear oder

28:47.010 --> 28:51.670
quadratisch oder kubisch oder was immer Sie da als Exponenten K haben.

28:52.030 --> 28:55.770
Ist genau dann effizient polynomiell lösbar, wenn es von Turing

28:55.770 --> 28:58.570
-Maschinen in polynomieller Zeit gelöst werden kann.

28:59.090 --> 29:03.610
Also in Turing-Maschinen, das wäre dann meinetwegen das T und hier die

29:03.610 --> 29:11.210
Zeit dieser Turing-Maschine von N aus O von irgendeinem N hoch R.

29:11.970 --> 29:16.510
Auch polynomiell, nicht unbedingt die gleiche Zeit, aber polynomiell.

29:17.130 --> 29:20.470
Und da zu dieser Art Charakterisierung kommen wir noch wieder zurück.

29:21.830 --> 29:24.670
Die Folgerungen aus dieser Georgischen These sind also, es ist

29:24.670 --> 29:28.610
ausreichend Turing-Maschinen zu betrachten, man darf aber das Modell

29:28.610 --> 29:31.310
nehmen, das einem gerade für die aktuelle Fragestellung passt.

29:32.070 --> 29:33.070
Da muss man die natürlich kennen.

29:34.710 --> 29:37.670
Dann ist es ja so, dass natürlich jeder aufzählbare Menge auch Turing

29:37.670 --> 29:40.090
aufzählbar, jeder entscheidbare Menge auch Turing entscheidbar und

29:40.090 --> 29:43.590
umgekehrt, das sind alles einfache Folgerungen aus dieser These.

29:44.430 --> 29:53.370
Und jetzt kommen wir zu einem Problem, an dem ich Ihnen zeigen will,

29:53.570 --> 29:56.410
dass dieses Problem eine besondere Eigenschaft hat.

29:57.310 --> 30:01.570
Es ist zunächst mal sehr naheliegend, solch eine Frage zu stellen.

30:02.230 --> 30:07.510
Leider ist es so, dass diese Frage negativ beantwortet werden muss.

30:07.510 --> 30:11.690
Die Frage lautet, kann ich ein tolles Werkzeug bauen?

30:12.070 --> 30:15.830
Ein Werkzeug, das jeder Tutor sich wünscht oder jeder, der Aufgaben

30:15.830 --> 30:17.230
von Studenten bearbeiten muss.

30:17.330 --> 30:20.670
Die Studenten haben Programme zu schreiben und ich muss feststellen,

30:21.350 --> 30:25.250
hält das Programm, das dieser Student mir gegeben hat, hält dieses

30:25.250 --> 30:29.370
Programm für jede beliebige Eingabe an oder nicht?

30:30.550 --> 30:33.150
Natürlich soll ein Programm immer anhalten können.

30:34.170 --> 30:35.510
Will man ja gerne haben.

30:35.630 --> 30:36.550
Aber kann ich das überprüfen?

30:36.670 --> 30:40.450
Kann ich mir ein Werkzeug schreiben, das einfach auf so ein Programm

30:40.450 --> 30:43.270
guckt und eine Eingabe und dann nach endlich vielen Schritten

30:43.270 --> 30:47.410
feststellt, wird dieses Programm für diese Eingabe anhalten oder

30:47.410 --> 30:47.730
nicht?

30:49.790 --> 30:54.050
Und dieses Problem ist leider nicht machbar.

30:54.150 --> 30:55.830
Ich kann einen solchen Algorithmus nicht angeben.

30:56.770 --> 30:59.530
Ich kann also keinen Algorithmus angeben, ein endlich beschriebenes

30:59.530 --> 31:03.870
Verfahren, das für ein beliebiges Programm mit einer beliebigen

31:03.870 --> 31:07.390
Eingabe entscheidet, ob dieses Programm für diese Eingabe anhält oder

31:07.390 --> 31:07.730
nicht.

31:08.410 --> 31:10.990
Das Problem, das ich Ihnen hier beschreibe, das Halteproblem, ist sehr

31:10.990 --> 31:16.110
einfach zu beschreiben, intuitiv klar, was man möchte und wir können

31:16.110 --> 31:17.950
dafür kein endliches Verfahren angeben.

31:18.810 --> 31:23.930
Für spezielle Problemklassen können wir das, aber für allgemeine

31:23.930 --> 31:25.170
leider nicht.

31:26.390 --> 31:29.730
Und diese Aussage werden wir jetzt beweisen.

31:30.530 --> 31:34.530
Mit den Elementen, die ich Ihnen gerade alle vorgestellt habe, werden

31:34.530 --> 31:37.750
Sie sehen, wir brauchen dort alle diese Teile, die wir gerade gemacht

31:37.750 --> 31:41.350
haben, um festzustellen, dass dieses Halteproblem tatsächlich

31:41.350 --> 31:42.390
unentscheidbar ist.

31:43.390 --> 31:49.230
Und wir nehmen einfach an, dass es eine Maschine gäbe, die wir mit H

31:49.230 --> 31:53.690
bezeichnen, eine Haltemaschine, die entscheiden kann, ob eine

31:53.690 --> 31:57.250
beliebige Turingmaschine, also das ist unsere Haltemaschine H, und die

31:57.250 --> 32:01.790
bekommt jetzt auf ihr Band eine Beschreibung einer Turingmaschine und

32:01.790 --> 32:02.990
ein Wort reingeschrieben.

32:04.450 --> 32:10.870
Und dann soll diese Haltemaschine H sich das alles anschauen und soll

32:10.870 --> 32:15.410
feststellen, ob die Turingmaschine T mit dieser Eingabe W anhält oder

32:15.410 --> 32:15.810
nicht.

32:16.370 --> 32:18.290
Wir sagen, es gibt so eine Haltemaschine.

32:18.290 --> 32:20.750
Dann gucken wir mal, was daraus passiert.

32:20.830 --> 32:25.050
Wir werden zeigen, wenn es eine solche Haltemaschine gibt, dann können

32:25.050 --> 32:30.070
wir eine andere Maschine konstruieren, eine Maschine T, die diese

32:30.070 --> 32:32.050
Sprache LNA akzeptiert.

32:33.310 --> 32:36.550
LNA, das war die Sprache, die wir uns gerade überlegt hatten, als

32:36.550 --> 32:40.130
diese Sprache, die über dieses Diagonalisierungsverfahren definiert

32:40.130 --> 32:40.430
war.

32:40.430 --> 32:49.130
Das ITE-Wort ist in dieser Sprache LNA, wenn es durch die ITE

32:49.130 --> 32:53.010
-Turingmaschine nicht akzeptiert werden kann und umgekehrt.

32:53.830 --> 32:58.070
Diese Maschine T, die wir jetzt also konstruieren wollen, würde

32:58.070 --> 32:59.530
folgendermaßen arbeiten.

32:59.850 --> 33:04.610
Wir müssen also davon ausgehen, dass wir eine Eingabe bekommen, W.

33:06.990 --> 33:12.730
Und wir wollen feststellen, ob dieses Wort W zu der Sprache LNA gehört

33:12.730 --> 33:13.830
oder nicht.

33:14.690 --> 33:15.850
Das muss entschieden werden.

33:16.970 --> 33:18.590
Was soll diese Maschine tun?

33:18.690 --> 33:19.590
Wie kann die arbeiten?

33:20.970 --> 33:25.570
Wir fangen damit an, dass wir ein I bestimmen, sodass dieses Wort W

33:25.570 --> 33:30.570
ist ja irgendein Wort in der Aufzählung dieser ganzen Wörter.

33:31.990 --> 33:35.530
Kann ich in der Reihe nach durchlaufen, durch die ganzen Wörter, dann

33:35.530 --> 33:38.530
habe ich das ITE-Wort, den Index I bestimmt.

33:39.590 --> 33:41.870
Ich habe gesagt, wie wir die Wörter anordnen wollen.

33:42.570 --> 33:45.470
Wir wissen, wie wir Turingmaschinen kodieren, die kann ich der Reihe

33:45.470 --> 33:46.630
nach durchlaufen.

33:48.430 --> 33:55.850
Und komme dann irgendwann zu der Kodierung der ITEN-Turingmaschine,

33:55.970 --> 33:57.570
die sind ja auch irgendwie alle angeordnet.

33:58.610 --> 34:05.630
Und jetzt simuliere ich einfach diese Haltemaschine, von der wir

34:05.630 --> 34:07.010
gesagt haben, es gibt sie.

34:07.810 --> 34:16.230
Die simuliere ich mit der Eingabe TI, also diese ITE-Turingmaschine

34:16.230 --> 34:17.870
und dem WI.

34:17.990 --> 34:20.810
Ich habe also jetzt die Haltemaschine, die lasse ich jetzt laufen, mit

34:20.810 --> 34:22.450
der Eingabe TI und WI.

34:22.450 --> 34:28.450
Die Haltemaschine liefert mir als Antwort, ob die Turingmaschine TI

34:28.450 --> 34:30.810
bei Eingabe von WI hält oder nicht.

34:32.370 --> 34:36.010
Und jetzt kann ich also eine Frage stellen, kann einen Test machen,

34:36.610 --> 34:42.490
wenn das TI angesetzt auf WI hält.

34:42.710 --> 34:44.690
Diesen Test kann ich beantworten.

34:45.210 --> 34:46.390
Das macht meine Haltemaschine.

34:47.210 --> 34:55.690
Die simuliert die Maschine TI und guckt nach, ob die Maschine TI bei

34:55.690 --> 34:56.310
WI hält.

34:56.670 --> 34:58.710
Die Haltemaschine sagt ja oder nein.

34:59.590 --> 35:05.430
Wenn also diese Turingmaschine TI angesetzt auf WI hält, dann mache

35:05.430 --> 35:06.150
ich etwas.

35:07.910 --> 35:15.690
Ich stelle fest, ob das WI aus dem L von TI ist.

35:15.690 --> 35:22.270
Die Haltemaschine sagt mir nur, dass TI hält bei Eingabe von WI oder

35:22.270 --> 35:22.650
nicht.

35:23.710 --> 35:27.730
Jetzt, wenn ich weiß, die Maschine hält, dann simuliere ich einfach

35:27.730 --> 35:31.670
diese Turingmaschine TI und ich weiß ja, sie hält bei Eingabe von WI.

35:31.790 --> 35:34.370
Das heißt, ich brauche nur eine gewisse Zeit zu warten.

35:34.850 --> 35:38.670
Dann habe ich eine Antwort auf diesen Test, ob das ITE-Wort WI in der

35:38.670 --> 35:41.050
Sprache dieser Turingmaschine TI drin ist.

35:41.790 --> 35:48.410
Und wenn es drin ist, dann weiß ich, dann ist dieses Wort WI nicht in

35:48.410 --> 35:50.830
der Sprache LNA.

35:51.490 --> 35:55.270
Das heißt, dann machen wir die Ausgabe FALSE, das ist dieser Teil hier

35:55.270 --> 35:55.490
oben.

35:56.430 --> 36:04.050
Wenn das WI nicht in L von TI ist, dann sage ich, dann ist die Ausgabe

36:04.050 --> 36:06.930
TRUE, weil dann das W aus LNA ist.

36:07.810 --> 36:11.250
Und das ist alles in endlicher Zeit ausführbar, weil ich angenommen

36:11.250 --> 36:16.070
habe, ich habe eine Haltemaschine, die in der Lage ist, für eine

36:16.070 --> 36:19.810
Turingmaschine bei Eingabe eines Wortes in endlicher Zeit

36:19.810 --> 36:23.370
festzustellen, ob diese Turingmaschine bei Eingabe von WI halten wird

36:23.370 --> 36:23.830
oder nicht.

36:25.070 --> 36:30.850
Damit habe ich hier eine Maschine konstruieren können, die für jedes

36:30.850 --> 36:34.870
Wort feststellen kann, ob das Wort in LNA liegt oder nicht.

36:34.870 --> 36:39.750
Und wir wissen natürlich, das andere ist natürlich auch, wenn jetzt

36:39.750 --> 36:44.770
hier die Haltemaschine gesagt hat, diese Turingmaschine TI hält

36:44.770 --> 36:50.770
angesetzt auf WI nicht, dann weiß ich, wenn sie nicht hält, der

36:50.770 --> 36:54.890
Eingabe von WI, dann ist dieses Wort WI nicht in der Sprache von TI.

36:55.650 --> 36:59.670
Wenn es nicht in der Sprache von TI ist, ist es aber in der Sprache

36:59.670 --> 37:04.490
meiner LNA, das heißt, dann kann ich auch die Ausgabe TRUE machen.

37:05.770 --> 37:11.730
Damit habe ich also alle Fälle abgehakt und habe damit den Widerspruch

37:11.730 --> 37:16.130
zu dem Satz, den wir gerade vorher bewiesen hatten, dass die Sprache

37:16.130 --> 37:18.870
LNA von keiner Turingmaschine akzeptiert werden kann.

37:20.230 --> 37:24.350
Das kam nur dadurch zustande, dass wir angenommen haben, es gibt eine

37:24.350 --> 37:27.750
Turingmaschine, die das Halteproblem lösen kann.

37:27.810 --> 37:29.970
Also ist das Halteproblem nicht lösbar.

37:30.570 --> 37:34.390
Da könnte man sagen, na gut, ist ja auch ziemlich weit hergeholt, dass

37:34.390 --> 37:36.650
man für ein beliebiges Programm, ein beliebiges Wort das immer

37:36.650 --> 37:41.250
entscheiden möchte, aber Sie werden gleich noch sehen, dass man dort

37:41.250 --> 37:45.970
noch eine Reihe anderer Formulierungen finden kann, von Problemen, die

37:45.970 --> 37:49.490
sehr praktisch aussehen, die alle nicht entscheidbar sind.

37:49.930 --> 37:54.890
Also wenn Sie im Job stehen und Ihnen wird gesagt, Sie haben doch mal

37:54.890 --> 37:58.550
was gehört über kontextfreie Grammatiken und jetzt gebe ich Ihnen hier

37:58.550 --> 38:02.310
zwei kontextfreie Grammatiken und Sie sollen feststellen, ob die

38:02.310 --> 38:03.410
äquivalent sind.

38:03.730 --> 38:07.290
Typische Aufgabe, die ein Tutor lösen muss bei uns, der kriegt

38:07.290 --> 38:10.030
irgendwelche studentischen Lösungen geliefert, der möchte sich ein

38:10.030 --> 38:12.910
Werkzeug schreiben, um das für beliebige Eingaben, beliebige

38:12.910 --> 38:15.870
kontextfreie Grammatiken festzustellen, sind die äquivalent, erzeugen

38:15.870 --> 38:17.030
die die gleiche Sprache oder nicht.

38:17.890 --> 38:24.130
Man kann zeigen, dass dieses Problem genauso nicht entscheidbar ist

38:24.130 --> 38:24.790
wie das Halteproblem.

38:24.790 --> 38:26.430
Man kann es zurückführen auf das Halteproblem.

38:27.390 --> 38:33.390
Genauso die Frage, also hier oben, das war klar, ob ein Programm für

38:33.390 --> 38:35.650
eine Eingabe W anhält, das ist das gleiche, wie ob eine Turing

38:35.650 --> 38:38.030
-Maschine für eine Eingabe anhält oder nicht.

38:38.530 --> 38:40.970
Dann, ob ein Programm P total korrekt ist.

38:41.110 --> 38:45.770
Total korrekt heißt, also partiell korrekt heißt, wenn ein Programm

38:45.770 --> 38:51.970
anhält, ist die Ausgabe korrekt, das heißt entsprechend der

38:51.970 --> 38:54.920
Spezifikation des Programms die richtige Ausgabe.

38:55.450 --> 38:59.570
Total korrekt heißt, das Programm hält für jede Eingabe an und dann

38:59.570 --> 39:00.850
ist die Ausgabe auch korrekt.

39:01.530 --> 39:04.190
Die andere Frage ist, ich habe zwei beliebige Programme und möchte nur

39:04.190 --> 39:05.550
feststellen, machen die das gleiche?

39:07.410 --> 39:10.370
Da kann man sich leicht überlegen, dass dieses Problem sofort

39:10.370 --> 39:11.850
überführbar ist auf das Halteproblem.

39:12.410 --> 39:16.250
Ich gucke mir einfach, ich habe also hier ein Programm P, das ist hier

39:16.250 --> 39:21.010
mein Programm, ich gebe einfach, wenn jemand sagt, ich kann das, für

39:21.010 --> 39:26.010
beliebige Programme überprüfen, ob die äquivalent sind, dann schreibe

39:26.010 --> 39:30.990
ich hier ein ganz einfaches Programm hin, das einfach nur eine

39:30.990 --> 39:32.030
Schleife ausführt.

39:32.990 --> 39:38.510
Dieses Programm hält nie an, das läuft beliebig lange, nur eine

39:38.510 --> 39:39.270
endliche Schleife.

39:39.270 --> 39:46.590
Und wenn ich sage, dieses Programm hier, dieses Programm Q, ist das

39:46.590 --> 39:50.190
Programm P äquivalent zu dem Q, dann muss ich feststellen, ob das

39:50.190 --> 39:54.350
Programm P tatsächlich auch für jede Angabe nicht hält.

39:55.850 --> 39:57.270
Das ist äquivalent zum Halteproblem.

39:58.750 --> 40:04.150
Und insofern, es gibt sehr einfache Transformationen dort und Sie

40:04.150 --> 40:09.630
sehen auf einmal, es gibt viele durchaus interessante, praxisrelevante

40:09.630 --> 40:13.390
Probleme, von denen man zeigen kann, die sind nicht entscheidbar.

40:13.930 --> 40:16.550
Wenn Sie so einen Auftrag kriegen, so ein Programm zu liefern, können

40:16.550 --> 40:21.330
Sie sofort sagen, das ist leider eine Aufgabe, die ist nicht zu

40:21.330 --> 40:21.750
erledigen.

40:22.270 --> 40:24.410
Ich kann nicht beweisen, dass das nicht geht, weil ich es auf

40:24.410 --> 40:25.770
Halteproblem zurückführen kann.

40:26.950 --> 40:33.230
Das geht also immer darum, dass ich kein allgemeines Verfahren angeben

40:33.230 --> 40:37.510
kann, das für beliebige Instanzen dieser Probleme die richtige Antwort

40:37.510 --> 40:37.910
liefert.

40:38.270 --> 40:41.050
Wenn man solche Situationen hat, muss man sehen, ob man irgendwelche

40:41.050 --> 40:43.750
Einschränkungen finden kann, für die das dann durchaus der Fall ist,

40:43.850 --> 40:45.770
für die man durchaus Antworten liefern kann.

40:46.470 --> 40:47.750
Und wir haben das ja auch gemacht.

40:48.410 --> 40:53.290
Wir hatten unsere Sprachklassen L3, L2, L1 und dann L0.

40:53.290 --> 40:57.230
Wir hatten gesehen, für L1 können wir das Wortproblem, das ist genau

40:57.230 --> 40:59.070
so ein Problem, können wir immer entscheiden.

40:59.910 --> 41:02.770
Dazwischen liegen dann irgendwo die entscheidbaren Sprachen zwischen

41:02.770 --> 41:03.710
L1 und L0.

41:04.250 --> 41:08.650
Und hier oben drüber sind die Sprachen, die nicht entscheidbar sind.

41:09.650 --> 41:15.790
Und also insofern haben wir hier, also auch hier drin sind schon nicht

41:15.790 --> 41:18.430
entscheidbare Sprachen in dem L0.

41:18.430 --> 41:22.110
Und da oben drin hat man gesehen, sind auch Sprachen wie diese Sprache

41:22.110 --> 41:22.530
LNA.

41:23.690 --> 41:28.390
Jetzt gibt es noch viele andere Charakterisierungen von Sprachen und

41:28.390 --> 41:32.350
auch von anderen Grammatiktypen, die ich nur ganz kurz ansprechen

41:32.350 --> 41:37.490
möchte, die anders arbeiten, die Sprachen anders charakterisieren.

41:39.450 --> 41:40.530
Oh, es gibt eine Frage.

41:40.810 --> 41:42.210
Entschuldigung, da habe ich gar nicht drauf geachtet.

41:43.370 --> 41:46.190
Können Sie nochmal kurz erklären, was intuitiv berechenbar bedeutet?

41:46.190 --> 41:49.070
Das hatte ich ganz zu Anfang der Vordesung heute nochmal wiederholt.

41:49.970 --> 41:54.910
Intuitiv berechenbar war, dass ich eine Funktion dann als berechenbar

41:54.910 --> 42:03.370
beschreibe, wenn ich sie auf einem endlichen Stück Papier irgendwie

42:03.370 --> 42:04.250
beschreiben kann.

42:04.370 --> 42:10.930
Ich kann hier eine Beschreibung meiner Funktion irgendwie erstellen.

42:11.930 --> 42:13.250
Endlich beschreibbar.

42:13.990 --> 42:18.430
Und wenn ich jetzt irgendein Argument angebe, also das ist die

42:18.430 --> 42:24.910
Beschreibung meiner Funktion f, und wenn ich jetzt irgendein f von w

42:24.910 --> 42:30.310
berechnen möchte, irgendein Argument, dann kann ich das hier in

42:30.310 --> 42:32.470
endlicher Zeit tatsächlich berechnen.

42:32.470 --> 42:41.650
Also wenn ich ein w gegeben habe, kann ich zu dem f von w in endlich

42:41.650 --> 42:42.630
vielen Schritten kommen.

42:43.450 --> 42:48.670
Endliche Zeit, um ein endlich beschriebenes Verfahren oder eine

42:48.670 --> 42:54.290
endlich beschriebene Funktion für jedes Argument tatsächlich berechnen

42:54.290 --> 42:54.870
zu können.

42:55.430 --> 42:59.190
Das ist intuitiv, weil ich nicht sage, was hier genau für eine

42:59.190 --> 43:00.030
Codierung drin sein muss.

43:00.030 --> 43:01.330
Das ist irgendeine beliebige Codierung.

43:01.870 --> 43:04.750
Und diese irgendeine beliebige Codierung, die ich hinschreiben kann

43:04.750 --> 43:09.590
als endlicher Text, das ist halt zunächst mal keine formale

43:09.590 --> 43:09.910
Definition.

43:10.010 --> 43:12.850
Es wird formal in dem Augenblick, wo ich sage, durch eine Turing

43:12.850 --> 43:13.810
-Maschine beschreibbar.

43:14.630 --> 43:15.750
Das ist eine Spezialisierung.

43:16.670 --> 43:18.690
Könnt ihr auch sagen, durch einen endlichen Automaten beschreibbar.

43:19.670 --> 43:21.510
Das wäre nicht universell.

43:22.530 --> 43:24.570
Da gibt es dann noch mehr Funktionen.

43:25.330 --> 43:29.850
Also das ist das, was zu Beginn dieses Kapitels stand als intuitiv

43:29.850 --> 43:30.430
berechenbar.

43:30.870 --> 43:34.050
Die ganzen Endlichkeit-Anforderungen, die Allgemeinheitsanforderungen,

43:34.490 --> 43:37.270
dass ich eben auch das für jede Eingabe machen kann.

43:37.670 --> 43:42.410
Nicht nur bei Sortierproblemen, nicht nur einfach eine Folge sortieren

43:42.410 --> 43:43.730
kann, sondern jede beliebige Folge.

43:43.830 --> 43:46.250
Dann habe ich ein allgemeines Sortierproblem gelöst.

43:47.150 --> 43:50.910
Also das war diese Definition der allgemeinen oder intuitiven

43:50.910 --> 43:51.710
Berechenbarkeit.

43:51.710 --> 43:54.930
Und jetzt zu den Lindenmeier-Systemen.

43:54.970 --> 43:56.230
Was sind Lindenmeier-Systeme?

43:56.330 --> 43:57.590
Das sind ganz interessante Geschichten.

43:57.750 --> 44:02.070
Der Lindenmeier war ein, der hieß Aristide Lindenmeier, ein

44:02.070 --> 44:07.410
Systembiologe, der formale Modelle für das Wachstum von biologischen

44:07.410 --> 44:11.450
Strukturen gesucht hat.

44:12.410 --> 44:17.090
Und der hat zum Beispiel festgestellt, man kann das Wachstum von

44:17.090 --> 44:19.570
gewissen Strukturen so darstellen.

44:19.570 --> 44:23.710
Ich kann einen Strich ersetzen dadurch, dass ich hier noch so links

44:23.710 --> 44:25.230
und rechts einen Strich ranmale.

44:25.670 --> 44:28.690
Dann kann ich also einen Strich und diesen Strich, da kann ich wieder

44:28.690 --> 44:30.750
irgendetwas ranmalen.

44:31.030 --> 44:33.570
Und dann kann ich das hier auch wieder machen.

44:33.950 --> 44:35.370
Und ich kann das da überall machen.

44:36.470 --> 44:39.790
Und ich kann auf einmal Strukturen erzeugen, die sehen aus wie

44:39.790 --> 44:41.470
irgendwelche Farne oder ähnliches.

44:42.110 --> 44:43.550
Und ich habe eine ganz einfache Regel.

44:44.970 --> 44:46.810
Das war hier im Prinzip die Regel.

44:46.810 --> 44:50.130
Ich kann einen solchen Strich ersetzen durch eine solche Struktur, wo

44:50.130 --> 44:53.050
ich irgendwas daran male.

44:54.190 --> 44:58.190
Das hier entspricht dem, dass ich eine Regel habe, die meinetwegen

44:58.190 --> 45:08.170
sagt, ich kann A, A, A ersetzen durch, ich schreibe es anders, das

45:08.170 --> 45:09.750
soll eine kontextfreie Regel sein.

45:10.430 --> 45:16.630
Ich habe eine Regel, die ersetzt A durch meinetwegen A, B, A, C.

45:17.550 --> 45:20.630
Und ich darf diese Regel, Sie sehen, ich habe jetzt nicht mehr

45:20.630 --> 45:22.850
Unterschieden, nicht Terminal und Terminalzeichen.

45:22.850 --> 45:30.730
Ich darf die jetzt, wenn ich ausgehe von einem Wort A, darf ich durch

45:30.730 --> 45:35.010
Anwendung dieser Regel erzeugen mein A, B, A, C.

45:35.510 --> 45:38.550
Und dann kann ich das auf jedes Zeichen gleichzeitig anwenden.

45:38.910 --> 45:43.470
Dann habe ich also hier A, B, A, C stehen, dann steht da ein B, dann

45:43.470 --> 45:48.010
steht da A, B, A, C und es steht wieder ein C daneben.

45:48.740 --> 45:53.030
Das entspricht dem, was ich hier unten gemacht habe, bildvisualisiert,

45:53.070 --> 45:55.010
habe ich hier oben einfach als Zeichen hingeschrieben.

45:56.070 --> 46:02.030
Und das heißt, durch kontextfreie Regeln und parallele Ableitungen,

46:02.050 --> 46:07.350
ich ersetze jedes Zeichen durch eine Regel gleichzeitig, durch diese

46:07.350 --> 46:10.750
parallelen Ableitungen bekommt man ganz andere Strukturen, ganz andere

46:10.750 --> 46:11.550
Sprachstrukturen.

46:12.790 --> 46:17.930
Und das sind völlig andere Sprachklassen, die aber auch alle natürlich

46:17.930 --> 46:20.810
in der Klasse der entscheidenden Sprachen drin sind und so weiter.

46:21.150 --> 46:23.970
Aber es ist eine andere Strukturierung der Sprachen, da werden

46:23.970 --> 46:25.430
biologische Strukturen dargestellt.

46:25.770 --> 46:29.190
Sie kennen Fraktale und ähnliches, das sind im Prinzip auch solche

46:29.190 --> 46:34.310
Arten, um komplexe Systeme zu beschreiben durch einfache endliche

46:34.310 --> 46:35.570
Systeme.

46:35.570 --> 46:40.730
Oder eine andere Art der Automatendefinition, ich kann stochastische

46:40.730 --> 46:45.870
Automaten definieren, bei denen ich zu jedem Übergang von einem

46:45.870 --> 46:49.110
Zustand zum nächsten Zustand sage, ich habe eine gewisse

46:49.110 --> 46:54.970
Wahrscheinlichkeit, mit der ich von dem Zustand S1 in den Zustand S2

46:54.970 --> 46:55.550
übergehe.

46:55.550 --> 47:02.290
Sie kennen das vielleicht auch aus dem Operations Research oder

47:02.290 --> 47:04.150
Statistik.

47:04.350 --> 47:07.050
In der Statistik schaut man sich Markov-Prozesse an.

47:08.030 --> 47:11.550
Das sind im Prinzip Markov-Prozesse, bei denen Sie zu jedem Zustand

47:11.550 --> 47:14.730
eines Systems Wahrscheinlichkeiten haben für den Übergang in einen

47:14.730 --> 47:15.530
nächsten Zustand.

47:15.950 --> 47:18.190
So können Sie stochastische Automaten definieren, Sie können dann

47:18.190 --> 47:21.010
Sprachen definieren, die mit einer gewissen Wahrscheinlichkeit

47:21.010 --> 47:24.850
akzeptiert werden und haben auch darüber eine völlig andere Struktur

47:24.850 --> 47:25.390
von Sprachen.

47:25.550 --> 47:29.190
Nur, dass Sie sehen, wenn man sich mit formalen Modellen von Sprachen

47:29.190 --> 47:33.550
beschäftigt, gibt es eine Vielfalt von Möglichkeiten, das zu tun.

47:34.050 --> 47:36.930
Und die liefern hier andere Hierarchien als das, was wir hier oben

47:36.930 --> 47:37.670
angegeben haben.

47:38.010 --> 47:41.150
Das ist die Chomsky-Hierarchie, dieses hier wären ganz andere

47:41.150 --> 47:44.610
Sprachhierarchien, die man durch solche Arten definieren kann.

47:45.150 --> 47:47.350
Das also nur kurz als Randbemerkung dazu.

47:47.510 --> 47:49.770
Und dann haben wir hier noch eine Folie, wo wir diese Tabelle, die wir

47:49.770 --> 47:52.310
schon mal gesehen haben, am Ende des vorigen Kapitels nochmal

47:52.310 --> 47:53.150
vervollständigen.

47:53.690 --> 47:59.550
Wir haben also innerhalb der allgemeinen Sprachen, der L0-Sprachen

47:59.550 --> 48:05.170
festgestellt, es gibt dort entscheidbare und semi-entscheidbare

48:05.170 --> 48:05.710
Sprachen.

48:06.190 --> 48:07.850
Das waren dann die aufzählbaren Sprachen.

48:09.410 --> 48:18.030
Wir können also hier zum Beispiel folgende Sprache angeben, wenn Sie

48:18.030 --> 48:25.650
als Sprache definieren, die Menge von Paaren, die besteht aus der

48:25.650 --> 48:30.770
Beschreibung einer Turing-Maschine und einem Wort, von dem ich weiß,

48:30.870 --> 48:32.910
die Turing-Maschine hält auf diesem Wort.

48:32.910 --> 48:43.610
Dann kann ich eine Turing-Maschine bauen, die für jede solche Eingabe

48:43.610 --> 48:48.270
T W, bei der ich weiß, die Turing-Maschine hält bei Eingabe dieses

48:48.270 --> 48:50.630
Wortes, kann die Turing-Maschine das überprüfen.

48:50.630 --> 48:53.870
Also die universelle Turing-Maschine kann selbstverständlich für jedes

48:53.870 --> 49:04.330
Wort T simulieren und feststellen, ob dieses Wort dann angesetzt auf W

49:04.330 --> 49:04.690
hält.

49:04.990 --> 49:07.930
Das ist in endlicher Zeit ausführbar, weil die Maschine ja hält, kann

49:07.930 --> 49:11.290
ich feststellen, ob die hält.

49:11.470 --> 49:16.330
Damit habe ich hier eine Sprache definiert, die aus allen haltenden

49:16.330 --> 49:19.590
Turing -Maschinen-Beschreibungen und Eingaben besteht.

49:20.130 --> 49:23.950
Das sind dann aufzählbare Sprachen und wir haben gesehen, es gibt auch

49:23.950 --> 49:26.490
Sprachen, die halt nicht durch Turing-Maschinen beschreibbar sind.

49:27.470 --> 49:32.210
Damit haben wir also unsere Tabelle hier vervollständigt.

49:32.990 --> 49:36.430
Wir hatten uns auch mit dem Erkennungsaufwand beschäftigt und das wird

49:36.430 --> 49:39.390
uns als nächstes jetzt intensiv beschäftigen, nämlich wie kann ich den

49:39.390 --> 49:44.370
Aufwand charakterisieren, den ich habe, für das Wortproblem oder auch

49:44.370 --> 49:48.730
für andere Aufgaben, nämlich Funktionen zu berechnen, wenn ich weiß,

49:48.830 --> 49:52.410
ich kann eine Funktion berechnen, wie viel Aufwand muss ich dann

49:52.410 --> 49:54.750
reinstecken, wie kann ich das möglichst effizient machen.

49:55.470 --> 49:59.290
Und das ist das, was jetzt anschließend kommt, uns mit dem Aufwand zu

49:59.290 --> 50:02.830
beschäftigen, den wir haben, wenn wir eine Turing-Maschine ausführen

50:02.830 --> 50:04.610
oder irgendeine Funktion berechnen.

50:04.950 --> 50:06.950
Das müssen wir irgendwie charakterisieren können, wir haben das immer

50:06.950 --> 50:09.030
so intuitiv gemacht, Sie kennen das ja auch aus der Grundlage der

50:09.030 --> 50:12.690
Informatik 1, dass man den Aufwand charakterisiert, so und so viel

50:12.690 --> 50:16.110
Operation muss ich ausführen.

50:16.110 --> 50:19.670
Die Frage ist also, was kostet eigentlich die Berechnung einer

50:19.670 --> 50:20.190
Funktion?

50:20.690 --> 50:23.990
Abgesehen davon, dass ich einen Aufwand habe, um die erst mal

50:23.990 --> 50:26.510
überhaupt richtig zu beschreiben und das Programm zu entwerfen.

50:27.050 --> 50:28.990
Was kostet die Lösung eines Problems?

50:30.130 --> 50:33.110
Also eine Funktion kann ich ja verwenden, um ein Problem zu lösen.

50:35.450 --> 50:38.790
Ich formuliere Probleme häufig anders als eine Funktion.

50:38.790 --> 50:42.470
Und die Antwort darauf ist natürlich abhängig davon, was für ein

50:42.470 --> 50:46.250
Berechnungsmodell ich habe, was sind eigentlich meine einzelnen

50:46.250 --> 50:52.130
Operationen, die ich ausführe und welchen Algorithmus wende ich an.

50:52.930 --> 50:55.610
Sie erinnern sich bei den Sortierverfahren, da gab es welche, die

50:55.610 --> 50:58.930
liefen in Zeit Nlog N und andere liefen in Zeit N².

50:59.850 --> 51:02.130
Also je nach Verfahren können Sie unterschiedlichen Aufwand haben.

51:03.090 --> 51:08.010
Und ich muss natürlich auch anschauen, wenn ich die Zeit betrachte,

51:08.930 --> 51:14.250
mache ich das Ganze sequenziell oder kann ich auch Operationen

51:14.250 --> 51:15.190
parallel ausführen?

51:16.250 --> 51:19.110
Die Anzahl der Schritte wird dann natürlich unterschiedlich sein.

51:19.850 --> 51:23.050
Die Anzahl der Operationen ist vielleicht gleich, aber die Anzahl der

51:23.050 --> 51:25.090
Schritte, die Zeit, die ich brauche, kann unterschiedlich sein.

51:25.170 --> 51:27.830
Also das Berechnungsmodell ist sehr wichtig, da gehe ich nur relativ

51:27.830 --> 51:28.710
kurz hier drauf ein.

51:28.710 --> 51:32.390
Es gibt eine Reihe Standardansätze, das eine sind die Turing

51:32.390 --> 51:35.050
-Maschinen, da kommen wir aus der allgemeinen Aussage über

51:35.050 --> 51:37.710
Berechenbarkeit und grundsätzliche Komplexitätsklassen.

51:38.910 --> 51:42.570
Ich kann aber auch ein bisschen näher rangehen an die realen Rechner,

51:43.270 --> 51:45.370
nämlich eine sogenannte Register-Maschine.

51:45.790 --> 51:49.210
Wir werden später sehen, es gibt noch ein ganz reales Modell, die von

51:49.210 --> 51:49.810
Neumann -Maschine.

51:50.950 --> 51:54.270
Und dann kann ich das Ganze auch parallel betrachten, ich kann

51:54.270 --> 51:56.570
parallele Random Access Machines betrachten.

51:57.450 --> 52:02.450
Ganz kurz, da habe ich also eine Steuerungseinheit Control, ich habe

52:02.450 --> 52:07.310
ein Rechenwerk, ich habe ein Processing Unit und ich habe einen

52:07.310 --> 52:11.690
Speicher und die arbeiten geeignet zusammen.

52:12.330 --> 52:16.670
Und wenn ich davon jetzt mehrere hinmale, dann habe ich im Prinzip

52:16.670 --> 52:22.250
mehrere solche Maschinen, die miteinander kommunizieren können,

52:22.310 --> 52:25.170
dadurch, dass die vielleicht hier über den Speicher verbunden sind.

52:25.170 --> 52:28.010
Dann haben sie das, was sie in ihren Rechnern heutzutage drin haben,

52:28.350 --> 52:30.570
Rechner mit mehreren Kernen, mit mehreren Prozessoren.

52:31.230 --> 52:33.550
Und das kann man eben als allgemeines Modell des Parallel Random

52:33.550 --> 52:34.590
Access Machines beschreiben.

52:35.170 --> 52:37.830
Das sind Themen, die wir in der anderen Vorlesung, Effiziente

52:37.830 --> 52:39.310
Algorithmen, intensiver betrachten.

52:39.610 --> 52:41.550
Da kann ich hier nicht im Einzelnen drauf eingehen.

52:41.930 --> 52:46.030
Wir werden uns jetzt im Prinzip noch darauf beschränken, Turing

52:46.030 --> 52:51.450
-Maschinen, und gucken uns an, wie wir auf der Basis jetzt die

52:51.450 --> 52:54.010
Komplexität von Problemen betrachten können.

52:56.290 --> 52:58.670
Allerdings werden wir jetzt Turing-Maschinen gar nicht weiter

52:58.670 --> 53:00.990
anschauen, sondern wir gehen davon aus, wir haben ein geeignetes

53:00.990 --> 53:01.790
Berechnungsmodell.

53:02.610 --> 53:06.350
Wenn wir jetzt Probleme charakterisieren wollen, wie ihr gut bekanntes

53:06.350 --> 53:08.050
Beispiel des Sortierproblems.

53:09.030 --> 53:11.390
Da kann ich das Problem auf unterschiedliche Art und Weise

53:11.390 --> 53:14.310
charakterisieren, den Aufwand, den ich habe, um das zu berechnen.

53:15.030 --> 53:17.150
Ich kann obere Schranken angeben.

53:18.210 --> 53:21.730
Obere Schranken bekomme ich dadurch, dass ich einen Algorithmus

53:21.730 --> 53:22.390
analysiere.

53:22.390 --> 53:29.690
Also zum Beispiel, wenn ich das Verfahren Bubble Sort nehme.

53:30.670 --> 53:33.430
Das ist ein allgemeines Verfahren, mit dem ich jede Folge, die

53:33.430 --> 53:35.330
sortiert werden muss, sortieren kann.

53:35.750 --> 53:39.050
Und ich weiß, da habe ich einen Aufwand von N².

53:41.930 --> 53:47.870
Also quadratisch in der Länge der Folgen kann ich damit jede beliebige

53:47.870 --> 53:48.630
Folge sortieren.

53:48.630 --> 53:50.230
Damit habe ich eine obere Schranke.

53:50.330 --> 53:54.170
Ich brauche nie mehr als quadratisch viele Operationen, um eine Folge

53:54.170 --> 53:55.770
zu sortieren.

53:56.370 --> 54:00.190
Ich kann aber auch versuchen, untere Schranken zu finden.

54:00.710 --> 54:03.410
Dann kann ich nämlich eine Auswahl darüber machen, wie gut dieses O

54:03.410 --> 54:04.810
von N² eigentlich ist.

54:05.850 --> 54:09.450
Da muss ich sagen, wenn ich jetzt eine beliebige Folge habe, wie viel

54:09.450 --> 54:13.250
Aufwand muss ich dann mindestens betreiben, um diese Folge zu

54:13.250 --> 54:13.710
sortieren.

54:14.330 --> 54:18.430
Wir wissen, da gibt es eine untere Schranke, die liegt bei N log N.

54:21.650 --> 54:25.950
Und wenn Sie dann ein Verfahren haben, das in der Zeit N log N läuft,

54:26.030 --> 54:28.090
wissen Sie, das ist optimal, das geht nicht besser.

54:28.810 --> 54:31.850
Ganz wichtig, wenn Sie Ihrem Arbeitgeber sagen müssen, wie gut ein

54:31.850 --> 54:33.570
Verfahren ist, das Sie hingeschrieben haben.

54:34.030 --> 54:37.630
Wenn Sie zeigen können, das trifft genau die untere Schranke, dann

54:37.630 --> 54:38.490
geht es nicht besser.

54:39.510 --> 54:43.570
Wobei natürlich hier Groß-O und Groß-Omega stehen, da haben Sie noch

54:43.570 --> 54:44.490
Konstanten davor.

54:44.570 --> 54:46.970
Wenn Sie die Konstanten noch verbessern können, können Sie auch noch

54:46.970 --> 54:50.150
ein bisschen mehr Geld kriegen, weil Sie größere Leistungen gebracht

54:50.150 --> 54:50.430
haben.

54:51.470 --> 54:53.850
Also, das müssen wir jetzt ein bisschen genauer nochmal machen.

54:55.070 --> 54:56.590
Jetzt kommt doch nochmal ein bisschen Turing-Maschinen.

54:57.830 --> 55:00.690
Das ist aber nur unser abstraktes Modell.

55:00.690 --> 55:09.190
Wir haben also zwei Mengen, M1 und M2, als Teilmengen der Menge aller

55:09.190 --> 55:10.530
Wörter über dem Alphabet E.

55:11.230 --> 55:16.330
Und wir wollen eine beliebige Funktion von M1 nach M2, die von einer

55:16.330 --> 55:18.410
Turing -Maschine berechnet wird.

55:18.650 --> 55:21.690
Und jetzt sagen wir, wie wir die Komplexität dieser Funktion

55:21.690 --> 55:22.450
charakterisieren.

55:22.930 --> 55:24.650
Das müssen wir jetzt formal einmal machen.

55:24.650 --> 55:28.550
Und zwar reden wir in diesem Fall einerseits von der Zeitkomplexität.

55:29.790 --> 55:33.670
Zeit ist Geld und deswegen schaut man sich das an.

55:34.330 --> 55:39.270
Ich schaue mir also an die Zeit, also T für Time, einer Turing

55:39.270 --> 55:42.610
-Maschine, TM, bei Eingabe von W.

55:42.910 --> 55:46.390
Das wäre die Länge der kürzesten Konfigurationenfolge von der

55:46.390 --> 55:48.450
Anfangskonfiguration zur Endkonfiguration.

55:48.710 --> 55:52.210
Klar, wie man das macht, also dass man eine solche Länge betrachtet.

55:52.210 --> 55:55.350
Sie wissen, das kann ich also auch für nichtdeterministische Turing

55:55.350 --> 55:56.230
-Maschinen angeben.

55:57.850 --> 56:01.330
Da habe ich ja irgendwann eine Konfigurationenfolge.

56:01.410 --> 56:04.550
Ich mache das über die Konfigurationenfolge einer Berechnung.

56:05.130 --> 56:06.530
Das Wort W wird eingegeben.

56:06.850 --> 56:08.210
Die Länge der kürzesten Konfigurationenfolge.

56:08.850 --> 56:12.030
Bei nichtdeterministischen haben wir eventuell viele verschiedene

56:12.030 --> 56:15.310
Möglichkeiten, Konfigurationenfolgen zu machen.

56:15.830 --> 56:20.150
Und die kürzeste Konfigurationenfolge, das ist die Zeitkomplexität

56:20.150 --> 56:21.250
dieser Berechnung.

56:22.200 --> 56:30.910
Und dann kann ich noch betrachten das Maximum aller solcher Zeiten für

56:30.910 --> 56:32.830
Wörter, die die gleiche Länge haben.

56:34.090 --> 56:41.670
Also T, TM von N ist das Maximum aller Ausführungszeiten dieser Turing

56:41.670 --> 56:45.370
-Maschine TM auf Wörtern der gleichen Länge.

56:46.590 --> 56:49.090
Das gleiche kann ich machen für den Platz.

56:50.830 --> 56:52.910
Was muss ich mir den Platz anschauen?

56:53.010 --> 56:58.570
Bei meiner Turing-Maschine, da habe ich mein Band, auf dem ich

56:58.570 --> 56:59.250
irgendwie arbeite.

56:59.710 --> 57:02.490
Ich habe hier irgendwas als Eingabe gehabt.

57:03.530 --> 57:07.210
Und am Ende habe ich vielleicht links und rechts noch irgendwas mehr

57:07.210 --> 57:08.190
gebraucht an Platz.

57:09.190 --> 57:11.870
Und ich habe vielleicht irgendeinen Bereich hier drin auch irgendwie

57:11.870 --> 57:12.330
verändert.

57:13.290 --> 57:15.610
Natürlich muss ich alles, oder es kann sein, dass ich alles lesen

57:15.610 --> 57:16.670
muss, was dort drauf steht.

57:16.670 --> 57:23.350
Aber wenn ich von der Platzkomplexität der Berechnung einer Funktion F

57:23.350 --> 57:27.850
mit einer Turing-Maschine für eine Eingabe W rede, dann rede ich von

57:27.850 --> 57:33.050
der Anzahl der durch Schreiben veränderten Zellen des Bandes in der

57:33.050 --> 57:36.630
kürzesten Konfigurationenfolge von der Initial- zur Endkonfiguration.

57:37.310 --> 57:40.470
Ich könnte auch sagen, ich mache das Modell, um das nochmal zu

57:40.470 --> 57:43.630
motivieren, ein bisschen anders.

57:44.590 --> 57:49.290
Dass ich hier mein Eingabeband habe und daneben, wie gesagt, ich kann

57:49.290 --> 57:53.010
auch mein Arbeitsband definieren, schaue ich nach, wie viel Platz

57:53.010 --> 57:58.270
brauche ich auf meinem Arbeitsband, um für eine gewisse Eingabe W am

57:58.270 --> 58:02.550
Ende tatsächlich das Ergebnis auf dem Arbeitsband zu produzieren.

58:07.010 --> 58:10.750
Und das heißt, ich kann eben auch Funktionen haben, die nur eine sehr

58:10.750 --> 58:13.330
kurze Zeit brauchen, vielleicht nur eine logarithmische Zeit brauchen,

58:13.590 --> 58:15.690
um eine Funktion zu berechnen oder ähnliches.

58:17.270 --> 58:21.430
Also habe ich einerseits den Platz, den Speicherplatz, den ich brauche

58:21.430 --> 58:24.170
für meine Funktion und ich habe die Zeit.

58:24.510 --> 58:25.790
Und das beides betrachte ich jetzt.

58:25.790 --> 58:32.350
Dann kann ich genauso gut sagen, ich mache hier den maximalen Platz,

58:32.370 --> 58:38.230
den ich brauche, um für Wörter der gleichen Länge ein Ergebnis zu

58:38.230 --> 58:38.850
produzieren.

58:39.530 --> 58:44.190
Und das, was wir hier beschreiben, das sind also jetzt Maße für den

58:44.190 --> 58:46.850
Berechnungsaufwand im schlechtesten Fall.

58:47.070 --> 58:51.190
Für alle Wörter gleicher Länge die maximale Zeit.

58:51.190 --> 58:54.150
Es kann sein, dass ich im Schnitt deutlich besser bin.

58:54.670 --> 59:01.370
Sie kennen, Sie erinnern sich an das Verfahren Quicksort, bei dem Sie

59:01.370 --> 59:09.950
im schlechtesten Fall bei O von n² sind, im Mittel aber bei O von n

59:09.950 --> 59:15.330
log n, mittlere Zeit, und im besten Fall auch bei n log n.

59:16.470 --> 59:18.390
Es sei denn, Sie haben noch eine optimierte Version, dann können Sie

59:18.390 --> 59:19.990
da sogar in linearer Zeit fertig werden.

59:19.990 --> 59:23.490
Also ich kann mir auch das mittlere Verhalten anschauen, da brauche

59:23.490 --> 59:26.410
ich aber eine Aussage über die Verteilung meiner Probleminstanzen.

59:27.630 --> 59:31.470
Und das andere ist das Verhalten im besten Fall, nur da müssen Sie

59:31.470 --> 59:34.370
Glück haben, dass Sie gerade für eine Anwendung den besten Fall haben.

59:34.910 --> 59:38.130
Auf jeden Fall, wenn Sie den schlechtesten Fall betrachten, dann haben

59:38.130 --> 59:42.630
Sie eine auf jeden Fall sichere Aussage bei dieser Abschätzung über

59:42.630 --> 59:45.090
den Zeitaufwand oder Platzaufwand.

59:45.090 --> 59:49.390
Das kennen Sie auch bereits aus Grundlageninformatik I und kann man

59:49.390 --> 59:52.430
ebenso allgemein hier für Komplexitätsmaße definieren.

59:53.390 --> 59:59.150
Und jetzt können wir Komplexitätsklassen definieren, aufbauend auf

59:59.150 --> 01:00:00.530
dieser Definition.

01:00:01.910 --> 01:00:06.770
Wir haben also jetzt unterschiedliche Arten von Turing-Maschinen und

01:00:06.770 --> 01:00:09.290
wir haben deterministische und nicht deterministische Turing

01:00:09.290 --> 01:00:09.670
-Maschinen.

01:00:09.670 --> 01:00:15.750
Und wir können jetzt für eine beliebige Funktion, das kann sein, dass

01:00:15.750 --> 01:00:24.570
das eine Funktion ist, die eine Zahl n abbildet auf n², das wäre also

01:00:24.570 --> 01:00:29.170
die Funktion, das G einfach nur die Quadratfunktion, dann würde ich

01:00:29.170 --> 01:00:35.530
schauen, bei dTime von n², wäre das gerade die Menge aller Funktionen,

01:00:35.650 --> 01:00:39.730
die in der entsprechenden Zeit von einer deterministischen Turing

01:00:39.730 --> 01:00:40.850
-Maschine berechenbar sind.

01:00:41.430 --> 01:00:44.950
Ich habe die ganze Zeit hier diese O-Notation verwendet.

01:00:44.950 --> 01:00:52.030
Nur nochmal ganz kurz, wenn ich hier so ein O von G hinschreibe, was

01:00:52.030 --> 01:00:54.230
ist denn das O von G?

01:00:54.690 --> 01:00:56.090
Das ist jetzt irgendeine Funktion.

01:00:57.270 --> 01:01:01.710
Das ist die Menge aller, ich schreibe jetzt mal hin, die Menge aller

01:01:01.710 --> 01:01:09.990
Funktionen h, für die folgendes gilt.

01:01:10.990 --> 01:01:29.510
Es gibt ein n0, es gibt ein c, sodass für alle n größer gleich n0, h

01:01:29.510 --> 01:01:36.270
von n kleiner gleich c mal G von n ist.

01:01:37.590 --> 01:01:43.130
Das heißt, das G von n, diese Funktion G, ist eine obere Schranke für

01:01:43.130 --> 01:01:44.850
die Funktion h, die da drin sind.

01:01:46.710 --> 01:01:48.030
Das ist die O-Notation.

01:01:48.230 --> 01:01:52.910
Bis auf einen konstanten Faktor habe ich asymptotisch das G als eine

01:01:52.910 --> 01:01:54.650
obere Grenze.

01:01:54.810 --> 01:02:02.650
Zum Beispiel ist die lineare Funktion ist in O von n² drin, die wächst

01:02:02.650 --> 01:02:03.690
nicht schneller als n².

01:02:04.310 --> 01:02:06.570
Auch n hoch 1,5 ist da drin.

01:02:06.690 --> 01:02:11.550
Und n hoch 1,8 sind alle da drin, in O von n².

01:02:12.230 --> 01:02:13.630
Auch n² selber ist da drin.

01:02:14.210 --> 01:02:18.490
Das kennen Sie aber im Prinzip alles aus Grundlagen der Informatik 1

01:02:18.490 --> 01:02:18.890
bzw.

01:02:19.310 --> 01:02:23.490
aus anderen Vorlesungen, bei denen man Aufwandsabschätzungen macht.

01:02:23.490 --> 01:02:25.630
Oder Wachstumsabschätzungen macht.

01:02:28.250 --> 01:02:32.350
Das sind also nochmal zurück die Details von G, die Menge aller

01:02:32.350 --> 01:02:40.450
Funktionen, die in der Zeit O von G von einer deterministischen Turing

01:02:40.450 --> 01:02:41.550
-Maschine berechenbar sind.

01:02:42.290 --> 01:02:46.570
Genauso in time von G, da schaue ich mir eine nicht-deterministische

01:02:46.570 --> 01:02:47.490
Turing -Maschine an.

01:02:48.370 --> 01:02:51.350
Und Sie erinnern sich daran, wir können alles das, was eine nicht

01:02:51.350 --> 01:02:54.530
-deterministische Turing-Maschine tun kann, simulieren durch eine

01:02:54.530 --> 01:02:55.870
deterministische Turing-Maschine.

01:02:56.350 --> 01:02:58.390
Aber da habe ich schon darauf hingewiesen, das kann sein, dass der

01:02:58.390 --> 01:03:00.750
Aufwand dafür deutlich größer wird.

01:03:01.530 --> 01:03:03.050
Eventuell ein exponentieller Unterschied.

01:03:05.830 --> 01:03:10.210
Dann haben wir D-Space, das gleiche für den Platzaufwand.

01:03:10.830 --> 01:03:14.530
Wenn ich also eine deterministische Turing-Maschine habe, die mit

01:03:14.530 --> 01:03:20.930
Platzkomplexität O von G berechenbar ist, dann ist die Funktion in

01:03:20.930 --> 01:03:24.030
dieser Menge D-Space von G mit drin.

01:03:24.170 --> 01:03:26.710
Das gleiche für N-Space, nicht-deterministische Turing-Maschine.

01:03:27.650 --> 01:03:30.790
Ganz allgemeine abstrakte Definition, wir machen das gleich konkreter.

01:03:31.590 --> 01:03:36.690
Das G von N kann eben irgendein Polynom sein, N hoch K oder N hoch

01:03:36.690 --> 01:03:37.210
irgendwas.

01:03:37.210 --> 01:03:41.090
Aber es reicht immer, die höchste Potenz anzugeben.

01:03:42.450 --> 01:03:44.790
Es kann sein, dass es N log N ist, das hatte ich oben auch schon

01:03:44.790 --> 01:03:45.670
erwähnt.

01:03:45.970 --> 01:03:51.850
Es kann sein, dass ich Log hoch K von N habe, also Quadratlog N hoch 3

01:03:51.850 --> 01:03:52.370
oder was immer.

01:03:52.890 --> 01:03:58.430
Ich kann Potenzen angeben, also das sind so typische Funktionen, die

01:03:58.430 --> 01:03:59.090
man betrachtet.

01:03:59.470 --> 01:04:03.730
Und dann habe ich entsprechend Klassen von Funktionen und ich kann das

01:04:03.730 --> 01:04:05.530
auch wieder allgemein definieren.

01:04:05.530 --> 01:04:09.450
Ich kann sagen, ich betrachte die Klasse der in polynomieller Zeit

01:04:09.450 --> 01:04:10.530
berechenbaren Funktionen.

01:04:11.430 --> 01:04:14.170
Und zwar von deterministischen Turing-Maschinen.

01:04:15.370 --> 01:04:19.170
In polynomieller Zeit von deterministischen Turing-Maschinen

01:04:19.170 --> 01:04:20.390
berechenbaren Funktionen.

01:04:20.510 --> 01:04:24.610
D-Time von N hoch K ist die Menge aller Funktionen, die in Zeit O von

01:04:24.610 --> 01:04:27.370
N hoch K durch Turing-Maschinen berechenbar sind.

01:04:27.510 --> 01:04:28.690
Deterministische Turing-Maschinen.

01:04:28.690 --> 01:04:34.050
Die Vereinigung aller solcher Mengen sind also alle Funktionen, die in

01:04:34.050 --> 01:04:38.950
polynomieller Zeit für ein beliebiges K in Zeit N hoch K durch eine

01:04:38.950 --> 01:04:41.070
deterministische Turing-Maschine berechnet werden können.

01:04:41.630 --> 01:04:44.630
Und jetzt kann ich das gleiche machen für N-Time.

01:04:45.770 --> 01:04:49.330
Nicht-deterministische Turing-Maschine, der erlaube ich polynomieller

01:04:49.330 --> 01:04:49.810
Zeit.

01:04:50.710 --> 01:04:53.950
Und dann habe ich die Klasse der Probleme, die von nicht

01:04:53.950 --> 01:04:57.610
-deterministischen Turing-Maschinen in polynomieller Zeit berechenbar

01:04:57.610 --> 01:04:57.910
sind.

01:04:57.910 --> 01:04:59.570
Sieht ganz ähnlich aus.

01:05:01.290 --> 01:05:03.470
Jetzt kann man sich überlegen, wie ist eigentlich das Verhältnis

01:05:03.470 --> 01:05:04.850
dieser beiden Klassen zueinander.

01:05:05.950 --> 01:05:09.530
Also dies N-P heißt nicht-deterministische Turing-Maschine

01:05:09.530 --> 01:05:10.450
polynomieller Zeit.

01:05:11.310 --> 01:05:17.870
Typisches Beispiel dafür ist meinetwegen die Frage, gibt es, ich habe

01:05:17.870 --> 01:05:23.230
eine Anzahl von Städten und ich möchte jetzt fragen, kann ich für

01:05:23.230 --> 01:05:28.390
irgendeinen Handelsvertreter eine Tour angeben, die eine Länge hat,

01:05:29.350 --> 01:05:32.470
Tourlänge kleiner gleich irgendein K.

01:05:35.530 --> 01:05:39.010
Dann mache ich das folgendermaßen, ich rate einfach irgendeine Tour

01:05:39.010 --> 01:05:44.610
und überprüfe, ob diese Tour kürzer gleich K ist.

01:05:45.530 --> 01:05:51.510
Das wäre ein nicht-deterministischer Weg zur Lösung meines Problems.

01:05:52.610 --> 01:05:55.650
Und das ist genau das, was man mit nicht-deterministischen Turing

01:05:55.650 --> 01:05:56.450
-Maschinen ja machen kann.

01:05:56.530 --> 01:05:59.710
Ich kann einfach die so verzweigen, dass ich jeden möglichen Weg durch

01:05:59.710 --> 01:06:02.110
jede mögliche Permutation der Städte einfach rate.

01:06:03.090 --> 01:06:05.530
Und überprüfen kann in polynomieller Zeit, das ist ja ganz einfach zu

01:06:05.530 --> 01:06:11.030
überprüfen, ob ein gewisser Weg durch meine Menge von Städten, ob

01:06:11.030 --> 01:06:14.250
dieser Weg länger oder kürzer als K ist.

01:06:14.850 --> 01:06:19.310
Und wenn es einen Weg kürzer als K gibt, dann hätte ich ja diesen Weg

01:06:19.310 --> 01:06:20.050
raten können.

01:06:20.450 --> 01:06:23.230
Und dann in polynomieller Zeit überprüfen, ob der Weg tatsächlich

01:06:23.230 --> 01:06:24.550
kürzer ist als K oder nicht.

01:06:25.290 --> 01:06:29.350
Und damit habe ich also genau auf andere Art und Weise das NP

01:06:29.350 --> 01:06:32.750
charakterisiert, ohne jetzt auf Turing-Maschinen mich zurückziehen zu

01:06:32.750 --> 01:06:32.990
müssen.

01:06:32.990 --> 01:06:38.850
Ich sage einfach, die Klasse NP, das sind alle Probleme, bei denen ich

01:06:38.850 --> 01:06:42.350
irgendeine potenzielle Lösung raten kann.

01:06:43.570 --> 01:06:45.790
Das kostet mich gar nichts, die zu raten.

01:06:46.570 --> 01:06:51.530
Oder gerade Aufwand in der Größe der möglichen Lösung, die ich dort

01:06:51.530 --> 01:06:52.190
angeben muss.

01:06:53.070 --> 01:06:57.930
Und dann überprüfe ich, ob diese geratene Lösung tatsächlich zulässig

01:06:57.930 --> 01:07:01.070
ist, die die Antwort gibt auf meine Frage.

01:07:01.070 --> 01:07:04.890
Und wenn das so ist, dann habe ich also das entsprechend beantwortet.

01:07:05.350 --> 01:07:07.850
In polynomieller Zeit, aber eben nicht deterministisch.

01:07:07.930 --> 01:07:10.050
Raten und überprüfen in polynomieller Zeit.

01:07:11.770 --> 01:07:16.310
Das Problem ist natürlich, dass die deterministische Simulation

01:07:16.310 --> 01:07:27.130
exponentielle Worst-Case-Execution-Time hat.

01:07:27.130 --> 01:07:30.830
Wenn Sie also irgendwo WZ finden, als Abkürzung, das ist Worst-Case

01:07:30.830 --> 01:07:31.590
-Execution -Time.

01:07:31.930 --> 01:07:32.770
Im schlechtesten Fall.

01:07:33.750 --> 01:07:35.950
Das hatten wir schon mal gesehen, bei der Simulation der nicht

01:07:35.950 --> 01:07:36.890
deterministischen Turing-Maschinen.

01:07:37.370 --> 01:07:45.250
Das heißt, wenn ich auf die Standardart und Weise, Sie sagen mir, ich

01:07:45.250 --> 01:07:49.150
kann tatsächlich jetzt in polynomieller Zeit mit einer nicht

01:07:49.150 --> 01:07:53.350
deterministischen Turing-Maschine durch Raten und Überprüfen ein

01:07:53.350 --> 01:07:54.130
Problem lösen.

01:07:54.130 --> 01:07:56.150
Und ich will das deterministisch machen.

01:07:56.610 --> 01:07:59.710
Mit dem Standardverfahren, das deterministisch zu machen, kann es

01:07:59.710 --> 01:08:02.210
sein, dass Sie dann auf einmal exponentielle Zeit brauchen.

01:08:03.730 --> 01:08:05.850
Und es könnte ja sein, dass es besser geht.

01:08:07.030 --> 01:08:09.390
Also das P enthalten in NP ist klar.

01:08:10.090 --> 01:08:12.730
Jede deterministische Turing-Maschine ist ja auch eine spezielle nicht

01:08:12.730 --> 01:08:13.430
deterministische.

01:08:15.070 --> 01:08:19.850
Und die Frage ist, sind diese beiden Klassen gleich oder sind die

01:08:19.850 --> 01:08:20.390
ungleich?

01:08:20.390 --> 01:08:25.810
Das, was ich hier oben in rot angedeutet habe, zeigt, wenn ich das

01:08:25.810 --> 01:08:29.590
naiv mache, bekomme ich hier einen riesigen Unterschied.

01:08:29.670 --> 01:08:32.270
Von polynomiell zu exponentieller Zeit, im schlechtesten Fall.

01:08:33.190 --> 01:08:36.790
Wenn ich es geschickt mache, könnte es ja sein, dass ich das in

01:08:36.790 --> 01:08:39.170
polynomieller Zeit hinkriege, auch deterministisch.

01:08:40.230 --> 01:08:42.190
Ich muss ja nicht diesen naiven Ansatz nehmen.

01:08:43.110 --> 01:08:44.890
Und diese Frage ist bis heute offen.

01:08:45.930 --> 01:08:47.430
Das ist ein offenes Problem.

01:08:48.450 --> 01:08:54.310
Man weiß nicht, ob man geschickte Verfahren finden kann, die für jede

01:08:54.310 --> 01:08:58.170
nicht deterministische Turing-Maschine, die in polynomieller Zeit ein

01:08:58.170 --> 01:09:03.030
Problem lösen kann, eine deterministische Variante finden kann, die

01:09:03.030 --> 01:09:04.730
auch nur polynomielle Zeit braucht.

01:09:05.530 --> 01:09:08.470
Es gibt zig Versuche, das zu beweisen, dass das so ist oder dass es

01:09:08.470 --> 01:09:09.130
nicht so ist.

01:09:10.050 --> 01:09:14.030
Kein einziger dieser Beweise ist bis heute erfolgreich.

01:09:14.810 --> 01:09:17.590
Man weiß es nicht, ob das ungleich ist oder nicht.

01:09:17.650 --> 01:09:21.590
Es gibt andere Komplexitätsklassen, bei denen auch offen war, ob die

01:09:21.590 --> 01:09:24.470
echt enthalten sind oder gleich sind.

01:09:25.170 --> 01:09:26.030
Da hat man das gezeigt.

01:09:26.130 --> 01:09:31.030
Und ganze Hierarchien von Zeitkomplexitätsklassen, die rutschten auf

01:09:31.030 --> 01:09:34.610
einmal zusammen in eine einzige Klasse, wo man vorher annahm, dass das

01:09:34.610 --> 01:09:35.870
eine wirkliche Hierarchie ist.

01:09:35.870 --> 01:09:38.550
Und dann gab es tatsächlich Beweise, dass die gleich sind.

01:09:38.970 --> 01:09:40.350
Hier weiß man es bis heute nicht.

01:09:41.070 --> 01:09:43.510
Und das ist durchaus ein sehr praktisches Problem.

01:09:44.290 --> 01:09:47.970
Und das nämlich heißt, das, was ich hier oben gerade beschrieben habe,

01:09:48.050 --> 01:09:50.570
das Travelling-Salesperson-Problem, Problem des Handelsreisenden, ist

01:09:50.570 --> 01:09:51.690
ein sehr praktisches Problem.

01:09:52.150 --> 01:09:55.450
Und es gibt leider sehr viele sehr praktische Probleme, die alle in

01:09:55.450 --> 01:09:56.590
dieser Klasse NP liegen.

01:09:56.590 --> 01:10:02.050
Und wir wissen von diesen Problemen nicht, also zumindest von gewissen

01:10:02.050 --> 01:10:04.590
schwierigen Problemen in dieser Klasse nicht, ob wir sie problemlos

01:10:04.590 --> 01:10:05.290
lösen können.

01:10:06.890 --> 01:10:08.650
Okay, das also kurz dazu.

01:10:09.150 --> 01:10:10.110
Steht hier nochmal drin.

01:10:10.610 --> 01:10:12.550
Und das wird uns jetzt ein bisschen beschäftigen, solche

01:10:12.550 --> 01:10:14.650
Problemklassen anzuschauen.

01:10:17.330 --> 01:10:21.510
Um damit umgehen zu können, brauchen wir einen Begriff, den wir

01:10:21.510 --> 01:10:22.510
Reduzierbarkeit nennen.

01:10:22.510 --> 01:10:33.010
Also, wir haben ein Problem P und Q und wir haben Lösungsmengen LQ und

01:10:33.010 --> 01:10:33.430
LP.

01:10:34.750 --> 01:10:37.650
Lösungsmengen für diese Probleme P und Q, also meinetwegen für

01:10:37.650 --> 01:10:42.290
Sortieren und Medienbestimmen oder sowas.

01:10:43.450 --> 01:10:46.530
Sie haben verschiedene Probleme und Lösungsmengen.

01:10:46.530 --> 01:10:53.130
Und jetzt interessiert es Sie, ob Sie eventuell ein Problem Q dadurch

01:10:53.130 --> 01:10:58.870
lösen können, dass Sie es transformieren in ein Problem P. Ein

01:10:58.870 --> 01:11:02.210
Beispiel, das ich Ihnen gleich geben werde ist, Sie möchten Matrizen

01:11:02.210 --> 01:11:06.350
multiplizieren können und Sie wissen, wie Sie Matrizen invertieren.

01:11:07.690 --> 01:11:11.770
Dann können Sie einfach das Multiplikationsproblem anders formulieren,

01:11:12.430 --> 01:11:14.730
in ein Inversionsproblem transformieren.

01:11:14.730 --> 01:11:15.950
Das kommt auf der nächsten Folie.

01:11:17.170 --> 01:11:19.010
Dann wissen Sie, wie Sie invertieren können.

01:11:19.090 --> 01:11:21.390
Sie bekommen die Lösung für das Inversionsproblem, bekommen die

01:11:21.390 --> 01:11:22.170
invertierte Matrix.

01:11:22.870 --> 01:11:26.110
Und in der invertierten Matrix finden Sie das Produkt der beiden

01:11:26.110 --> 01:11:29.390
Matrizen, das Sie vorher interessiert hat.

01:11:31.130 --> 01:11:35.150
Und das heißt, ich möchte gerne wissen, kann ich eine solche

01:11:35.150 --> 01:11:40.610
Transformation finden und eine Rücktransformation der Lösung des

01:11:40.610 --> 01:11:48.370
Zielproblems, sodass ich also das Problem Q hier dadurch auch indirekt

01:11:48.370 --> 01:11:49.530
lösen kann.

01:11:50.310 --> 01:12:02.290
Also ein Problem Q ist polynomialzeitreduzierbar auf das Problem P, so

01:12:02.290 --> 01:12:03.550
wie es hier angedeutet ist.

01:12:04.670 --> 01:12:09.410
Und so geschrieben, kleiner gleich, mit polynomiellem Aufwand,

01:12:09.970 --> 01:12:14.150
transformierbar auf das P. Genau dann, wenn das Q durch eine in

01:12:14.150 --> 01:12:18.270
polynomialer Zeit berechenbare Funktion in P transformiert werden kann

01:12:18.270 --> 01:12:23.450
und jede Lösung von F und Q, also hier unten, jede Lösung in

01:12:23.450 --> 01:12:26.110
polynomialer Zeit wieder zurücktransformiert werden kann in eine

01:12:26.110 --> 01:12:27.090
Lösung von Q.

01:12:28.050 --> 01:12:30.290
Eine Lösung von P zurücktransformiert in eine Lösung von Q.

01:12:34.670 --> 01:12:40.090
Und eines ist natürlich klar, dieses hier geht irgendwie in O von N

01:12:40.090 --> 01:12:48.290
hoch irgendein K1, das hier geht irgendwie in O von N hoch K2.

01:12:49.770 --> 01:12:53.830
Und wenn, jetzt muss ich mal anschauen, welche Zeit brauche ich hier.

01:12:54.690 --> 01:13:01.770
Wenn das hier auch ist aus O von N hoch K3, auch polynomiell, dann

01:13:01.770 --> 01:13:05.070
kann ich natürlich dieses Problem Q auch in polynomialer Zeit lösen,

01:13:05.170 --> 01:13:07.090
weil ich nur den Weg hier einmal rumlaufen muss.

01:13:07.610 --> 01:13:09.530
Dreimal polynomiell ist polynomiell.

01:13:09.530 --> 01:13:17.910
Das heißt, wenn das P polynomiell lösbar ist und das Q polynomiell auf

01:13:17.910 --> 01:13:21.290
P reduzierbar ist, dann ist auch das Q polynomiell lösbar, weil ich da

01:13:21.290 --> 01:13:22.870
einmal rumlaufen kann.

01:13:24.390 --> 01:13:29.950
Wenn aber das, wenn ich weiß, dieses Q ist nicht polynomiell lösbar,

01:13:30.090 --> 01:13:34.490
das ist wieder einfach die Umkehrung, und das Q ist polynomiell

01:13:34.490 --> 01:13:38.730
reduzierbar auf P, dann kann auch P nicht polynomiell lösbar sein.

01:13:41.980 --> 01:13:45.360
Ja, also das ist, wenn ich weiß, das kann nicht polynomiell gelöst

01:13:45.360 --> 01:13:49.960
werden, dann kann ich auch durch eine Transformation das P nicht

01:13:49.960 --> 01:13:53.260
entsprechend, dann kann auch das nicht polynomiell lösbar sein, denn

01:13:53.260 --> 01:13:56.100
wäre es polynomiell lösbar, hätte ich ja durch diese polynomielle

01:13:56.100 --> 01:14:02.520
Reduktion ein Lösungsverfahren gefunden für Q, das polynomieller Zeit

01:14:02.520 --> 01:14:04.860
lösbar oder berechenbar gewesen wäre.

01:14:05.520 --> 01:14:06.960
Also das ist diese Transformation.

01:14:07.880 --> 01:14:12.160
Ein Beispiel hatte ich Ihnen versprochen, nämlich das Beispiel, dass

01:14:12.160 --> 01:14:19.900
wir zwei Matrizen mollifizieren wollen, Matrizen A und B, zwei n-Kreuz

01:14:19.900 --> 01:14:20.540
-n -Matrizen.

01:14:21.620 --> 01:14:26.900
Dann definiere ich einfach eine Transformation in eine 3n mal 3n

01:14:26.900 --> 01:14:31.740
-Matrix C, die so aussieht, dass es eine Diagonalmatrix ist, wo sich

01:14:31.740 --> 01:14:34.160
hier oben die beiden Matrizen A und B reinschreiben.

01:14:34.160 --> 01:14:37.820
Und hier in der Diagonalen haben Sie nur 3 mal Identitätsmatrix, also

01:14:37.820 --> 01:14:41.760
3 mal Identitätsmatrix der Größe n.

01:14:43.820 --> 01:14:48.800
Und die inverse Matrix dazu hat diese Struktur und da haben Sie hier

01:14:48.800 --> 01:14:50.180
oben das Produkt drin stehen.

01:14:50.580 --> 01:14:55.540
Das heißt, wenn Sie invertieren können, dann können Sie auch das

01:14:55.540 --> 01:14:57.080
Produkt von zwei Matrizen berechnen.

01:14:59.280 --> 01:15:04.260
Und insofern ist also dieser Weg hier möglich, ist nicht unbedingt

01:15:04.260 --> 01:15:10.580
effizient, ist aber sogar mit der gleichen Zeitkomplexität O von n

01:15:10.580 --> 01:15:12.060
hoch 3 machbar.

01:15:12.540 --> 01:15:15.420
Sogar in O von n hoch 2.3 irgendwas.

01:15:17.080 --> 01:15:19.020
Das kommt in einer anderen Vorlesung.

01:15:19.020 --> 01:15:22.560
Also das kann man dann zeigen, damit ist also die Zeit für die

01:15:22.560 --> 01:15:26.500
Multiplikation in der gleichen Größenordnung, wie die Inversion von

01:15:26.500 --> 01:15:28.100
entsprechend etwas größeren Matrizen.

01:15:28.480 --> 01:15:29.680
Das ist genau eine solche Transformation.

01:15:29.940 --> 01:15:33.760
Wir werden noch weitere Transformationen kennenlernen von Problemen.

01:15:35.160 --> 01:15:39.780
Und jetzt kommen wir zu einem Begriff, der in dem Zusammenhang ganz

01:15:39.780 --> 01:15:40.380
wichtig ist.

01:15:40.460 --> 01:15:42.580
Ich hatte gesagt, es gibt bestimmte Probleme, von denen wir wissen,

01:15:42.640 --> 01:15:43.880
die sind relativ schwer.

01:15:43.880 --> 01:15:47.940
In der Menge aller Probleme, die in dieser Menge NP drin sind.

01:15:48.100 --> 01:15:52.400
In der Menge NP sind ja auch alle Probleme drin, die in konstanter

01:15:52.400 --> 01:15:56.060
Zeit oder linearer Zeit lösbar sind oder in quadratischer Zeit.

01:15:56.420 --> 01:15:58.520
Aber es gibt eben auch Probleme, die sind relativ schwer.

01:15:59.440 --> 01:16:04.420
Und wir sagen jetzt, wir charakterisieren die Schwierigkeit der Lösung

01:16:04.420 --> 01:16:10.000
eines Problems dadurch, welche Menge von anderen Problemen ich auf

01:16:10.000 --> 01:16:12.900
dieses Problem reduzieren kann in polemischer Zeit.

01:16:12.900 --> 01:16:19.800
Ich habe ein Problem X und ich sage, dieses Problem X ist von einer

01:16:19.800 --> 01:16:23.320
Gestalt, dass ich viele andere Probleme in polemischer Zeit darauf

01:16:23.320 --> 01:16:24.160
reduzieren kann.

01:16:24.240 --> 01:16:28.000
Und diese vielen anderen Probleme seien zum Beispiel irgendwelche

01:16:28.000 --> 01:16:31.880
Probleme Q1, Q2, Q3 aus NP.

01:16:32.060 --> 01:16:36.640
Alle Probleme aus NP, egal welches Problem, kann ich in polemischer

01:16:36.640 --> 01:16:38.880
Zeit reduzieren auf dieses Problem X.

01:16:41.580 --> 01:16:48.960
Das heißt, wenn ich hierfür eine Lösung finde, kann ich die Lösung

01:16:48.960 --> 01:16:52.900
transformieren in eine Lösung von Q1 oder Q2 oder Q3, entsprechend der

01:16:52.900 --> 01:16:53.680
jeweiligen Transformation.

01:16:55.320 --> 01:17:00.180
Ich muss also jedes Problem aus NP auf das X reduzieren können.

01:17:00.940 --> 01:17:10.120
Und dann weiß ich ja, die Lösung dieses Problems X hier, die ist

01:17:10.120 --> 01:17:15.720
mindestens so schwer, wie die Lösung des schwierigsten Problems aus

01:17:15.720 --> 01:17:15.980
NP.

01:17:18.260 --> 01:17:22.640
Ich kann ja in der gleichen Komplexität, mit der ich das X lösen kann,

01:17:23.100 --> 01:17:26.540
kann ich bis auf polynomiale Unterschiede jedes andere Problem aus NP

01:17:26.540 --> 01:17:26.880
lösen.

01:17:29.100 --> 01:17:32.320
Und deswegen sage ich, das ist NP schwer.

01:17:32.940 --> 01:17:35.580
Mindestens so schwer, wie jedes Problem, das in NP liegt.

01:17:38.020 --> 01:17:43.580
Wenn ich also jetzt dieses Problem X in polynomieller Zeit in eine

01:17:43.580 --> 01:17:47.900
Lösung LX transformieren könnte, dann könnte ich ja auch entsprechend,

01:17:48.360 --> 01:17:51.980
nicht direkt, also könnte ich im Prinzip aus den entsprechenden

01:17:51.980 --> 01:17:58.880
transformierten Problemen Q1 auf X reduzieren oder Q2 oder Q3, könnte

01:17:58.880 --> 01:18:02.020
ich hier was zurück transformieren auf Lösungen von Q1, Q2, Q3.

01:18:02.640 --> 01:18:06.720
Wenn das hier in polynomieller Zeit wäre, das X, dann könnte ich jedes

01:18:06.720 --> 01:18:09.840
Problem aus NP in polynomieller Zeit lösen.

01:18:10.640 --> 01:18:14.560
Und das heißt, wenn ich diese Frage beantworten möchte, ist die Menge,

01:18:15.260 --> 01:18:19.740
die Problemklasse P gleich der Problemklasse NP, muss ich ein Problem

01:18:19.740 --> 01:18:27.100
finden, das NP schwer ist und das ich in polynomieller Zeit lösen

01:18:27.100 --> 01:18:27.600
kann.

01:18:28.660 --> 01:18:35.080
Wenn ich das finde, nur bei einem einzigen Problem, dann habe ich

01:18:35.080 --> 01:18:37.900
tatsächlich für alle das gelöst.

01:18:37.900 --> 01:18:42.060
Und das ist ein ganz toller Ansatz, weil dadurch der Aufwand, um

01:18:42.060 --> 01:18:46.180
tatsächlich zu beweisen, ist das P gleich NP oder P ungleich NP, sich

01:18:46.180 --> 01:18:49.560
darauf reduziert, für ein Problem eine Aussage zu machen, von dem ich

01:18:49.560 --> 01:18:50.860
nur wissen muss, ist das NP schwer.

01:18:51.520 --> 01:18:54.720
Jetzt gibt es natürlich beliebig schwierige Probleme, die außerhalb

01:18:54.720 --> 01:18:57.620
von NP liegen können, die NP schwer sind.

01:18:58.460 --> 01:19:02.360
Und es ist klar, die sind also mindestens so schwer wie jedes Problem

01:19:02.360 --> 01:19:02.820
aus NP.

01:19:02.820 --> 01:19:07.260
Und was uns jetzt besonders interessiert, das sind die Probleme, die

01:19:07.260 --> 01:19:12.260
so schwer sind wie jedes Problem aus NP, aber gleichzeitig in NP

01:19:12.260 --> 01:19:12.620
liegen.

01:19:15.160 --> 01:19:18.360
Und das Interessante ist zum Beispiel, das Problem des

01:19:18.360 --> 01:19:21.280
Handelsreisenden gehört zum Beispiel dazu.

01:19:22.760 --> 01:19:26.800
Das ist so schwer wie jedes andere Problem aus NP.

01:19:29.740 --> 01:19:33.420
Und es sind praktisch die schwersten Probleme in NP, weil ich jedes

01:19:33.420 --> 01:19:35.300
andere auf diese Probleme reduzieren kann.

01:19:36.760 --> 01:19:45.000
Dieser Begriff wurde vor über 40 Jahren geprägt, definiert.

01:19:45.000 --> 01:19:50.420
Und dieser Stephen Cook von der University of Toronto in Kanada, der

01:19:50.420 --> 01:19:55.940
hat damals insbesondere gezeigt, dass das Erfüllbarkeitsproblem der

01:19:55.940 --> 01:20:01.780
Aussagenlogik, also ich gebe Ihnen irgendeine Formel, A und B oder ich

01:20:01.780 --> 01:20:09.340
sage hier in konjunktiver Normalform, machen wir lieber A oder B und C

01:20:09.340 --> 01:20:15.520
oder D oder A und so weiter.

01:20:15.640 --> 01:20:20.080
Irgendwelche logischen Formel, eine aussagenlogische Formel in

01:20:20.080 --> 01:20:23.360
konjunktiver Normalform, das heißt wir haben hier eine konjunktive

01:20:23.360 --> 01:20:25.400
Verknüpfung von Disjunktionen.

01:20:25.400 --> 01:20:30.080
Wenn Sie sich eine beliebige solche Formel anschauen und feststellen

01:20:30.080 --> 01:20:33.360
wollen, ist die erfüllbar, das heißt gibt es eine Belegung der

01:20:33.360 --> 01:20:37.880
Variablen dort mit Wahrheitswerten, sodass diese Formel insgesamt wahr

01:20:37.880 --> 01:20:39.560
ist oder nicht.

01:20:40.120 --> 01:20:42.380
Das ist das Erfüllbarkeitsproblem der Aussagenlogik.

01:20:44.520 --> 01:20:47.300
Dieses Problem ist ein NP-schweres Problem.

01:20:48.480 --> 01:20:54.000
Das heißt, ich kann jedes Problem aus NP in eine aussagenlogische

01:20:54.000 --> 01:20:55.440
Formel transformieren.

01:20:56.860 --> 01:21:01.780
Und wenn ich die Erfüllbarkeit einer aussagenlogischen Formel in

01:21:01.780 --> 01:21:06.840
polymeter Zeit machen kann, dann kann ich natürlich das Ergebnis

01:21:06.840 --> 01:21:09.060
problemlos reduzieren.

01:21:09.120 --> 01:21:11.320
Ich muss nur feststellen, ist diese Formel wahr oder nicht.

01:21:11.800 --> 01:21:15.000
Aus wahr oder nicht habe ich dann das ursprüngliche Problem auch

01:21:15.000 --> 01:21:15.400
gelöst.

01:21:16.420 --> 01:21:19.220
Das ist das erste Problem, von dem man nachgewiesen hat, es ist NP

01:21:19.220 --> 01:21:21.680
-schwer, auch NP-vollständig.

01:21:22.020 --> 01:21:26.360
Wenn ich die Lösung geraten habe, dass ich überprüfen kann, ob die

01:21:26.360 --> 01:21:28.400
Formel damit wahr ist oder nicht, das ist ganz einfach.

01:21:29.120 --> 01:21:36.760
Und damit habe ich also das Enthaltensein in NP sofort mit drin.

01:21:37.560 --> 01:21:41.000
Und was ich schon gesagt hatte, dieses Travelling Salesperson Problem

01:21:41.000 --> 01:21:46.460
ist auch ein solches Problem, bei dem ich, wie es formuliert ist,

01:21:46.600 --> 01:21:50.900
steht hier nochmal, das ist auch ein NP-vollständiges Problem.

01:21:51.680 --> 01:21:55.600
Und ich kann also zeigen, dass ich das Satzproblem reduzieren kann auf

01:21:55.600 --> 01:21:56.880
das Travelling Salesperson Problem.

01:21:57.680 --> 01:22:03.340
Und da ich jedes NP-Problem auf Satz reduzieren kann, kann ich auch

01:22:03.340 --> 01:22:06.940
dann mit einer weiteren Transformation jedes Problem auf das

01:22:06.940 --> 01:22:08.560
Travelling Salesperson Problem reduzieren.

01:22:09.460 --> 01:22:12.200
Und wenn ich das weiß, wenn ich zum Beispiel das Travelling

01:22:12.200 --> 01:22:17.040
Salesperson Problem auf die Projektplanung mit beschränkten Ressourcen

01:22:17.040 --> 01:22:22.840
abbilden möchte, oder abbilden kann, dann habe ich auf einmal auch,

01:22:23.000 --> 01:22:25.740
dass Projektplanung mit beschränkten Ressourcen und zeitlichen Mindest

01:22:25.740 --> 01:22:30.320
- und Maximalabständen ein NP-vollständiges Problem ist.

01:22:30.420 --> 01:22:33.700
Und hier ist sogar die Bestimmung einer zulässigen Lösung NP

01:22:33.700 --> 01:22:34.460
-vollständig.

01:22:35.040 --> 01:22:38.860
Zu überprüfen, ob eine Lösung für dieses Projektplanungsproblem

01:22:38.860 --> 01:22:41.600
zulässig ist oder nicht, ist bereits NP-vollständig.

01:22:42.080 --> 01:22:45.520
Also das sind eine ganze Reihe von Begriffen, die werden wir nächstes

01:22:45.520 --> 01:22:47.360
Mal am Montag dann nochmal weiterführen.

01:22:47.680 --> 01:22:51.240
Und dann kommen wir auch ans Ende dieses Teils formale Modelle.

01:22:52.520 --> 01:22:56.340
Da geht es eben jetzt einfach darum, allgemeine Charakterisierung zu

01:22:56.340 --> 01:22:58.240
machen von der Schwierigkeit von Problemen.

01:22:58.660 --> 01:23:03.100
Das hier sind zentrale Begriffe, weil ich nämlich sowas weiß, weil

01:23:03.100 --> 01:23:06.300
sobald ich ein NP-schweres Problem habe, muss ich sehr genau

01:23:06.300 --> 01:23:08.480
aufpassen, was ich damit mache, wie ich das löse.

01:23:08.480 --> 01:23:09.640
Das schauen wir uns nächstes Mal an.

01:23:09.720 --> 01:23:10.940
Ich danke Ihnen für die Aufmerksamkeit.