Kolmogorov-Komplexität - Kolmogorov complexity

Dieses Bild veranschaulicht einen Teil des Fraktals der Mandelbrot-Menge . Allein das Speichern der 24-Bit-Farbe jedes Pixels in diesem Bild würde 23 Millionen Bytes erfordern, aber ein kleines Computerprogramm kann diese 23 MB reproduzieren, indem es die Definition der Mandelbrot-Menge und die Koordinaten der Ecken des Bildes verwendet. Somit beträgt die Kolmogorov-Komplexität der Rohdatei, die diese Bitmap codiert, in jedem pragmatischen Berechnungsmodell viel weniger als 23 MB . Die universelle Bildkomprimierung von PNG reduziert es nur auf 1,6 MB, kleiner als die Rohdaten, aber viel größer als die Kolmogorov-Komplexität.

In der algorithmischen Informationstheorie (einem Teilgebiet der Informatik und Mathematik ) ist die Kolmogorov-Komplexität eines Objekts, beispielsweise eines Textstücks, die Länge eines kürzesten Computerprogramms (in einer vorgegebenen Programmiersprache ), das das Objekt als Ausgabe erzeugt. Sie ist ein Maß für die Rechenressourcen , die zum Spezifizieren des Objekts erforderlich sind, und wird auch als algorithmische Komplexität , Solomonoff-Kolmogorov-Chaitin-Komplexität , Programmgrößenkomplexität , deskriptive Komplexität oder algorithmische Entropie bezeichnet . Es ist nach Andrey Kolmogorov benannt , der 1963 zum ersten Mal zu diesem Thema veröffentlichte.

Der Begriff der Kolmogorov-Komplexität kann verwendet werden, um Unmöglichkeitsergebnisse ähnlich dem Diagonalargument von Cantor , dem Unvollständigkeitssatz von Gödel und dem Halteproblem von Turing anzugeben und zu beweisen . Insbesondere kann kein Programm P, das eine untere Schranke für die Kolmogorov-Komplexität jedes Textes berechnet, einen Wert zurückgeben, der wesentlich größer ist als die eigene Länge von P (siehe Abschnitt § Chaitins Unvollständigkeitssatz ); daher kann kein einzelnes Programm die exakte Kolmogorov-Komplexität für unendlich viele Texte berechnen.

Definition

Betrachten Sie die folgenden zwei Zeichenfolgen mit 32 Kleinbuchstaben und Ziffern:

abababababababababababababababab , und
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

Der erste String hat eine kurze englischsprachige Beschreibung, nämlich " write ab 16 times", die aus 17 Zeichen besteht. Der zweite hat keine offensichtliche einfache Beschreibung (unter Verwendung des gleichen Zeichensatzes), außer dass man den String selbst aufschreibt, dh " write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7", der 38 Zeichen hat. Daher kann man sagen, dass der Vorgang des Schreibens des ersten Strings "weniger Komplexität" hat als das Schreiben des zweiten.

Formaler ausgedrückt ist die Komplexität eines Strings die Länge der kürzesten möglichen Beschreibung des Strings in einer festen universellen Beschreibungssprache (die Empfindlichkeit der Komplexität in Bezug auf die Wahl der Beschreibungssprache wird unten erörtert). Es kann gezeigt werden, dass die Kolmogorov-Komplexität eines Strings nicht mehr als einige Bytes größer sein kann als die Länge des Strings selbst. Strings wie das obige abab- Beispiel, deren Kolmogorov-Komplexität im Verhältnis zur String-Größe klein ist, werden nicht als komplex betrachtet.

Die Kolmogorov-Komplexität kann für jedes mathematische Objekt definiert werden, aber der Einfachheit halber ist der Umfang dieses Artikels auf Strings beschränkt. Wir müssen zunächst eine Beschreibungssprache für Strings angeben. Eine solche Beschreibungssprache kann auf einer beliebigen Computerprogrammiersprache basieren, wie beispielsweise Lisp , Pascal oder Java . Wenn P ein Programm ist, das einen String x ausgibt , dann ist P eine Beschreibung von x . Die Länge der Beschreibung ist einfach die Länge von P als Zeichenkette, multipliziert mit der Anzahl der Bits in einem Zeichen (zB 7 für ASCII ).

Alternativ könnten wir eine Codierung für Turing-Maschinen wählen , wobei eine Codierung eine Funktion ist, die jeder Turing-Maschine M eine Bitfolge < M > zuordnet . Wenn M eine Turing-Maschine ist, die bei Eingabe von w String x ausgibt , dann ist der verkettete String < M > w eine Beschreibung von x . Für die theoretische Analyse eignet sich dieser Ansatz eher zum Konstruieren detaillierter formaler Beweise und wird in der Forschungsliteratur im Allgemeinen bevorzugt. In diesem Artikel wird ein informeller Ansatz diskutiert.

Jeder String s hat mindestens eine Beschreibung. Zum Beispiel wird die zweite obige Zeichenfolge vom Programm ausgegeben:

function GenerateString2()
    return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

wohingegen der erste String durch den (viel kürzeren) Pseudocode ausgegeben wird:

function GenerateString1()
    return "ab" × 16

Wenn eine Beschreibung d ( s ) eines Strings s von minimaler Länge ist (dh mit den wenigsten Bits), heißt sie minimale Beschreibung von s , und die Länge von d ( s ) (dh die Anzahl der Bits im minimalen Beschreibung) ist die Kolmogorov-Komplexität von s , geschrieben K ( s ). Symbolisch,

K ( s ) = | d ( s )|.

Die Länge der kürzesten Beschreibung hängt von der Wahl der Beschreibungssprache ab; aber die Auswirkung des Sprachwechsels ist begrenzt (ein Ergebnis, das als Invarianzsatz bezeichnet wird ).

Invarianzsatz

Informelle Behandlung

Es gibt einige Beschreibungssprachen, die im folgenden Sinne optimal sind: Bei einer beliebigen Beschreibung eines Objekts in einer Beschreibungssprache kann diese Beschreibung mit einem konstanten Overhead in der optimalen Beschreibungssprache verwendet werden. Die Konstante hängt nur von den beteiligten Sprachen ab, nicht von der Beschreibung des Objekts oder des zu beschreibenden Objekts.

Hier ist ein Beispiel für eine optimale Beschreibungssprache. Eine Beschreibung besteht aus zwei Teilen:

  • Der erste Teil beschreibt eine andere Beschreibungssprache.
  • Der zweite Teil ist eine Beschreibung des Objekts in dieser Sprache.

Technisch ausgedrückt ist der erste Teil einer Beschreibung ein Computerprogramm (genauer: ein Compiler für die Sprache des Objekts, geschrieben in der Beschreibungssprache), wobei der zweite Teil die Eingabe in das Computerprogramm ist, das das Objekt als Ausgabe erzeugt.

Es folgt der Invarianzsatz: Bei einer gegebenen Beschreibungssprache L ist die optimale Beschreibungssprache mindestens so effizient wie L , mit einem gewissen konstanten Overhead.

Beweis: Jede Beschreibung D in L kann in eine Beschreibung in der optimalen Sprache umgewandelt werden, indem zuerst L als Computerprogramm P beschrieben wird (Teil 1) und dann die ursprüngliche Beschreibung D als Eingabe in dieses Programm verwendet wird (Teil 2). Die Gesamtlänge dieser neuen Beschreibung D′ beträgt (ungefähr):

| D′ | = | P | + | D |

Die Länge von P ist eine Konstante, die nicht von D abhängt . Es entsteht also höchstens ein konstanter Overhead, unabhängig vom beschriebenen Objekt. Daher ist die optimale Sprache bis zu dieser additiven Konstante universell .

Eine formellere Behandlung

Satz : Wenn K 1 und K 2 die Komplexitätsfunktionen relativ zu den Turing- Vollbeschreibungssprachen L 1 und L 2 sind , dann gibt es eine Konstante c  – die nur von den gewählten Sprachen L 1 und L 2 abhängt – so dass

s . - cK 1 ( s ) - K 2 ( s ) ≤ c .

Beweis : Aus Symmetriegründen genügt es zu beweisen, dass es eine Konstante c gibt, so dass für alle Strings s

K 1 ( s ) K 2 ( s ) + c .

Angenommen, es gibt ein Programm in der Sprache L 1 , das als Interpreter für L 2 fungiert :

function InterpretLanguage(string p)

wobei p ein Programm in L 2 ist . Der Interpreter zeichnet sich durch folgende Eigenschaft aus:

Das Ausführen InterpretLanguageauf Eingabe p gibt das Ergebnis von Ausführen von p zurück .

Wenn also P ein Programm in L 2 ist, das eine minimale Beschreibung von s ist , dann gibt InterpretLanguage( P ) die Zeichenkette s zurück . Die Länge dieser Beschreibung von s ist die Summe von

  1. Die Länge des Programms InterpretLanguage, die wir als Konstante c annehmen können .
  2. Die Länge von P, die per Definition K 2 ( s ) ist.

Dies beweist die gewünschte obere Schranke.

Geschichte und Kontext

Algorithmische Informationstheorie ist das Gebiet der Informatik, das die Kolmogorov-Komplexität und andere Komplexitätsmaße an Strings (oder anderen Datenstrukturen ) untersucht.

Das Konzept und die Theorie der Kolmogorov-Komplexität basieren auf einem entscheidenden Theorem, das zuerst von Ray Solomonoff entdeckt und 1960 veröffentlicht und in "A Preliminary Report on a General Theory of Inductive Inference" als Teil seiner Erfindung der algorithmischen Wahrscheinlichkeit beschrieben wurde . Eine ausführlichere Beschreibung gab er in seinen 1964 erschienenen Veröffentlichungen "A Formal Theory of Inductive Inference", Teil 1 und Teil 2 in Information and Control .

Andrey Kolmogorov veröffentlichte dieses Theorem später unabhängig in Problems Inform. Übertragung 1965. Gregory Chaitin präsentiert diesen Satz auch in J. ACM  – Chaitins Aufsatz wurde im Oktober 1966 eingereicht und im Dezember 1968 überarbeitet und zitiert sowohl Solomonoffs als auch Kolmogorovs Aufsätze.

Das Theorem besagt, dass es unter Algorithmen, die Strings aus ihren Beschreibungen (Codes) decodieren, einen optimalen gibt. Dieser Algorithmus lässt für alle Strings Codes zu, die so kurz sind, wie es jeder andere Algorithmus erlaubt, bis zu einer additiven Konstante, die von den Algorithmen, aber nicht von den Strings selbst abhängt. Solomonoff verwendet diesen Algorithmus und die Codelängen, die er erlaubt, um eine "universelle Wahrscheinlichkeit" einer Zeichenkette zu definieren, auf der induktive Inferenz der nachfolgenden Ziffern der Zeichenkette basieren kann. Kolmogorov benutzte diesen Satz, um mehrere Funktionen von Strings zu definieren, einschließlich Komplexität, Zufälligkeit und Information.

Als Kolmogorov auf Solomonoffs Arbeit aufmerksam wurde, erkannte er Solomonoffs Priorität an. Mehrere Jahre lang war Solomonoffs Werk in der Sowjetunion besser bekannt als in der westlichen Welt. Der allgemeine Konsens in der wissenschaftlichen Gemeinschaft war jedoch, diese Art von Komplexität mit Kolmogorov zu assoziieren, der sich mit der Zufälligkeit einer Folge beschäftigte, während die Algorithmische Wahrscheinlichkeit mit Solomonoff in Verbindung gebracht wurde, der sich auf die Vorhersage mit seiner Erfindung der universellen A-priori-Wahrscheinlichkeitsverteilung konzentrierte . Der breitere Bereich, der die Beschreibungskomplexität und -wahrscheinlichkeit umfasst, wird oft als Kolmogorov-Komplexität bezeichnet. Der Informatiker Ming Li hält dies für ein Beispiel für den Matthew-Effekt : „… jedem, der hat, wird mehr gegeben…“

Es gibt mehrere andere Varianten der Kolmogorov-Komplexität oder algorithmischen Informationen. Das am weitesten verbreitete basiert auf selbstabgrenzenden Programmen und geht hauptsächlich auf Leonid Levin (1974) zurück.

Ein axiomatischer Ansatz zur Kolmogorov-Komplexität basierend auf Blum-Axiomen (Blum 1967) wurde von Mark Burgin in der von Andrey Kolmogorov zur Veröffentlichung vorgelegten Arbeit eingeführt.

Grundlegende Ergebnisse

In der folgenden Diskussion sei K ( s ) die Komplexität des Strings s .

Es ist nicht schwer zu erkennen, dass die minimale Beschreibung eines Strings nicht zu viel größer sein kann als der String selbst – das Programm GenerateString2darüber, das s ausgibt, ist um einen festen Betrag größer als s .

Satz : Es gibt eine Konstante c mit

s . K ( s ) | s | + c .

Unberechenbarkeit der Kolmogorov-Komplexität

Ein naiver Versuch eines Programms zur Berechnung von K

Auf den ersten Blick mag es trivial erscheinen, ein Programm zu schreiben, das K ( s ) für beliebige s berechnen kann , wie zum Beispiel das folgende:

function KolmogorovComplexity(string s)
    for i = 1 to infinity:
        for each string p of length exactly i
            if isValidProgram(p) and evaluate(p) == s
                return i

Dieses Programm durchläuft alle möglichen Programme (indem es durch alle möglichen Strings iteriert und nur diejenigen berücksichtigt, die gültige Programme sind), beginnend mit dem kürzesten. Jedes Programm wird ausgeführt, um das von diesem Programm erzeugte Ergebnis zu finden, indem es mit der Eingabe s verglichen wird . Wenn das Ergebnis übereinstimmt, wird die Länge des Programms zurückgegeben.

Dies wird jedoch nicht funktionieren , weil einige der Programme p beenden getestet werden nicht, zum Beispiel , wenn sie Endlosschleifen enthalten. Es gibt keine Möglichkeit, all diese Programme zu umgehen, indem man sie vor der Ausführung auf irgendeine Weise testet, da das Halteproblem nicht berechenbar ist .

Außerdem kann überhaupt kein Programm die Funktion K berechnen , sei sie noch so ausgefeilt. Dies wird im Folgenden bewiesen.

Formaler Beweis der Unberechenbarkeit von K

Satz : Es existieren Ketten beliebiger Kolmogorov-Komplexität. Formal: für jedes n ∈ ℕ gibt es einen String s mit K ( s ) n .

Beweis: Sonst könnten alle der unendlich vielen möglichen endlichen Strings von den endlich vielen Programmen mit einer Komplexität unter n Bit erzeugt werden.

Satz : K ist keine berechenbare Funktion . Mit anderen Worten, es gibt kein Programm, das irgendeinen String s als Eingabe nimmt und als Ausgabe die ganze Zahl K ( s ) erzeugt .

Der folgende indirekte Beweis verwendet eine einfache Pascal- ähnliche Sprache, um Programme zu bezeichnen; aus Gründen der Einfachheit des Beweises nehmen Sie an, dass seine Beschreibung (dh ein Interpreter ) eine Länge von hat1 400 000 Bit. Angenommen für Widerspruch gibt es ein Programm

function KolmogorovComplexity(string s)

die als Eingabe eine Zeichenfolge s nimmt und K ( s ) zurückgibt . Alle Programme sind von endlicher Länge, also nehmen Sie zur Vereinfachung des Beweises an, dass es7 000 000 000 Bit. Betrachten Sie nun das folgende Programm der Länge1288 Bit:

function GenerateComplexString()
    for i = 1 to infinity:
        for each string s of length exactly i
            if KolmogorovComplexity(s) ≥ 8000000000
                return s

Unter Verwendung KolmogorovComplexityals ein Unterprogramm, versucht das Programm jede Zeichenfolge, mit dem kürzesten beginnen, bis sie einen String mit Kolmogorov Komplexität zumindest zurück8 000 000 000 Bit, dh eine Zeichenfolge, die von keinem Programm kürzer als erzeugt werden kann8 000 000 000 Bit. Die Gesamtlänge des obigen Programms, das s erzeugt hat, beträgt jedoch nur7 001 401 288 Bit, was ein Widerspruch ist. (Wenn der Code von KolmogorovComplexitykürzer ist, bleibt der Widerspruch bestehen. Wenn er länger ist, kann die in verwendete Konstante GenerateComplexStringimmer entsprechend geändert werden.)

Der obige Nachweis verwendet einen Widerspruch ähnlich jener des Berry paradox : „ 1 Die 2 kleinste 3 positiven 4 ganze Zahl 5 , dass 6 nicht 7 seine 8 definierten 9 in 10 weniger 11 als 12 zwanzig 13 Englisch 14 Worte“. Es ist auch möglich , der nicht-Berechenbarkeit zu zeigen K durch Reduktion aus der nicht-Berechenbarkeit des Halteproblem H , da K und H sind Turing-äquivalent .

Es gibt eine Folgerung, die in der Programmiersprachen-Community humorvoll " Full-Employment-Theorem " genannt wird, die besagt, dass es keinen perfekten Compiler zur Größenoptimierung gibt.

Kettenregel für Kolmogorov-Komplexität

Die Kettenregel für die Kolmogorov-Komplexität besagt, dass

K ( X , Y ) K ( X ) + K ( Y | X ) + O (log( K ( X , Y ))).

Darin heißt es , dass das kürzeste Programm , das wiedergibt X und Y ist nicht mehr als eine logarithmische Term größer als ein Programm zur Wiedergabe X und ein Programm zur Wiedergabe Y gegeben X . Mit dieser Aussage kann man ein Analogon der gegenseitigen Information für die Kolmogorov-Komplexität definieren .

Kompression

Es ist einfach, obere Grenzen für K ( s ) zu berechnen – komprimieren Sie einfach den String s mit einer Methode, implementieren Sie den entsprechenden Dekomprimierer in der gewählten Sprache, verketten Sie den Dekomprimierer mit dem komprimierten String und messen Sie die Länge des resultierenden Strings – konkret: die Größe eines selbstextrahierenden Archivs in der angegebenen Sprache.

Ein String s ist um eine Zahl c komprimierbar, wenn er eine Beschreibung hat, deren Länge | . nicht überschreitet s | − c Bits. Dies ist äquivalent zu der Aussage, dass K ( s ) ≤ | s | − c . Andernfalls ist s durch c inkompressibel . Ein um 1 inkompressibler String heißt einfach inkompressibel  – nach dem Schubladenprinzip , das gilt, weil jeder komprimierte String nur auf einen unkomprimierten String abbildet, müssen inkompressible Strings existieren, da es 2 n Bitstrings der Länge n gibt , aber nur 2 n − 1 kürzere Strings, dh Strings mit einer Länge von weniger als n , (dh mit Länge 0, 1, ..., n − 1).

Aus dem gleichen Grund sind die meisten Strings komplex in dem Sinne, dass sie nicht signifikant komprimiert werden können – ihr K ( s ) ist nicht viel kleiner als | s |, die Länge von s in Bit. Um dies genau zu machen, legen Sie einen Wert von n fest . Es gibt 2 n Bitstrings der Länge n . Die gleichmäßige Wahrscheinlichkeitsverteilung auf dem Raum dieser Bitstrings weist jedem String der Länge n genau das gleiche Gewicht 2 n zu .

Satz : Bei der gleichmäßigen Wahrscheinlichkeitsverteilung auf dem Raum von Bitfolgen der Länge n beträgt die Wahrscheinlichkeit, dass eine Zeichenfolge durch c inkompressibel ist, mindestens 1 − 2 c +1 + 2 n .

Um den Satz zu beweisen, beachte, dass die Anzahl der Längenbeschreibungen, die nc nicht überschreiten , durch die geometrische Reihe gegeben ist:

1 + 2 + 2 2 + … + 2 nc = 2 nc +1 − 1.

Es bleiben mindestens

2 n − 2 nc +1 + 1

Bitstrings der Länge n , die mit c inkompressibel sind . Um die Wahrscheinlichkeit zu bestimmen, dividiere durch 2 n .

Unvollständigkeitssatz von Chaitin

Kolmogorov Komplexität K ( s ) und zwei berechenbare untere Schranke Funktionen prog1(s), prog2(s). Die horizontale Achse ( logarithmische Skala ) zählt alle Strings s nach Länge geordnet auf; die vertikale Achse ( lineare Skala ) misst die Kolmogorov-Komplexität in Bits . Die meisten Strings sind inkompressibel, dh ihre Kolmogorov-Komplexität übersteigt ihre Länge um einen konstanten Betrag. Im Bild sind 9 komprimierbare Saiten zu sehen, die als fast vertikale Schrägen erscheinen. Aufgrund des Unvollständigkeitssatzes von Chaitin (1974) kann die Ausgabe eines Programms, das eine untere Grenze der Kolmogorov-Komplexität berechnet, eine feste Grenze nicht überschreiten, die von der Eingabezeichenfolge s unabhängig ist .

Nach dem obigen Theorem ( § Kompression ) sind die meisten Strings komplex in dem Sinne, dass sie nicht signifikant "komprimiert" beschrieben werden können. Es stellt sich jedoch heraus, dass die Tatsache, dass eine bestimmte Zeichenfolge komplex ist, nicht formal bewiesen werden kann, wenn die Komplexität der Zeichenfolge einen bestimmten Schwellenwert überschreitet. Die genaue Formalisierung ist wie folgt. Legen Sie zunächst ein bestimmtes axiomatisches System S für die natürlichen Zahlen fest . Das axiomatische System muss stark genug sein, damit man zu bestimmten Aussagen A über die Komplexität von Strings eine Formel F A in S assoziieren kann . Diese Assoziation muss die folgende Eigenschaft haben:

Wenn F A aus den Axiomen von S beweisbar ist , dann muss die entsprechende Aussage A wahr sein. Diese "Formalisierung" kann anhand einer Gödel-Nummerierung erreicht werden .

Satz : Es existiert eine Konstante L (die nur von S und der Wahl der Beschreibungssprache abhängt ), so dass es keinen String s gibt, für den die Aussage

K ( s ) ≥ L       (wie in S formalisiert )

kann innerhalb von S nachgewiesen werden .


Beweisidee : Der Beweis dieses Ergebnisses basiert auf einer selbstreferenziellen Konstruktion, die im Berry-Paradoxon verwendet wird . Wir erhalten zunächst ein Programm, das die Beweise innerhalb von S aufzählt, und wir spezifizieren eine Prozedur P, die als Eingabe eine ganze Zahl L nimmt und die Zeichenketten x ausgibt, die innerhalb von Beweisen innerhalb von S der Aussage K ( x ) L liegen . Indem L dann größer als die Länge dieser Prozedur P gesetzt wird , haben wir, dass die erforderliche Länge eines Programms zum Drucken von x wie in K ( x ) L als mindestens L angegeben, dann kleiner als der Betrag L ist, da die Zeichenfolge x wurde nach dem Verfahren P gedruckt . Dies ist ein Widerspruch. Somit ist es dem Beweissystem S nicht möglich , K ( x ) ≥ L für L beliebig groß, insbesondere für L größer als die Länge der Prozedur P , (die endlich ist) zu beweisen .

Beweis :

Wir können eine effektive Aufzählung aller formalen Beweise in S durch ein Verfahren finden

function NthProof(int n)

die als Eingabe n nimmt und einen Beweis ausgibt. Diese Funktion zählt alle Beweise auf. Einige davon sind Beweise für Formeln, um die wir uns hier nicht kümmern, da jeder mögliche Beweis in der Sprache von S für einige n erbracht wird . Einige davon sind Komplexitätsformeln der Form K ( sn, wobei s und n Konstanten in der Sprache von S sind . Es gibt ein Verfahren

function NthProofProvesComplexityFormula(int n)

die bestimmt, ob der n- te Beweis tatsächlich eine Komplexitätsformel K ( sL beweist . Die Strings s und die ganze Zahl L wiederum sind durch folgende Prozedur berechenbar:

function StringNthProof(int n)
function ComplexityLowerBoundNthProof(int n)

Betrachten Sie das folgende Verfahren:

function GenerateProvablyComplexString(int n)
    for i = 1 to infinity:
        if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
            return StringNthProof(i)

Gegeben an n versucht dieses Verfahren jeden Beweis, bis es eine Zeichenkette und einen Beweis im formalen System S der Formel K ( sL für irgendein L  ≥  n findet ; wenn es keinen solchen Beweis gibt, wird es ewig durchlaufen.

Betrachten Sie schließlich das Programm, das aus all diesen Prozedurdefinitionen und einem Hauptaufruf besteht:

GenerateProvablyComplexString(n0)

wobei die Konstante n 0 später bestimmt wird. Die Gesamtprogrammlänge kann als U +log 2 ( n 0 ) ausgedrückt werden , wobei U eine Konstante ist und log 2 ( n 0 ) die Länge des ganzzahligen Wertes n 0 darstellt , unter der vernünftigen Annahme, dass er in Binärziffern kodiert ist . Wir wählen n 0 größer als die Programmlänge, d. h. so, dass n 0 > U + log 2 ( n 0 ) ist. Dies gilt eindeutig für n 0 ausreichend groß, da die linke Seite in n 0 linear wächst, während die rechte Seite in n 0 bis zur festen Konstanten U logarithmisch wächst .

Dann kann in S kein Beweis der Form " K ( s )≥ L " mit Ln 0 erbracht werden , wie man an einem indirekten Argument sieht : Wenn ein Wert ≥ n 0 zurückgegeben werden könnte , dann würde die Schleife im Inneren schließlich enden , und diese Prozedur würde einen String s zurückgeben, so dass ComplexityLowerBoundNthProof(i)GenerateProvablyComplexString

K ( s )
n 0           durch Bau von GenerateProvablyComplexString
> U +log 2 ( n 0 ) durch die Wahl von n 0
K ( s ) da s vom Programm mit dieser Länge beschrieben wurde

Dies ist ein Widerspruch, QED

Als Konsequenz muss das obige Programm mit dem gewählten Wert von n 0 eine ewige Schleife durchlaufen.

Ähnliche Ideen werden verwendet, um die Eigenschaften der Chaitin-Konstanten zu beweisen .

Mindestnachrichtenlänge

Das Prinzip der minimalen Nachrichtenlänge der statistischen und induktiven Inferenz und des maschinellen Lernens wurde 1968 von CS Wallace und DM Boulton entwickelt. MML ist Bayesian (dh es beinhaltet vorherige Überzeugungen) und informationstheoretisch. Es hat die wünschenswerten Eigenschaften der statistischen Invarianz (dh die Inferenztransformationen mit einer Neuparametrierung, z. dh das MML-Modell wird so schnell wie möglich zu jedem echten zugrunde liegenden Modell konvergieren). CS Wallace und DL Dowe (1999) zeigten eine formale Verbindung zwischen MML und algorithmischer Informationstheorie (oder Kolmogorov-Komplexität).

Kolmogorov Zufälligkeit

Kolmogorov-Zufälligkeit definiert eine Zeichenfolge (normalerweise aus Bits ) genau dann als zufällig, wenn jedes Computerprogramm , das diese Zeichenfolge erzeugen kann, mindestens so lang ist wie die Zeichenfolge selbst. Um dies genau zu machen, muss ein universeller Computer (oder universelle Turingmaschine ) angegeben werden, so dass "Programm" ein Programm für diese universelle Maschine bedeutet. Ein zufälliger String in diesem Sinne ist "inkompressibel", da es unmöglich ist, den String in ein Programm zu "komprimieren", das kürzer ist als der String selbst. Für jeden Universalcomputer gibt es mindestens einen algorithmisch zufälligen String jeder Länge. Ob eine bestimmte Zeichenfolge jedoch zufällig ist, hängt vom ausgewählten Universalcomputer ab. Dies liegt daran, dass ein universeller Computer eine bestimmte Zeichenfolge in sich selbst hartcodiert haben kann und ein auf diesem universellen Computer ausgeführtes Programm dann einfach mit einer kurzen Bitfolge (dh viel kürzer als die Zeichenfolge selbst) auf diese hartcodierte Zeichenfolge verweisen kann. .

Diese Definition kann erweitert werden, um einen Zufallsbegriff für unendliche Folgen aus einem endlichen Alphabet zu definieren. Diese algorithmisch zufälligen Folgen können auf drei äquivalente Arten definiert werden. Ein Weg verwendet ein wirksames Analogon der Maßtheorie ; ein anderer verwendet wirksame Martingale . Der dritte Weg definiert eine unendliche Folge als zufällig, wenn die präfixfreie Kolmogorov-Komplexität ihrer Anfangssegmente schnell genug wächst — es muss eine Konstante c geben, so dass die Komplexität eines Anfangssegments der Länge n immer mindestens nc beträgt . Diese Definition wird im Gegensatz zur Definition der Zufälligkeit für einen endlichen String nicht davon beeinflusst, welche universelle Maschine verwendet wird, um die präfixfreie Kolmogorov-Komplexität zu definieren.

Beziehung zur Entropie

Für dynamische Systeme sind Entropierate und algorithmische Komplexität der Trajektorien durch einen Satz von Brudno verbunden, dass die Gleichheit für fast alle gilt .

Es kann gezeigt werden, dass für die Ausgabe von Markov-Informationsquellen die Kolmogorov-Komplexität mit der Entropie der Informationsquelle zusammenhängt. Genauer gesagt konvergiert die Kolmogorov-Komplexität der Ausgabe einer Markov-Informationsquelle, normiert durch die Länge der Ausgabe, fast sicher (wenn die Länge der Ausgabe ins Unendliche geht) gegen die Entropie der Quelle.

Bedingte Versionen

Die bedingte Kolmogorov-Komplexität zweier Strings ist, grob gesagt, definiert als die Kolmogorov-Komplexität von x gegeben y als Hilfseingabe für die Prozedur.

Es gibt auch eine längenbedingte Komplexität , die die Komplexität von x bei der Länge von x als bekannt/Eingabe ist.

Siehe auch

Anmerkungen

Verweise

Weiterlesen

Externe Links