Thomas Kahle
Als ich studiert habe, waren Vorlesungen mit Gödel und mit Kohomologie immer die beliebtesten. Daher geht’s heute mal wieder um Gödel und den Unvollständigkeitssatz. Um den hinzubekommen, muss man aber erst die Mathematik durchnummerieren, und zwar nicht wie Graf Zahl, sondern so, dass man aus den Zahlen auch wieder die Aussagen zurückberechnen kann. Von da aus ist es nicht mehr weit zu Quines — Computerprogrammen, die ihren eigenen Quelltext ausgeben.
- Graf Zahl zählt Hotdogs (YouTube)
- Neinhorn
- Über formal unentscheidbare Sätze (Gödel, 1931)
- Gödels Theorem auf Goodreads
- Gödel, Einstein und die Folgen (Rezension auf spektrum.de)
- Das Paris-Harrington-Theorem ist wahr aber nicht beweisbar.
- Quine-Programme
- Rice-Theorem
- Gödels Theorem (Peter Cameron)
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Automatisch generiertes Transkript (nicht geprüft)
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.
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.
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,
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.
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
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
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,
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.
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.
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.
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
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,
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.
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,
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
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.
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.
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
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
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
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.
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
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,
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
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,
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
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
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
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.
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
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
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
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,
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.
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.
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,
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.
Fun Fact: Nicht immer kann man tatsächlich berechnen, ob etwas ein gültiges Programm ist, die Syntax von C++ ist beispielsweise unentscheidbar.
Ich habe den Beweis nicht mehr komplett im Kopf, das hat mir mal ein befreundeter Informatiker erzählt, aber es läuft darauf hinaus, dass man in das Template-System von cpp (so heißen generics in cpp) eine allgemeine Turingmaschine embedden kann. So bekommt man eine Reduktion auf das Halteproblem.
Moderne Compiler lösen das so, dass sie nach einer bestimmten Rekursionstiefe einfach einen Error werfen, da das in der Praxis aller Wahrscheinlichkeit nach ein Programmierfehler ist. Technisch gesehen verletzen sie damit aber die cpp-Spezifikation.
LG
Interessant. Wenn das so ist, dann gibt es da bestimmt noch viele andere unentscheidbare Dinge. Wie wäre es mit Syntax-Highlighting? Z.B. kann man in LaTeX in einer Mathe-Umgebung wieder eine normale Text-Umgebung öffnen und darin wieder eine Mathe-Umgebung usw. Ist es möglich im Editor alle Textbausteine korrekt einzufärben, sodass Mathe-Umgebungen eine andere Farbe haben als Text?
das ist vielleicht etwas gecheatet, aber LaTeX-Macros sind ja Turingvollständig, man könnte sich vermutlich ein Enviroment definieren, dass entweder ein equation- oder ein text-enviroment ist, je nachdem, was beim Halteproblem herauskommt. Das kann dann natürlich nicht korrekt gesyntax-highlightet werden.