Kolmogorov Komplexität: Warum brauchen Sie mehr Bytes als die Zeichenkette selbst?

Antworten:

13

Der genaue Wert der Kolmogorov-Komplexität hängt von der Sprache ab, die für die Darstellung von Zeichenfolgen ausgewählt wurde. Diese Sprache muss vollständig sein, sodass es keine Option ist, alle Zeichenfolgen als solche darzustellen.

Nach dem Pigeonhole-Prinzip gibt es, wenn es mindestens eine Kette von höchstens Länge gibt, deren Darstellung kürzer als sich selbst ist, auch mindestens eine Kette von höchstens n Länge, deren Darstellung länger als sich selbst ist. (Die Darstellung ist ein Kompressionsalgorithmus.)nn

Sie können eine Beschreibungssprache haben, in der jede Zeichenfolge eine Darstellung hat, die höchstens ein Bit länger ist als sie selbst: Beginnen Sie jede Darstellung mit einem Bit, das entweder "buchstäblich drucken" oder "interpretieren" anzeigt. Nicht alle Beschreibungssprachen sind so einfach.

CC

Gilles 'SO - hör auf böse zu sein'
quelle
6

Die hier betrachtete Beschreibung einer Saite ist eine Eingabe für eine universelle Turingmaschine. Sie können sich das als C-Programm vorstellen. Die Zeichenfolge hello worldnicht, von selbst, bildet ein C - Programm, aber die folgenden tut: int main(int argc, char *argv[]) { printf("hello world"); }. Wie Sie sehen, ist der Overhead konstant, aber nicht Null.

Yuval Filmus
quelle
3
Außerdem ist es in C (oder einem idealisierten Turing-complete C) nicht möglich, beliebige Zeichenfolgen mit O (1) Leerzeichen zu drucken, da einige Zeichen in Zeichenfolgenliteralen in Anführungszeichen gesetzt werden müssen.
Gilles 'SO- hör auf böse zu sein'