EIG015 Mathe zählen mit Gödel

0:00 Hallöchen, Hallöchen! Ihr hört richtig, ihr hört Eigenraum. Ich bin wieder da. Es hat länger gedauert, als mir lieb ist mit dieser neuen Folge, aber dafür habe ich ein neuronales Netz trainiert, nämlich mein Hirn, damit es diesen Podcast heute generieren kann. Also, ich schreite zu einer neuen Folge und wie ihr den Titel schon entnehmen könnt, geht es heute ums Abzählen. Einige von euch kennen bestimmt den Graf Zahl aus der Sesamstraße.

0:29 Ich bin ja als Kind nicht so richtig mit der Sesamstraße sozialisiert worden, aber so nach einiger Lebenszeit nimmt man doch so einiges auf. Jedenfalls gibt es ja diesen Graf Zahl, der hört sich ungefähr so an. Nummer 1, ein Kellner. Was war das? Nur ein bisschen Blitz und Donner. Und dieser Graf Zahl, der zählt immer irgendwelche Sachen durch in verschiedenen Folgen und es gibt bestimmt auch eine Folge, wo der Computerprogramme durchzählt oder mathematische Sätze oder so.

0:59 Und wenn es die Folge nicht gibt, dann sollte es die Folge vielleicht doch geben. Naja, also ihr könnt mir ja dann sagen, ob es so eine Folge gibt und den YouTube-Link in die Kommentare packen. Und ich hatte neulich sogar in einer Klausur, die ich schreiben ließ, eine Aufgabe dazu. Da sollte man zeigen, dass es genauso viele Computerprogramme gibt wie natürliche Zahlen. Also in der Fachsprache sagen wir, dass die Computerprogramme abzählbar unendlich viele sind. Natürlich gibt es unendlich viele Computerprogramme. Das kann man ganz einfach sehen. Zum Beispiel gibt es das Computerprogramm, was einfach die Zahl 1 ausgibt und es gibt das Computerprogramm, was die Zahl 2 ausgibt und es gibt das Computerprogramm,

1:35 was die Zahl 3 ausgibt und so geht es immer weiter. Also gibt es mindestens so viele Computerprogramme, wie es Zahlen gibt. Aber lustigerweise gibt es auch nur genauso viele Computerprogramme, wie es natürliche Zahlen gibt. Und der Beweis ist eigentlich auch gar nicht so schwer, denn so ein Computerprogramm, das kann man ja abspeichern in einer Textdatei.

1:54 Und da benutzt man irgendwie einen endlichen Zeichensatz, zum Beispiel ASCII oder in der moderneren Programmiersprache UTF-8 oder so. Jedenfalls ist der Witz an der Sache, dass dieser ASCII-Code aus nur endlich vielen Zeichen besteht und UTF-8 auch. Es sind zwar ziemlich viele bei UTF-8, aber jedenfalls nur endlich viele. Und dann kann man einfach durchzählen. Man fängt an mit dem leeren Text. Das ist der erste. Ist auch ein Programm. Ich zähle erstmal alle Texte durch, die es gibt. Dann fange ich an mit dem leeren Text und dann fange ich an mit dem Text, der nur aus einem A besteht. Und dann nehme ich den Text, der nur aus einem B besteht. Und gehe ich erstmal alle Texte durch, die nur aus einem

2:30 Buchstaben bestehen oder einem Zeichen in meiner Sprache. Und da bin ich nach endlicher Zeit fertig, weil ich die alle durchnummeriert habe, eigentlich nur die Buchstaben. Und dann mache ich alle Texte mit zwei Buchstaben. Dann mache ich alle Texte mit drei Buchstaben und so weiter und so fort. Jetzt ist es natürlich so, dass ich da vielleicht nicht immer ein Computerprogramm abgezählt habe, weil AAA5B17 ist kein gültiges Computerprogramm. Jedenfalls nicht in der Programmiersprache, die ich kenne. Und wenn man nur die Computerprogramme abzählen will, dann wählt man einfach aus allen Texten die aus, die gültig sind und nummeriert die dann nochmal neu. Man nummeriert erst alle Texte durch und dann wählt man daraus alle aus, die gültige Haskell-Programme sind. Und dann hat

3:10 man alle Haskell-Programme abgezählt und so weiter. Man kann für so einen Text übrigens auch berechnen, ob er ein gültiges Programm ist. Das wäre sozusagen eine Art Syntax-Prüfung. Obwohl man nicht berechnen kann, ob das Programm dann anhält oder was das Programm macht. Aber dazu später mehr. So, also kann man Computerprogramme durchzählen. Man kann auch Mathematik durchzählen. Man kann alles durchzählen, was man aufschreiben kann. Zum Beispiel, wenn man Mathematik aufschreibt, dann braucht man irgendwie so mathematische Symbole, wie zum Beispiel, wenn man Zahlen aufschreiben will, braucht man ein Symbol für die Null. Dann braucht man ein Symbol für den Nachfolger von einer Zahl. Wenn man das ausdrücken will, dann kann man alle Zahlen ausdrücken,

3:44 indem man so viele Nachfolgersymbole davor macht, wie man die Zahl haben will. Dann braucht man für so logische Aussagen vielleicht noch Klammern und existiert ein Zeichen und für alle Zeichen. Naja, so die mathematische Notation, die in der formalen Sprache der Mathematik vorkommt. Aber das sind auch nur endlich viele Zeichen. Man kann prüfen, ob das, was da steht, gültige Mathematik ist. Und man hat vielleicht noch so ein kleines Problem mit so Variablen, die man manchmal in mathematischen Aussagen braucht. Aber das ist auch nur ein kleines Problem. Denn man nimmt sich einfach so eine Platzhaltervariable, sagen wir mal x, und dann nimmt man noch einen Strich, einen Modifikator, so wie wir das gerne machen in der Mathematik.

4:24 Und die zweite Variable, wenn man noch eine zweite braucht, die nennen wir dann einfach x' und der Strich ist auch so ein Zeichen. Und wenn wir drei Variablen brauchen, nennen wir x, x' und x''. Und so weiter. Ist eigentlich genauso wie mit diesem Nachfolgersymbol, das uns erlaubt, alle natürlichen Zahlen mit nur endlich vielen Zeichen auszudrücken. Ja, also kann man so aufgeschriebene Mathematik überprüfen, ob die gültig ist. Also kann man auch die mathematischen Sätze durchzählen.

4:52 So, aber warum soll man das machen? Also das ist natürlich irgendwie eine interessante Übung, wenn man sich so fragt, wie groß ist unendlich und was ist alles unendlich und wie viel gibt's davon. Aber eigentlich ist es so ein bisschen wie mit diesen Affen an der Schreibmaschine. Also wenn ein Affe an der Schreibmaschine irgendwelche zufälligen Buchstaben schreibt, unendlich lange, dann kommt da zufällig auch irgendwann mal der komplette Text von dem Buch Neinhorn drin vor. Aber und? Was soll das jetzt? Und diese Nummerierung ist auch total beliebig.

5:25 Also wir haben ja eigentlich nichts vorgegeben, sondern nur so eine Art Existenzbeweis. Also man kann die Mathematik durchnummerieren, aber die Nummerierung enthält keinen Inhalt. Wenn ich jetzt die Nummer eines Programms habe, in dieser Nummerierung, zum Beispiel das Programm Nummer 17 oder das Programm Nummer 17.717, dann kann ich nicht zurückschließen auf das Programm oder die Nummer einer mathematischen Aussage. Ich kann die Aussage nicht rekonstruieren aus der Nummer. Und wenn man das noch macht, wenn man es schafft, so zu nummerieren, dass man mechanische Art und Weise, also mit einem Computer zwischen der Aussage oder dem Programm und seiner Nummer hin und her wechseln kann, also insbesondere auch zurück von der Nummer zum Programm, dann hat

6:17 man eine Gödelnummerierung, nennt sich das. Und sowas ist ganz praktisch. Und eine Möglichkeit, es gibt viele Möglichkeiten, das hinzukriegen, diese Gödelnummerierung. Und eine lustige Art und Weise, das zu tun hat, mit der Primfaktorzulegung zu tun, die wir letztes Mal besprochen haben. Und die Grundidee für die Umkehrung ist, also dass man aus der Zahl wieder das Programm berechnen kann, ist, die Primfaktorzulegung der Zahl auszunutzen. Also die Primfaktorzulegung ist eindeutig. Das haben wir ja das mal besprochen. Und aus dieser eindeutigen Primfaktorzulegung wollen wir irgendwie ablesen, was das für ein Programm ist. Jetzt überlegen wir mal. Also wir schreiben diese Primfaktorzulegung hin. Dann steht da, unsere Zahl ist also 2 hoch irgendwas. Vielleicht 2 hoch 0,

7:06 aber vielleicht auch 2 hoch irgendwas Größeres. Also kommt jedenfalls ein paar mal 2 oder eben kein mal 2 in unserer Zahl vor. Und dann kommt 3 ein paar mal vor oder nicht. Und 5 ein paar mal oder nicht. Und die Information über unser Programm, die können wir jetzt codieren in diesen Anzahlen, wie oft jeder Primfaktor vorkommt. Und wir machen das auf ganz naive Art und Weise. Wir schauen einfach, die 2 ist die erste Primzahl. Wie oft kommt die 2 vor? Und diese Anzahl, die ist eindeutig unsere Zahl zugeordnet, die soll uns codieren, was das erste Zeichen von unserem Programm ist. Und die 3 ist die zweite Primzahl. Und wie oft die 3 vorkommt, soll uns codieren, was das zweite Zeichen von unserem Programm ist. Also andersherum noch mal.

7:57 Wenn ich einen Text habe oder ein Programm und das jetzt in eine Zahl umwandeln will, sodass ich auch wieder zurückkomme, dann nehme ich einfach für jedes Symbol, wie zum Beispiel ein ASCII-Symbol oder ein UTF-8-Symbol, das vorkommen kann, irgendeine natürliche Zahl. Ich nummeriere die irgendwie durch. Bei ASCII ist das ja schon durchnummeriert. Also die ASCII-Tabelle, da haben die Buchstaben irgendwie Zahlen. Also p ist 112 und was weiß ich. Und dann speichert man das erste Zeichen so ab. Man nimmt einfach 2 hoch, die Zahl für das erste Zeichen in meinem Text. Und dann 3 hoch, die Zahl für das zweite Zeichen. Also wenn ich jetzt irgendwie sowas wie print hello world schreiben will, dann suche ich erst mal, was das p ist. Print hello world fängt mit p an. Also suche ich,

8:42 was das p für ein ASCII-Code hat. Das hat 112, wie ich gerade schon sagte. Also nehme ich 2 hoch 112. Das ist schon eine ganz schön große Zahl. Aber dann nehme ich das r, weil bei print hello world kommt als zweites ein r. Das hat die 114. Also multipliziere ich noch dazu 3 hoch 114. Und dann suche ich das i und nehme 5 hoch diese Zahl von dem i. Und so mache ich immer weiter. Ihr seht schon, dass das jetzt eine ziemlich große Zahl werden kann. Ein bisschen unübersichtlich. Aber es geht ums Prinzip. Und das Prinzip ist, man kann wieder zurückrechnen. Weil die Primfaktorzerlegung eindeutig ist, kann ich, wenn ich dieses große Produkt kriege am Ende, die Primfaktorzerlegung im Prinzip berechnen und

9:28 auch wieder zurück. Also dass die Zahlen jetzt riesig groß werden, ist mir egal. Primfaktorzerlegung von großen Zahlen ist auch schwer, wie man schon öfter gehört hat. Und die Sicherheit von irgendwelchen kryptographischen Algorithmen basiert darauf. Aber das ist hier relevant, weil es uns nur ums Prinzip geht, kann berechnet werden auf mechanische Art und Weise. Wenn man jetzt die praktischen Aspekte von dieser Methode dann wirklich sehen will, dann ist es vielleicht hier auch gar nicht so schwer. Man kann ja den Text der Reihe nach dekodieren, indem man erst mal bestimmt, wie oft ist die Zahl durch zweiteilbar und dann wie oft ist die Zahl durch dreiteilbar.

10:05 Das ist also keine richtige Faktorisierung, sondern man geht einfach die Primfaktoren der Reihe nach durch und macht so Division mit Rest irgendwie optimiert. Naja, könnte trotzdem lange dauern. Habe ich mir jetzt nicht so genau überlegt und ich glaube, das ist auch nicht so relevant. Was natürlich dazu führt, wenn man das so macht, dass die allermeisten Zahlen gar keine Aussage kodieren. Ja, denn Zahlen, die irgendwie Primfaktoren haben, die nicht in meinem ASCII-Code sind, also irgendwelche großen Primfaktoren, kommen gar nicht vor. Aber das ist nicht schlimm. Also nicht jede Zahl kodiert jetzt ein wirkliches Programm, aber das ist kein Problem. Man kann ja aus der Zahl die Primfaktorzerlegung berechnen und feststellen, dass es kein Programm kodiert.

10:51 Auf Wikipedia habe ich übrigens gelesen, dass Graf Zahl die Lieblingszahl 34.969 hat und das ist das Quadrat von 187. 187 ist 11 mal 17, also ist die Lieblingszahl von Graf Zahl 11 Quadrat mal 17 Quadrat. Und deswegen ist sie eigentlich auch kein Programm, weil die gar keine Zweipotenz vorkommt. Um das erste Zeichen von dem entsprechenden Programm abzulesen, müssten wir schauen, was da für eine Zweipotenz drin vorkommt. Und da kommt gar keine drin vor. Also hat er sich eben keine Gödel-Nummer von einem Programm ausgesucht, der Graf Zahl. Diese Gödel-Nummerierung wurde übrigens von Gödel erfunden, von Kurt Gödel zum Beweis des Unvollständigkeitssatz 1930er Jahre. Und wer diese großen Zahlen nicht mag, das ist auch gar nicht nötig. Man könnte auch den ASCII-Code so

11:48 ein bisschen abändern, so dass der keine Nullen mehr verwendet, also zum Beispiel die 100 nicht vorkommt als ASCII-Code. Und dann kann man 0 als Trennzeichen nehmen und schreibt einfach die Zahlen hintereinander, die Symbole. Also schreibt man, wenn man das erste Zeichen haben will, schreibt man eine 1 und wenn man das zweite Zeichen haben will, schreibt man eine 2. Aber eine 10 darf man nicht nehmen, weil die eine 0 enthält. Also man darf keine Zahlen nehmen, die eine 0 enthalten. Und dann schreibt man die einfach hintereinander und als Trennzeichen zwischen die einzelnen Zeichen macht man jeweils eine 0. Und wenn man die einfach so die Stellen hintereinander schreibt, kriegt man auch eine natürliche Zahl. Und aus der natürlichen Zahl kann man jetzt nicht mit Primfaktor zur

12:21 Rekonstruktion, aber einfach indem man sie an den Nullen aufspaltet, auch die Zeichenkette wieder rekonstruieren. Was auch noch witzig ist, jede Zahl hat auch wieder eine Gödelzahl. Also ich könnte zum Beispiel meine Lieblingszahl 17, die könnte ich ausdrücken in der formalen Mathematik als den Nachfolger vom Nachfolger vom Nachfolger von 0. Also 17 mal der Nachfolger von 0 ergibt ihm die 17. Und das ist eine Formel in der Mathematik. Die Formel ist Nachfolger von Nachfolger von Nachfolger von 0. Und diese Formel kann ich dann Gödel kodieren und dann bekomme ich eine Zahl. Eine irre große Zahl, weil da 17 mal dieses Nachfolgersymbol steht. Aber diese Zahl ist dann die Gödelzahl von meiner 17. Also auch jede Zahl hat eine Gödelzahl. Okay, aber es kommt noch

13:12 schlimmer. Jeder Beweis, den wir in der Mathematik führen, also so das Brot und Butter unserer Mathematik, ist ja auch ein Stück Mathematik. Also er ist irgendwie aufgeschrieben, der sagt, ich nehme die Aussage und nehme die Aussage, kombiniere die mit logischen Regeln und die ganzen logischen Regeln, die kann ich alle aufschreiben und wie ich die anwende und welche Aussagen. Also hat auch ein Beweis eine Gödelnummer. Okay, alles in der Mathematik hat eine Gödelnummer.

13:41 Wir haben die ganze Mathematik durchnummeriert. Und wegen dieser ganzen Berechenbarkeit kann man auch zurück, wenn man eine Zahl hat, kann man da überprüfen, ob die zu einem gültigen Stück Mathematik gehört. Und man kann dann auch so Aussagen überprüfen. Wir haben jetzt die ganze Mathematik eingebettet in die Zahlen. Also wenn ich jetzt zum Beispiel prüfen will, ob ein Beweis eine Aussage beweist. Ich habe eine Aussage und ich habe einen Beweisvorschlag dazu. Dann kann ich ja mechanisch überprüfen, ob der Beweis die Aussage beweist. Er prüft den Beweis eben auf Korrektheit, ob alle Schlussregeln korrekt angewendet wurden. Und das kann ich aber auch mit den Gödelzahlen machen. Ich kann also auch prüfen, wenn ich zwei Zahlen habe, ob die erste

14:29 Zahl die Gödelzahl eines Beweises für die Aussage ist, die durch die zweite Zahl kodiert wurde. Wenn ich also zwei Zahlen habe, dann stimmt es entweder, dass die erste Zahl ein Beweis für die zweite Zahl ist, nachdem ich sie dekodiert habe, oder es stimmt halt eben nicht. Und das kann man alles überprüfen. Und die Witze an der Sache ist eben diese Berechenbarkeit der Umkehrfunktion. Die macht allerlei lustige Sachen möglich. Also wenn man nicht dumm durchnummeriert, wie wir es am Anfang gemacht haben, sondern auf diese schlaue Gödelart und Weise, dann hat man was Sinnvolles gemacht, weil die Mathematik jetzt über sich selbst sprechen kann. Also die ganze Mathematik ist eingebettet in die Zahlen und es gibt eine Wissenschaft, die sich mit Zahlen beschäftigt,

15:15 nämlich die Mathematik. Also können wir jetzt mit Mathematik Mathematik untersuchen. Und das ist die wichtige Einsicht von Kurt Gödel, die ihn dann zum Gödelsatz und damit dem Unvollständigkeitssatz führte. Ich will jetzt einmal so einen Gödelsatz sagen und das wird jetzt ein bisschen heftig. Also ihr habt jetzt verschiedene Möglichkeiten. Ihr könnt jetzt entweder Skip drücken und die nächste Kapitelmarke anspringen oder ihr hört es euch fünfmal an oder ihr versucht es einfach einmal euch anzuhören. Aber wenn ihr jetzt gerade Fahrrad fahrt, dann ach, ihr haltet lieber an. Ich will für nichts verantwortlich sein. Also, ich versuch's mal. Es gibt eine Formel, die hat zwei Variablen x und y. Ich nenne die Formel jetzt mal f von x, y. Für

15:59 diese Variablen kann ich natürliche Zahlen einsetzen und dann kann die Formel stimmen oder nicht stimmen. Und ich baue die Formel so, dass wenn ich da zwei natürliche Zahlen m und n einsetze, dann soll f von m und n gültig sein, wenn m die Gödelzahl eines Beweises von n ist. Also das, was ich eben gesagt habe, welches existiert, dass ich überprüfen kann, ob eine Zahl ein Beweis von einer anderen Zahl ist nach Dekodierung. Das schreibe ich jetzt als Formel. Die Formel ist richtig, wenn das stimmt und sonst falsch. Okay, das ist meine Aussage. So, aus der Formel bilde ich jetzt eine mathematische Aussage. Die Aussage nenne ich g und die Aussage g geht so. Für alle y gilt f von x und y nicht. In dieser mathematischen Aussage ist das x noch frei. Das y,

16:55 das zweite Argument, also x ist das, wo der Beweis drin stehen soll in meinem f und y ist das, was bewiesen werden soll. Und jetzt sage ich, für alle y gilt f von x, y nicht. Also für alle y ist x kein Beweis von y. Also existiert überhaupt kein Beweis von y, könnte man so sagen. So, diese Aussage hat eine Gödelzahl, weil alles hat eine Gödelzahl. Sagen wir mal p. p ist jetzt die Gödelzahl von dieser Aussage. Für alle y gilt f von x, y nicht. So, und jetzt kommt die Selbstreferenzialität. Jetzt setze ich p in die Formel ein, in die Formel f. Diese Gödelzahl von der Aussage. Dann erhält man eine Aussage h und die Aussage hängt nur von y ab, weil p habe ich für x eingesetzt. Ich setze p in die Formel ein als x und hätte eine Aussage h, die nur von y

17:48 abhängt. Und die ist selbstreferenziell und die sagt jetzt sowas wie, h gilt genau dann, wenn die Gödelzahl von h nicht die Gödelzahl irgendeines beweisbaren Satzes ist. Okay? h, die Formel, die ich konstruiert habe, gilt genau dann, wenn die Gödelzahl von h nicht die Gödelzahl irgendeines beweisbaren Satzes ist. Daraus folgt, dass h wahr und nicht beweisbar ist. Denn die Formel, die ich oben konstruiert habe, die Formel g, deren Gödelnummer ich genommen habe, die sagt ja, für alle y gilt x ist kein Beweis von y. Das heißt, es gibt keinen Beweis von y. Und die Gödelnummer dieser Formel habe ich genommen und jetzt habe ich die eingesetzt, um die Aussage h zu konstruieren, die dann genau dann gilt, wenn ihre Gödelzahl nicht die Gödelzahl irgendeines beweisbaren

18:50 Satzes ist, sie also nicht beweisbar ist und sie ist wahr. Okay. Diese ganzen Sachen, die muss man aufarbeiten und aufschreiben und Gödel hat es getan in den 30ern. Ein Paper auf Deutsch, das ich auch euch verlinke, das es im Internet zu lesen gibt. Und daraus folgt dann, dass es in der Mathematik unbeweisbare Sätze gibt, die wahr sind. Also wahr sowie wahre Aussagen über natürliche Zahlen. Wenn wir an die natürlichen Zahlen glauben, dann glauben wir, dass es wahre Aussagen über die natürlichen Zahlen gibt. Jede Zahl ist das Produkt auf eindeutige Art und Weise von Primzahlen. Es ist eine wahre Aussage über natürliche Zahlen und die ist beweisbar. Und es gibt aber auch wahre Aussagen, die unbeweisbar sind. Jetzt ist diese Gödel-Aussage natürlich ganz schön konstruiert. Es gibt aber auch

19:38 echte Aussagen, die wirklich was über Zahlen oder Kombinatorik sagen und unbeweisbar sind. Das müsst ihr jetzt mal selbst nachlesen. Ich verlinke euch das Paris-Harrington-Theorem, was wohl die erste kombinatorische Aussage ist, was über Ramsey-Theorie. Da mache ich mal eine andere Folge drüber und das könnt ihr euch mal durchlesen. Also es gibt auch wirklich interessante Aussagen über natürliche Zahlen und kombinatorische Objekte, die nachweisbar war und unbeweisbar sind. Und all das wurde nur möglich durch die Umkehrbarkeit, durch diese Gödelnummerierung. Die ist eben besser als ein Telefonbuch, denn sie erlaubt algorithmische Übersetzung in beide Richtungen. Und das war nötig. Ohne diesen Umweg über die Zahlen zu nehmen, kann die Mathematik nicht über sich selbst sprechen.

20:24 Das ist so ein bisschen so wie, dass ein Satz in der deutschen Sprache nicht sich selbst in Anführungszeichen enthalten kann. Man kann keinen Satz schreiben, der sich selbst enthält. Denn was in den Anführungszeichen steht, ist ja der Satz selbst und da müssen dann die Anführungszeichen wieder drin sein, wo wieder die Anführungszeichen wieder drin sein müssen und so weiter. Also die Selbstreferenzialität war nur möglich durch diesen Umweg. Und das kommt einem auch in der Informatik mal über den Weg. Da gibt es ja diese Programme, Quines heißen die, habe ich auch schon mal darüber geredet, ich weiß gar nicht wo, die sich selbst ausgeben. Also es ist eine gute Fingerübung in einer Programmiersprache, die man mag, ein Programm zu schreiben, das seinen eigenen Quelltext

21:10 ausgibt. Und das funktioniert eben nicht so, dass man print und dann das Programm schreibt, weil das Programm ja dann nicht das Print Statement enthält. Ja, man muss irgendwie einen Umweg machen und lest es mal nach, wie man ein sogenanntes Quine programmiert. Und diese Selbstreferenzialität, die hat natürlich dann auch Anwendungen in der Informatik und einen davon will ich euch noch kurz vorstellen, die immer mit diesen Quines zu tun haben. Und da fragt man sich zum Beispiel, wenn man alle Computerprogramme betrachtet und wissen will, was die so für Laufzeiteigenschaften haben. Also in der Fachsprache semantische Eigenschaften nennt man das. Semantische Eigenschaften sind Eigenschaften über das Verhalten des Programms. Zum Beispiel macht

21:54 das Programm irgendwann, während es läuft, piep. Oder hält das Programm immer an. Oder, vielleicht die wichtigste Eigenschaft, die man prüfen möchte, tut das Programm, was in der Anleitung oder im Verkaufsprospekt steht, was das Programm tut. Angenommen, eine Computerfirma, nennen wir sie mal Macrosoft, gibt uns eine Implementierung der Quadratfunktion. Und wir wollen jetzt prüfen, ob das Programm die Eigenschaften hat, die behauptet werden. Nämlich, dass sie für jede Zahl das Quadrat zurückgibt. Das wäre auch so eine Laufzeiteigenschaft. Also wir wollen Computerprogramme untersuchen auf ihre Laufzeiteigenschaften. Und weil wir faul sind, wollen wir das natürlich mit dem Computer machen. Das heißt, wir wollen ein weiteres

22:37 Computerprogramm schreiben, so eine Art Testprogramm. Und in das Testprogramm geben wir dann unser neues Programm, was wir von Macrosoft gekauft haben, ein. Und das Testprogramm untersucht, ob das Programm von Macrosoft jemals Piep macht. Weil vielleicht möchte man ja nicht, dass der Computer Piep macht. Deswegen möchten wir das Programm vorher testen. Und es gibt einen Satz in der Informatik, der heißt Rice Theorem. Also Rice ist der Name eines Menschen. Da er sagt, dass man so ein Untersuchungsprogramm nicht schreiben kann. Also wenn ein Programm existiert, dass ein einziges Programm, das als Eingabe ein beliebiges anderes Programm krebt und dann eine Eigenschaft entscheidet, mit Sicherheit für jedes Programm, was ich als Eingabe reintue,

23:21 richtig entscheidet, hat das Programm die gegebene Eigenschaft oder nicht, dann kann das nur möglich sein, wenn die Eigenschaft trivial ist. Das heißt, entweder alle Programme haben sie oder kein Programm hat sie. Denn so eine Eigenschaft kann man entscheiden. Da gibt man einfach immer das Gleiche aus. Also sozusagen die konstante Eigenschaft, die alle Computerprogramme haben oder kein Computerprogramm hat. Also dieses Testprogramm macht das Programm jemals Piep. Ein einzelnes Programm, das alle anderen Programme testen kann, kann nicht existieren. Und der Beweis davon benutzt auch Gödel Nummerierung und geht eben auch über so einen Umweg der Selbstreferenzialität.

24:01 Und das führt einen auf allerlei philosophische Fragen. Und ein berühmter britischer Kombinatoriker Peter Cameron schreibt dazu, Gödel's theorem, also bezieht sich auf das Gödel Theorem, has been a battleground for philosophers arguing about whether the human brain is a deterministic machine. In which case presumably we would not be able to prove any formally unprovable statement.

24:23 Fortunately space does not allow me to give more details. Also er ist froh, dass er nicht weiter darüber reden muss, weil er nicht genug Platz hat in seinem Artikel. Und genauso habe ich auch nicht genug Zeit in meinem kleinen Podcast hier, um euch auseinanderzunehmen, ob diese Selbstreferenzialität und die Existenz unbeweisbarer wahrer Aussagen und die Existenz von Computerprogrammen, die ihren eigenen Programmcode ausgeben, dazu führt, dass wir ablehnen müssen, dass das menschliche Gehirn eine deterministische Maschine ist oder nicht. Deswegen kann ich euch noch ein paar Buchtipps geben und in die Shownotes tun. Zum Beispiel das Buch Gödel's theorem von Torkel Frenzen, das ich sogar ein bisschen besser, vor allem dünner finde als Gödel Escherbach,

25:11 in dem einige der Details, wie ich finde, ganz schön erklärt werden. Und für einen Geschichtsüberblick zu Gödel und seinem Leben empfehle ich noch Gödel, Einstein und die Folgen, obwohl das Buch auch viel kritisiert wurde. So, also in diesem Sinne hoffe ich, ihr konntet ein bisschen folgen, seid nicht vom Fahrrad gefallen und schaltet bald mal wieder ein. Macht's gut.