Complejidad de Kolmogorov: ¿Por qué necesitaría más bytes que la cadena en sí?

Respuestas:

13

El valor exacto de la complejidad de Kolmogorov depende del idioma elegido para representar las cadenas. Este lenguaje tiene que ser Turing completo, por lo que representar todas las cadenas como ellos mismos no es una opción.

Según el principio del casillero, si hay al menos una cadena de longitud como máximo cuya representación es más corta que sí misma, entonces también hay al menos una cadena de longitud como máximo n cuya representación es más larga que sí misma. (La representación es un algoritmo de compresión).nortenorte

Puede tener un lenguaje de descripción donde cada cadena tenga una representación que sea como máximo un poco más larga que ella misma: comience cada representación con un bit que indique "imprimir literalmente" o "interpretar". Sin embargo, no todos los lenguajes de descripción son tan simples.

CC

Gilles 'SO- deja de ser malvado'
fuente
6

La descripción de una cadena considerada aquí es una entrada a alguna máquina universal de Turing. Puedes pensarlo como un programa en C. La cadena hello worldno es así, por sí mismo, forman un programa en C, pero el siguiente lo hace: int main(int argc, char *argv[]) { printf("hello world"); }. Como puede ver, la sobrecarga es constante pero no cero.

Yuval Filmus
fuente
3
Como una sutileza adicional, no es posible en C (o en un C idealizado de Turing completo) imprimir cadenas arbitrarias con una sobrecarga de espacio O (1), porque algunos caracteres en literales de cadena necesitan comillas.
Gilles 'SO- deja de ser malvado'