Thomas Kahle
Auf diesem alten Kassenzettel kommen genau 20 DM heraus:
Ist das Zufall? Wir sprechen in dieser Folge über den Zufall und das Verhältnis der Menschen dazu.
- Geschichten aus der Mathematik Podcast
- Sprachnudel: Worte mit 20 Buchstaben
- NullenEinsen Experiment auf github
- Kolmogorov Komplexität
- Mandelbrot Menge
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)
Ja, hallo zusammen, willkommen zurück im Eigenraum zu Folge 40.
Mein Name ist Thomas, ich bin Mathematiker und ich mache das hier,
weil ich denke, dass es nicht genug Mathe-Podcasts gibt. Aber es gibt einen
neuen Mathe-Podcast. Habt ihr den schon gehört?
Er heißt Geschichten aus der Mathematik.
Geschichten aus der Mathematik? Moment mal. Gab es da nicht schon irgendwie
so einen Podcast, der so ähnlich hieß? Geschichten aus der Geschichte oder so?
Das kann doch kein Zufall sein.
Naja, das Geschichten aus der Mathematik-Konzept ist aber ein bisschen anders
als das Geschichten aus der Geschichte-Konzept.
In diesem Podcast erzählen die Hosts anhand einer Person aus der mathematischen
Geschichte eine mathematische Begebenheit und erklären dann auch ein bisschen
wenig Mathe dazu und ja, es ist super aufwendig produziert.
Ich glaube, die haben fünf Leute mindestens, die da am Start sind und naja,
ich verlinke euch das mal, könnt ihr ja mal reinhören.
So, in meiner 40. Folge möchte ich heute euch mal ein bisschen was über Zufall
erzählen oder fehlenden Zufall.
Und nehmen wir mal an, ihr seid im Metzger.
Seid ihr noch im Metzger oder sind wir heutzutage alle vegan?
Das ist ein bisschen old-fashioned.
Also sagen wir mal Supermarkt und ihr macht den Familieneinkauf und der ganze
Wagen ist voll bis oben hin und ihr schaufelt das alles aufs Band und es wird
gescannt und so weiter und so weiter. Und am Ende sagt die Kassiererin dann
nach einem kurzen Stutzen, 100 Euro bitte.
Alle eure Sachen wurden gescannt und es kostet 100 Euro. Und das ist doch ein Zufall, oder?
Also, wenn man so 30 verschiedene Sachen im Korb hat und die kosten alle irgendwie
79, 99 oder was weiß ich Centbeträge und dann sollen genau 100 Euro rauskommen.
Vielleicht hat man auch noch Pfand eingelöst und ein negativer Betrag steht
auch noch mit auf dem Kassensette. Bitte.
Würdet ihr euch darüber wundern? Also ich würde mich darüber schon ein bisschen
wundern. Das ist schon komisch.
Aber auf der anderen Seite, man kauft ja ständig irgendwas ein und dann wird
irgendeine Summe herausgerechnet und irgendeine Zahl, die muss ja rauskommen.
Und wenn diese Zahlen, diese Summen, die da rauskommen, auf dem Kassensendel
unten irgendwie so zufällig verteilt sind, dann könnte es natürlich auch sein,
dass da mal genau die 100 rauskommt.
Diesem Effekt wollen wir doch jetzt mal ein bisschen hier auf den Zahn fühlen.
Zufälligkeit ist auf jeden Fall extrem wichtig für alle möglichen Dinge.
Also wenn man zum Beispiel irgendwie eine Simulation vom Wetter macht oder so,
oder in der Informationssicherheit, wenn man Zufallszahlen braucht,
um sich Schlüsselmaterial zu erzeugen, ständig braucht man irgendwie Zufall
und da kommt natürlich sofort die Frage auf, wie man überhaupt misst, was zufällig ist.
Wie beantwortet man dann eigentlich die Frage, was ist Zufall und was ist zufällig,
wenn man jetzt sowas beobachtet?
Und in der Mathematik haben wir ja das Gebiet der Wahrscheinlichkeitstheorie,
das sich mit mit dem Zufall beschäftigt
und die sollten doch da irgendwas entwickelt haben für uns, oder?
Man könnte auch noch unterscheiden, Wahrscheinlichkeitstheorie und Statistik, also...
Ich würde mal sagen, das sind zwei Richtungen auf der gleichen Straße.
Also wenn der Zufall, was auch immer das jetzt ist, irgendwelche Daten erzeugt
und wir kennen den Zufall und wollen wissen, was für Eigenschaften die Daten
haben, dann machen wir Wahrscheinlichkeitstheorie.
Und wenn wir nur die Daten haben und wissen wollen, welche Eigenschaft hatte
der Zufall, der wohl diese Daten erzeugt hat, dann nenne ich das Statistik.
Und naja, um darüber zu reden, was jetzt zufällig ist, müssen wir uns erstmal
auf eine Definition von zufällig einigen, also von diesem Wort.
Also es kommt jetzt fast schon in so einen philosophischen Bereich rein.
Wenn man eine mathematische Definition macht, muss man erstmal,
um die dann in der Realität zu verwenden, einen Abgleich machen,
dass sie irgendwie das ausdrückt, was man eigentlich ausdrücken möchte oder
zumindest gut genug ausdrückt.
Und an der Stelle bin ich jetzt für das Wort zufällig. Und für meine Folge hier
ist die Arbeitshypothese zufällig bedeutet unvorhersagbar.
Also ein Prozess oder eine Zahl ist zufällig, wenn man aus keiner Gesetzmäßigkeit
oder aus dem Studium der Vergangenheit heraus vorhersagen kann,
was die Zahl oder das Objekt sein wird oder was der Prozess produziert.
Und mit der Zufälligkeit gibt es aber erstmal ein grundlegendes Problem.
Man kann jetzt nicht sagen, ob ein beobachtetes Ding auffällig war.
Stellen wir uns mal vor, wir haben eine endliche Menge von möglichen Ausgaben
eines zufälligen Prozesses.
Also wenn wir zum Beispiel die Ergebnisse auf unserem Kassenzettel nach dem
Zusammenrechnen sehen, dann wird das ja vielleicht immer unter einem hohen Betrag
sein, 1000 Euro, 2000 Euro.
Und es ist immer ein Euro-Cent-Betrag auf zwei Stellen gerundet und deswegen
wären das zum Beispiel nur endlich viele Möglichkeiten von Gesamtsummen,
die auf dem Kassenzettel wirklich vorkommen würden.
Oder, sagen wir mal, wir erzeugen irgendwelche Zeichenketten,
Strings, sagen wir jetzt für das Beispiel der Länge 20 aus unserem normalen Alphabet.
Und der Zufall sei jetzt so, also diese zufällige Erzeugung,
dass jeder Buchstabe komplett unabhängig von den anderen ausgelost wird und
welcher Buchstabe dann an der Stelle steht, auch wieder komplett unabhängig.
Gleich verteilt, unabhängig sein soll. Also jeder Buchstabe von A bis Z hat
die gleiche 1,26 Wahrscheinlichkeit.
Und dann haben wir jetzt so eine Zeichenkette, der für das Beispiel Länge 20,
wo jeder Buchstabe komplett unabhängig, gleich verteilt, ausgewürfelt wird.
Und das macht ihr. Und dann steht da auf einmal das Wort Demonstrativpronomen.
Also das habe ich jetzt nachgezählt, das hat wirklich 20 Buchstaben.
So, also das Wort Demonstrativpronomen ist jetzt da rausgekommen.
Das ist doch schon ein komischer Zufall, oder? Oder?
Also, wenn jetzt da Z, T, S, K, E, R, blablabla stehen würde,
würdet ihr euch vielleicht nicht so wundern, wie wenn da das Wort Demonstrativpronomen steht.
Denn dann denkt ihr bestimmt, das ist doch ein ziemlich komischer Zufall,
dass da jetzt genau ein Wort rausgekommen ist, was ich kenne.
Und war das jetzt Zufall im Sinne unserer obigen Definition?
Naja, es war ja nicht vorhersehbar, dass das Wort Demonstrativpronomen rauskommt.
Aber genauso wenig war es vorhersehbar, was überhaupt für ein Wort rauskommt
oder ob nicht irgendeine Buchstabenkombination herauskommt.
Nun kann man mit elementarer Wahrscheinlichkeitstheorie ja bestimmen,
dass alle Worte da gleichwahrscheinlich sind und mit Worte meine ich jetzt auch
nicht sinnvollen Worte.
Also alle Ausgaben, alle diese Buchstabenkombinationen, die nenne ich jetzt
Worte und alle sind gleichwahrscheinlich, weil wir alles immer mit der gleichen
Wahrscheinlichkeit jeden Buchstaben ausgewürfelt haben.
Also ist Demonstrativpronomen genauso wahrscheinlich oder unwahrscheinlich wie
zum Beispiel das Wort Lastkraftwagenführer oder das Wort Literaturverzeichnis
oder eben die ungefähr zweimal 10 hoch 28 möglichen anderen Kombinationen von
irgendwelchem Buchstabensalat.
Und das sind schon ziemlich viele Kombinationen. Also zweimal 10 hoch 28,
das ist eben eine 2 mit 28 Nullen.
Und ich habe das für euch mal auf sprachnudel.de recherchiert.
Es gibt in der deutschen Sprache wohl 34 Worte mit 20 Buchstaben.
Zum Beispiel noch Unverantwortlichkeit, Zylinderkopfschraube,
Vermessungsingenieur oder Matratzenhorchdienst.
Also was geht da vor sich?
Wenn ich Zylinderkopfschraube lese, ist es genauso wahrscheinlich,
wie wenn ich ZTSKERJWQ lese.
Warum kommt es mir komisch vor? Und das hat mit der menschlichen Psychologie
zu tun und der Evolution.
Menschen sind extrem gut darin, Muster zu erkennen. Das haben wir uns lange
evolutionär erarbeitet, um einfach eine schnellere Verarbeitung zu haben.
Und genau das beißt uns jetzt hier. Diese schnelle Mustererkennung kommt nämlich
mit dem Preis, dass man über Zufall, wirklichen Zufall, schlecht argumentieren kann.
Unser Gehirn zieht so gern voreilige Schlüsse, weil das eben in der Vergangenheit
den evolutionären Vorteil gesichert hat. Jedes Muster, das wir sehen, wird interpretiert.
Es werden überall Muster gesehen, wo keine sind. Und wenn wir ein Muster sehen,
dann stoßen wir sofort drauf.
Und das ist auch evolutionär sinnvoll, wenn wir uns in einer realistischen Situation
einfach zufälliges Drings erzeugen.
Und es kommt jetzt wirklich darauf an, zu entscheiden, ob da etwas ist,
ob dieser Prozess zufällig ist oder ob irgendwie ein Signal ist,
was wir verwerten können.
Dann wollen wir natürlich dem nachgehen, wenn da ein lesbares Wort herauskommt.
Was würdet ihr eher glauben? Das war
wirklich Zufall, dass da das Wort Verkehrsingenieur ausgewürfelt wurde?
Oder irgendwie war es doch kein Zufall? Es gibt eine andere Erklärung.
Das Programm ist nicht richtig implementiert. Irgendwer spielt uns einen Streich.
Irgendwas ist da im Spiel.
Also wenn ich in dieser Situation wäre, würde ich schließen,
dass die 20 Buchstaben nicht wirklich zufällig ausgewürfelt worden sein können.
Ich gebe nochmal eine andere Betrachtungsweise und da kommen wir zu der Krux
zwischen Mathematik und Psychologie.
Wir haben modelliert, wenn ich das mal so hochtrabend ausdrücken würde,
dass jede Buchstabenkombination gleichwahrscheinlich vorfinden werden und dann
haben wir Mathematik gemacht, aber unser Gehirn würde eher diese Modellierungsannahme über Bord werfen.
Als Glauben, dass es einfach nur in diesem ganz normalen zufälligen Prozess
ein so musterbehaftetes Ereignis eingetreten ist.
Und wie wir hier argumentieren, das ist im Prinzip schon die mathematisch-statistische
Methode des sogenannten Hypothesentests.
Wir haben eine Modellierungsannahme gemacht, sehen Daten, die unserer Hypothese
widersprechen und verwerfen die Hypothese.
Ich formuliere es mal um. Angenommen, ihr seid in der Steinzeit und den ganzen
Tag passiert nichts. Ihr beobachtet, ihr hört und das Rauschen des Windes,
das ist jeden Tag das gleiche und das filtert ihr immer raus.
Und plötzlich verändert sich das Geräusch.
Irgendwie war das Geräusch auf einmal anders. Es könnte sein,
dass es einfach eine zufällige Interferenz irgendwo im Wind war oder es war
eben ein Säbelzahntiger, der irgendwo hinter dem Busch lauert.
Wahrscheinlich war es nur der Wind. Aber ihr habt in dieser Gegend noch nie
einen Säbelzahntiger beobachtet.
Und es ist echt gefährlich, wenn so ein Säbelzahntiger jetzt da hinter diesem Busch ist.
Und so eine drohende Gefahr zu ignorieren, ist vielleicht ein Fehler.
Also reagiert er darauf und zwar sofort.
Und dieser ganze Film, der läuft im Kopf ab, ohne dass man groß darüber nachdenkt.
Es ist eine Sofortverarbeitung, die automatisch Muster erkennt und Prozesse
wie Flucht, Verteidigung und solche Sachen auslöst.
Das spielt jetzt hier mit rein, wenn wir wirklich Zufall analysieren wollen.
Es läuft wohl im Gehirn immer so eine Vorhersage, was wahrscheinlich als nächstes passiert.
Und wenn wir diesen zufälligen Prozess mit den Buchstaben anschauen,
dann ist unsere Erwartung, dass da einfach irgendeine Buchstaben-Suppe rauskommt.
Und jede Abweichung davon muss untersucht werden.
Jede Abweichung davon hat normalerweise einen Grund.
Und wenn sie keinen Grund hat, hat es auch nur geringe Kosten,
mal nachzuschauen und zu prüfen, ob nicht vielleicht doch ein Grund dahinter steckt.
Also die wahrscheinlichste Erklärung ist, dass unsere Modellierung falsch war.
So, jetzt leben wir aber in der modernen Welt. So evolutionäre Mechanismen haben
wir ja schön entkoppelt.
Und in der modernen Welt wollen wir nur Mathematik machen und modellieren.
Und dafür brauchen wir Rationalität.
Und die funktioniert eben nicht so schnell. Aber wir können nicht anders,
als immer zu denken, dass nach ein paar Einsen im Mensch ärgert dich nicht,
doch irgendwann wieder eine Sechs kommen muss.
Und es ist zwar auch richtig, dass irgendwann wieder eine Sechs kommen muss,
Aber es ist eben nicht wahrscheinlicher als bei jedem Wurf zuvor.
Das ist übrigens auch ein Problem, wenn Menschen selbst zufällige Daten erzeugen sollen.
Also wenn man Menschen als Zufallszahlengeneratoren hernehmen soll.
Da könnt ihr mal ein kleines Experiment machen.
Ihr versucht mal, eine Folge von Nullen und Einsen zu erzeugen,
einfach hinzuschreiben, ohne Würfel oder so, sondern ihr habt einen Stift oder
einen Computer und macht eine zufällige Folge von Nullen und Einsen.
Und dann jagt er die durch ein kleines Programm, was ich geschrieben habe,
mal für eine lange Nacht der Wissenschaft, vor längerer Zeit.
Und das Programm, das sagt immer voraus, was ihr als nächstes eingeben werdet.
Und bei so normalen Menschen, die das eine Weile machen und vielleicht schon
ein bisschen gelangweilt sind, kommt das Programm so oft zwischen 60 und 80 Prozent richtig.
Also ihr gebt immer eine zufällige 0 oder 1 ein und das Programm sagt einfach
vorher unter Ausnutzung, was ihr bisher eingegeben habt, was ihr als nächstes eingeben werdet.
Und es ist ein ganz einfaches Python-Programm, ist auf GitHub,
verlinke ich euch und das beweist euch, dass ihr eben nicht sehr gut seid,
darin zu verbergen, was ihr wohl als nächstes vorhabt, wenn ihr versucht,
selbst ein Zufallszahlengenerator zu sein.
Okay, wie das funktioniert, könnt ihr da auch in der Doku nachlesen,
aber das Problem ist eben Muster.
Es sind wieder diese Muster. Wenn ihr eine zufällige Folge von 100 Bits erzeugt,
dann könnt ihr ausrechnen, wie wahrscheinlich es ist, dass da zum Beispiel sechs
hintereinander folgende Einzelnen drin vorkommen.
Und ich habe das mal ausgerechnet, die Wahrscheinlichkeit, wenn ich mich nicht
verrechnet habe, müsste ungefähr 50 Prozent sein.
Das bedeutet, dass ihr, wenn ihr das macht, mit 50-prozentiger Wahrscheinlichkeit
dort sechs hintereinander folgende Einzelnen produzieren müsst.
In über 80 Prozent der Fälle müsstet ihr mindestens fünf hintereinander folgende
Nullen produzieren, in 20 Prozent aber nicht.
Hier beißt euch eure Mustererkennung in die andere Richtung.
Das sieht irgendwie nicht zufällig aus. Eure Mustererkennung schlägt sofort
zu und sagt, hey, Moment mal, jetzt habe ich da schon fünf Einsen gemacht,
jetzt kann ich doch nicht noch eine Eins machen, da muss doch mal wieder eine Null kommen.
Und deswegen, wenn ihr selbst eine zufällige Folge erzeugen wollt,
verhindert eure Mustererkennung, dass ihr das tut, weil es euch verdächtig vorkommen
würde, überkompensiert euer Gehirn und lässt euch was anderes ausgeben.
Also sollte man da besser einen echten Zufallszahlengenerator oder Pseudo-Zufallszahlengenerator
hernehmen und deswegen solltet ihr auch eure Passwörter nicht selbst erstellen
und so weiter und so fort.
Da gibt es ja eben dieses Buch von Daniel Kahnemann, in dem er beschreibt,
wie so zwei konkurrierende Systeme in unserem Gehirn miteinander wechselwirken.
Das System 1, was immer schnell Sachen erkennen will und Jumping to the Conclusion
macht und das System 2, was analytisch rational vorgeht und auf einer ganz anderen Zeitskale arbeitet.
Habe ich, glaube ich, hier im Podcast schon öfter erwähnt.
Können wir also mal zu ein bisschen System 2 kommen. Mit System 2 machen wir
Mathematik, mit System 1 rennen wir davon, wenn Gefahr ist und erkennen Muster, wo keine sind.
Und es muss ja irgendwelche Methoden geben, mit denen man Daten jetzt wirklich
auf Zufälligkeit untersuchen kann.
Und diese Methoden sind natürlich statistisch. Also wir können mit Hilfe von
Mathematik nur so statistische Zufälligkeit untersuchen. Also die Abwesenheit
von Dingen, die man mit Statistik untersuchen kann.
Härte gegen Statistik. Also genau das, was ich am Anfang gesagt habe,
das, was ich modellieren will, ist eine Unvorhersagbarkeit.
Wenn ein Angreifer meine Zufallszahlen nicht vorhersagen kann,
dann ist Schlüsselmaterial, was ich daraus ableite, hoffentlich sicher.
Sicher, wenn der Angreifer keine Methode zur Verfügung hat, vorherzusagen,
was ich tue, dann verhalte ich mich zufällig.
Und damit blende ich diese ganze philosophische Diskussion, was ist Zufälligkeit,
aus und reduziere es auf eine Art statistische Zufälligkeit,
die mithilfe von Statistik definiert ist.
Alles, Statistik ist nutzlos, ist meine Definition von Zufälligkeit,
weil ich davon ausgehe, dass ein Angreifer oder die Sachen, wofür ich die Zufälligkeit
brauche, eben auch Statistik zur Verfügung haben und was Besseres fällt uns,
der Menschheit und denen eben nicht ein.
So, die üblichen Methoden der Statistik sind dann da natürlich auch in Stellung
gebracht worden, gibt es schon seit 100 Jahren.
Also da kann man zum Beispiel so einfache Zählstatistiken einsetzen,
wenn alles zufällig ist, dann sollte in so einem Buchstabenstring jeder Buchstabe
ungefähr gleich oft vorkommen, in einem binären String 0 und 1 ungefähr gleich oft.
Dann auf der nächsten Ebene schaut man sich vielleicht Kombinationen an.
Kommt jede Kombination von aufeinanderfolgenden Paaren 0, 0,
0, 1, 1, 0 und 1, 1 ungefähr gleich oft vor? Was ist mit längeren Folgen?
Was ist mit außergewöhnlichen Folgen, zum Beispiel konsekutiven Einsen?
Also man kann immer, das macht man dann mit den Methoden der Hypothesentests,
man kann immer aus der Annahme, dass wirklich von so einem zufälligen Prozess erzeugt wurde,
ableiten, was für Frequenzen irgendwelche bestimmten Muster haben sollten und
diese dann mit der Realität vergleichen und dann eventuell darauf kommen,
dass das nicht zufällig erzeugt wurde.
Wobei, und das will ich nochmal erwähnen, es da immer sehr subtil auf die Modellierung ankommt.
Wenn ich die Annahme mache, dass ich eine Buchstabenkette der Länge 20 mache
und jeder Buchstabe wird einzeln ausgewürfelt und dann erzeuge ich aus diesen
20 einzeln ausgewürfelten Buchstaben die Zeichenkette,
dann habe ich vor mir 20 Datenpunkte eines gleichen Zufalls.
Wenn ich aber einmal nur eine 20 Zeichen lange Zeichenkette aus einem Gesamtbereich
von allen 20 Zeichen langen Zeichenketten auswähle,
dann ist es schon wieder subtil etwas anderes, dann sehe ich nämlich einen Datenpunkt
von einem zufallerzeugenden Prozess.
Und statistische Methoden sind sehr sensitiv, ob ich etwas sehe.
Denn wenn ich zum Beispiel nur einmal eine Zeichenkette sehe,
die ausgewürfelt wurde und ich sehe 20 Einsen oder ich sehe 20 As.
Dann habe ich eigentlich keine Information gewonnen, während wenn ich 20 Mal unabhängig.
Und 20 Mal kommt das A raus, dann habe ich schon starke Evidenz dagegen,
dass dort wirklich unabhängig jeder Buchstabe die gleiche Chance hatte vorzukommen.
Also das ist der Unterschied zwischen 20 Datenpunkte sehen und einen Datenpunkt
sehen. Aber der Eigenraum wäre nicht der Eigenraum, wenn es nicht eine skurrile
und elegante Methode geben würde.
Und auf die will ich jetzt nochmal eingehen.
Das ist die sogenannte Kolmogorov-Komplexität. Ein sehr interessantes Konzept,
was die Komplexität eines Objekts ausdrückt.
Und mit Objekt meine ich zum Beispiel unsere Zeichenkette oder ein Bild oder
irgendwas anderes. Und diese Komplexität ist definiert als die Länge des kürzesten
Computerprogramms, das eine Beschreibung der Menge ausgibt.
Dabei ist jetzt eine Programmiersprache, sagen wir mal, oder ein Turing-Maschinen-Modell,
wenn man es etwas theoretischer machen will, fixiert und dann hat man wieder
so eine Code-Golf-Aufgabe wie beim letzten Mal,
nur dass jetzt hier die perfekte Golferin antritt und man sucht die Länge des
kürzesten Computerprogramms, was das Objekt erzeugt.
Also wenn man zum Beispiel die Zeichenkette hat, A, A, A, A,
A, A, A, A, A, immer nur A's, dann gibt es ein kürzeres Programm,
was einfach lautet, gib 20 A's aus.
20 ist jetzt eine vielleicht zugeregte Zahl, sagen wir mal 20.000.
Also dann schreibt man ein kurzes Programm, sagen wir mal, schreib 20.000 mal A.
Die Zeichenkette A, B, A, B, A, B, A, B ist etwas komplizierter.
Die lautet, schreib einfach 10.000 mal hintereinander A, B.
Wenn wir jetzt aber wirklich einen zufälligen String der Länge 20.000 hatte,
dann gibt es vielleicht gar keine gute Möglichkeit, diesen String auszugeben,
außer in meinem Programmcode den String abzuspeichern.
Der hat also dann eine hohe Kolmogorov-Komplexität, wenn es kein kurzes Programm
gibt, das ihn ausgibt. Das Konzept ist eng verknüpft mit der Kompression, Datenkompression.
Das stammt aus den Überlegungen über Informationstheorie und Kodierung.
Wenn ich zum Beispiel meine Zeichenkette gut komprimieren kann.
Dann kann ich wieder ein kurzes Programm schreiben. Das kurze Programm würde
bestehen aus dem komprimierten Zeichenkette, die hoffentlich,
wenn die Kompression erfolgreich war, viel kürzer ist, und dem Dekodierprogramm.
Für asymptotisch immer länger werdende Zeichenketten kann man die fixierte Länge
des Dekodierprogramms vernachlässigen und es bleibt nur die Länge der komprimierten Zeichenkette.
Und die Annahme ist, und das kann man auch zeigen, dass eben wirklicher Zufall,
der unabhängig gleichverteilt erzeugt wurde, sich nicht gut komprimieren lässt.
Und daher die Idee, diese Länge des kürzesten Programms als Komplexität zu nehmen.
Und basierend auf diesem Begriff kann man jetzt auch eine Kolmogorov-Zufälligkeit definieren.
Ein String ist zufällig, wenn jedes Programm, das den String ausgibt,
mindestens so lang ist wie der String selbst.
Das ist doch relativ schlau, oder? Es gibt natürlich wieder Probleme mit dieser
Kolmogorov-Zufälligkeit und der Kolmogorov-Komplexität, denn wer jetzt schon
einige Folgen hier über Theoretische Informatik gehört hat, Der oder die würde
vielleicht auf die Idee kommen,
ob man diese Kolmogorov-Komplexität überhaupt berechnen könnte.
Ja, das ist also wieder so ein etwas theoretisch schöner Begriff,
der in der Praxis kaum auszuwerten ist.
Es gibt nämlich eine Reihe von Resultaten, die darüber sprechen,
dass es kein Computerprogramm gibt, welches für mehr als endlich viele Texte
diese Komplexität korrekt ausgibt.
Also ich wiederhole nochmal, wenn man ein Computerprogramm schreibt,
was Kolmogorov-Komplexität berechnen soll,
also was das kürzeste Programm finden soll, was eine gegebene Zeichenkette ausgibt,
aber die gegebene Zeichenkette ist jetzt der Input für mein Programm,
weil mein Programm, was ich jetzt finden will,
das soll ja die Kolmogorov-Komplexität von Zeichenketten ausrechnen.
Das soll also Programme finden, die die Zeichenkette ausgeben,
die ich als Eingabe für mein Programm bekommen habe.
Wie könnte ich jetzt so ein Programm machen? Man könnte versuchen,
einfach jeden Quelltext auszuprobieren.
Also ich kümmere mich jetzt nicht um Effizienz, sondern ich kümmere mich einfach
nur darum, gibt es so ein Programm?
Dann könnte ich auf die Idee kommen, ich probiere einfach mal alle Quelltexte aus.
Also ich will meine Zeichenkette der Länge 20.000 ausgeben und dann probiere
ich einfach alle Programme der Länge 1 aus.
Ich kann ja prüfen, wenn ich so ein Programm habe, ein Programm Quelltext,
ob der ein gültiges Programm ist, also einfach Syntaxprüfung.
Und nehme ich also alle Texte der Länge 1, prüfe die, ob die gültige Programme sind.
Wenn ja, führe ich sie aus und schaue, ob das gewünschte Ergebnis rauskommt.
Danach prüfe ich alle Programme der Länge 2.
Danach prüfe ich alle Programme der Länge 3. Danach prüfe ich alle Programme
der Länge 4 und so weiter.
Irgendwann komme ich zu einem Programm, was den gewünschten String ausgibt,
weil zum Beispiel einfach das Programm, was einfach nur eine Print-Funktion
ist und den gewünschten String abgespeichert hat, Das wird ja irgendwann drankommen
in meiner Enumeration der Programme.
So, warum ist es jetzt keine Möglichkeit, die Komogorov-Komplexität allgemeingültig zu berechnen?
Weil ich nicht weiß, ob diese ganzen Programme, die ich da unterwegs produziere, ob die anhalten.
Bevor ich zu meinem Programm komme, was den gewünschten Output gibt,
komme ich zu einem, was eine Endlosschleife enthält.
Aha, ich habe aber versucht, schon durch Syntaxprüfung erstmal die ungültigen
Programme rauszusortieren.
Jetzt müsste ich also auch noch die Programme raussortieren, die nicht anhalten.
Aber die Programme rauszusortieren, die nicht anhalten, bedeutet ja,
das Halteproblem zu lösen.
Da muss ich ja wieder ein Programm schreiben, was überprüft,
ob der gegebene Quelltext zu einer Endlosschleife führt oder nicht.
Und das geht eben nicht. Und so kann man eben zeigen, ich wiederhole es nochmal,
dass es kein Computerprogramm gibt, was für mehr als endlich viele Texte diese
Kolmogorov-Komplexität korrekt berechnet.
Also ein sehr eleganter Begriff.
Es gibt eben auch interessante Mengen, die uns komplex erscheinen,
aber niedrige Kolmogorov-Komplexität haben.
Aber ich kann da mal kurz die beliebten Fraktale erwähnen, also wie zum Beispiel
die Mandelbrotmenge oder so, die sind dann nicht sehr komplex,
denn die sind ja Plots von relativ einfachen Formeln.
Also man plottert immer den Realteil von irgendeiner Iteration in den komplexen
Zahlen oder solche Dinge und das sind relativ einfache Formeln und haben also
eine niedrige Beschreibungskomplexität in diesem Kolmogorov-Sinne und erscheinen
uns trotzdem auf dem Bild sehr komplex.
Also da kommt man ganz schön in die Philosophie der Komplexität rein.
Aber in dieser Welt der Komogorov-Komplexität sind eben zufällig erzeugte Sachen
komplex, weil sie nicht gut komprimierbar sind.
Ja, haben wir also einen schönen, eleganten Begriff der Zufälligkeit,
den wir nicht auswerten können. So, dann kommen wir nochmal ganz zurück zum Anfang.
Was ist jetzt mit diesem Kassenzettel? Ihr habt eure 30 Sachen gekauft,
Pfand zurückgegeben und der Betrag war genau 100 Euro.
Ist es jetzt Zufall? Natürlich ist es Zufall, dass ein glatter Betrag herauskommt.
Denn man hat zwar einen Plan, was man kaufen will, aber die Preise ändern sich
nach einem unvorhersehbaren Muster. Was man dann genau kauft,
was man genau braucht, ändert sich nach einem unvorhersehbaren Muster.
Also nach unserer Definition von zufällig ist der Betrag auf eurem Kassenzettel
sicherlich zufällig und schwer genau vorhersehbar. Aber trotzdem ist es nicht
so, dass etwas dahinter steckt.
Also aus dieser Beobachtung, dass da ein glatter Betrag herausgekommen ist,
folgt aber jetzt auch nichts.
Es ist einfach eine interessante Beobachtung. Man hat mal Glück gehabt,
etwas Kurioses ist passiert und daraus kann man dann manchmal auch einfach gar nichts weiter lernen.
So, trotzdem finde ich das Phänomen faszinierend und wenn euch das passiert,
macht doch mal ein Foto von dem Kassenzettel und schickt es mir an den Eigenraum
oder postet es auf Social Media und gebt mir irgendwie Bescheid.
So, apropos Social Media.
Wer gerne bis zum Ende hört, kennt das schon.
Folgt gerne dem eigenen Raum auf Mastodon oder Threads und empfehlt uns gerne
weiter und schaltet auch nächstes Mal wieder ein.
Ich hoffe, es hat euch ein bisschen Spaß gemacht. Bis bald und tschüss.