EN 
Українська
Polski
Español
Deutsch
日本語
Italiano
Português (BR)
Français
العربية
Nederlands
中文
한국어
हिन्दी
Türkçe
Tiếng Việt
Русский
Bahasa Indonesia
فارسی
বাংলা
ไทย
Filipino
Kiswahili
اردو
Bahasa Melayu
தமிழ்
עברית
Ελληνικά
ਪੰਜਾਬੀ
አማርኛ
မြန်မာဘာသာ
ខ្មែរ
ქართული
नेपाली
Монгол хэл
Հայերեն
සිංහල
ລາວ
Čeština
Română
Magyar
Български
Svenska
Dansk
Suomi
Norsk
Slovenčina
Hrvatski
Српски
Slovenščina
Lietuvių
Latviešu
Eesti
Íslenska
Shqip
Македонски
Bosanski
Malti🧮 Kolmogorow-Komplexität: Die kürzeste Beschreibung
Komprimieren Sie eine Bitfolge live mit einem echten LZ77-artigen Algorithmus und nutzen Sie die komprimierte Länge als ehrliches, berechenbares Obergrenzen-Proxy für die (nachweislich unberechenbare) Kolmogorow-Komplexität.
Über die Kolmogorow-Komplexität
Die Kolmogorow-Komplexität K(x) einer Zeichenkette x, unabhängig voneinander formalisiert von Ray Solomonoff, Andrei Kolmogorow und Gregory Chaitin, ist die Länge des kürzesten Programms, das auf einer festen universellen Maschine x ausgibt. Eine Zeichenkette wie tausend Wiederholungen von „01" hat niedriges K(x): Ein winziges Programm („drucke 01, 500-mal") erzeugt sie. Eine Zeichenkette, die wie die Ausgabe fairer Münzwürfe aussieht, hat typischerweise ein K(x) nahe ihrer eigenen Länge, da keine kürzere Beschreibung als die Zeichenkette selbst existiert. Entscheidend ist, dass K(x) nachweislich unberechenbar ist — eine Konsequenz, die eng mit dem Halteproblem verwandt ist: Kein Algorithmus kann eine beliebige Zeichenkette entgegennehmen und ihre wahre minimale Programmlänge ausgeben, da ein solcher Algorithmus zur Erkennung nicht haltender Programme kürzer als eine gegebene Schranke verwendet werden könnte.
Da die reale Größe unerreichbar ist, verwendet diese Simulation einen echten, ehrlich gekennzeichneten berechenbaren Ersatz: einen vereinfachten LZ77-Kompressor mit fester Breite, der tatsächlich auf der von Ihnen eingegebenen Bitfolge läuft. Er schiebt ein Fenster rückwärts durch die Zeichenkette, findet an jeder Position die längste zuvor gesehene Übereinstimmung und gibt einen echten Strom aus wörtlichen und Übereinstimmungs-Token aus. Die resultierende Bitanzahl ist eine echte obere Schranke für K(x) — nie der reale Wert und nie nachweislich eng —, aber sie reicht aus, um die zentrale Intuition greifbar zu machen: gemusterte Zeichenketten komprimieren stark, und Zeichenketten, die diesem Kompressor zufällig erscheinen, komprimieren kaum.
Häufig gestellte Fragen
Was genau ist Kolmogorow-Komplexität?
K(x) ist die Länge in Bits des kürzesten Programms, das auf einem festen universellen Computer (einer festen Referenzmaschine) ausgeführt die Zeichenkette x ausgibt und anhält. Es ist eine Eigenschaft der Zeichenkette selbst, nicht eines bestimmten Kompressors — kann jedoch nur relativ zur Wahl einer Maschine definiert werden, und verschiedene Maschinen ändern K(x) höchstens um eine additive Konstante (der Invarianzsatz).
Warum ist die Kolmogorow-Komplexität unberechenbar?
Könnte ein Algorithmus K(x) für jedes x berechnen, könnte man damit für jedes n die kürzeste Zeichenkette finden, deren Komplexität nachweislich n übersteigt — doch die Beschreibung „der kürzesten Zeichenkette mit einer Komplexität größer als n" ist selbst eine kurze Beschreibung einer angeblich nicht komprimierbaren Zeichenkette, ein als Berry-Paradoxon bekannter, rigoros gemachter Widerspruch. Formal gesehen würde die Berechnung von K(x) es erlauben, das Halteproblem zu lösen, was unmöglich ist. Dies ist ein echtes, grundlegendes Unentscheidbarkeitsergebnis, keine technische Einschränkung, die schnellere Hardware beheben könnte.
Wenn K(x) unberechenbar ist, was zeigt diese Simulation dann tatsächlich?
Sie zeigt ein echtes, berechenbares Proxy: die Länge der Ausgabe eines tatsächlichen Kompressionsalgorithmus (ein vereinfachtes LZ77), der gerade jetzt in Ihrem Browser auf Ihrer Zeichenkette läuft. Eine kurze komprimierte Länge ist ein solider Beleg für geringe Komplexität — ein Programm, das die komprimierten Token rekonstruiert, ist selbst eine gültige kurze Beschreibung. Eine lange komprimierte Länge ist ein viel schwächerer Beleg: Sie zeigt nur, dass dieser bestimmte Kompressor keine ausnutzbare Struktur gefunden hat, nicht dass nirgendwo eine kürzere Beschreibung existiert.
Warum komprimiert die „strukturierte" Thue-Morse-Vorgabe nicht so stark wie die repetitive Vorgabe?
Die Thue-Morse-Folge (Bit n = Parität der Anzahl der Einsen in der Binärdarstellung von n) hat eine winzige rekursive Erzeugungsregel, sodass ihre wahre Kolmogorow-Komplexität sehr niedrig ist — aber sie ist absichtlich überlappungsfrei konstruiert und vermeidet lange wiederholte Läufe. Ein Sliding-Window-LZ77-Kompressor findet meist nur wörtliche Teilstrings, sodass er diese Struktur nur teilweise ausnutzt. Dies ist eine ehrliche Einschränkung des Proxys: Geringe Komplexität garantiert nicht, dass ein bestimmter Kompressor sie findet.
Warum komprimiert die Zufalls-Vorgabe kaum?
Jedes Bit wird unabhängig mit Math.random() gezogen, sodass im Durchschnitt keine wiederholte Teilzeichenkette existiert, die das Sliding Window über das durch Zufall in einem kurzen Fenster Erwartete hinaus ausnutzen könnte. Die LZ77-Ausgabelänge bleibt nahe der Originallänge, genau das Verhalten, das man von einer Kolmogorow-zufälligen (oder algorithmisch zufälligen) Zeichenkette erwartet: Es existiert keine wesentlich kürzere Beschreibung.
Ist Math.random() wirklich zufällig?
Nein — es ist ein deterministischer Pseudozufallszahlengenerator, der intern vom Browser initialisiert wird. Für die Zwecke dieser Demonstration verhält er sich statistisch wie unabhängige Münzwürfe und ist ein vernünftiger praktischer Ersatz; eine philosophisch „wirklich zufällige" Quelle würde einen physikalischen Prozess wie radioaktiven Zerfall oder Quantenmessrauschen benötigen.
Wie wird die komprimierte Länge in Bits hier tatsächlich berechnet?
Der Encoder gibt eine Folge von Token aus: entweder ein wörtliches Bit oder eine (Offset, Länge)-Rückreferenz auf einen früheren übereinstimmenden Lauf (minimale Übereinstimmungslänge 3, maximales Fenster 48 Bit, maximale Übereinstimmung 32 Bit). Jedes Token kostet ein Flag-Bit plus entweder ein wörtliches Bit oder eine feste Anzahl von Bits für die Offset- und Längenfelder, dimensioniert nach Fenster- und Übereinstimmungsgrenzen. Die Summe dieser Kosten ergibt eine echte, ehrlich berechnete kodierte Bitlänge — eine vereinfachte Verwandte der LZ77-Stufe innerhalb von DEFLATE (ZIP, gzip, PNG).
Kommt ein besserer Kompressor immer näher an das wahre K(x) heran?
Ein besserer, klügerer Kompressor (arithmetische Codierung, größere Fenster, Kontextmodellierung oder eine vollständige Suche über kurze Programme) findet im Allgemeinen mehr Struktur und erzeugt engere obere Schranken. Aber keine endliche Familie von Kompressoren kann nachweislich K(x) für jede Eingabe exakt erreichen, da dies die unberechenbare Funktion selbst berechnen würde. Jeder reale Kompressor, wie gut auch immer, liefert nur eine weitere obere Schranke.
Welche Beziehung besteht zwischen Kolmogorow-Komplexität und Shannon-Entropie?
Die Shannon-Entropie misst den durchschnittlichen Informationsgehalt von Symbolen aus einer bekannten Wahrscheinlichkeitsverteilung — sie ist eine statistische Größe auf Verteilungsebene. Die Kolmogorow-Komplexität misst den Informationsgehalt einer einzelnen, individuellen Zeichenkette, ohne Bezug auf irgendeine Verteilung. Für lange, unabhängig und identisch verteilt aus einer Quelle erzeugte Zeichenketten konvergiert die erwartete Kolmogorow-Komplexität pro Symbol gegen die Entropierate der Quelle, was die beiden Ideen verbindet, ohne sie identisch zu machen.
Komprimieren Sie eine Bitfolge live mit einem echten LZ77-artigen Algorithmus und nutzen Sie die komprimierte Länge als ehrliches, berechenbares Obergrenzen-Proxy für die nachweislich unberechenbare Kolmogorow-Komplexität.
2D · HTML5 Canvas 2D · 60 FPS-Ziel · läuft vollständig clientseitig, keine Installation nötig