Claro, en el sentido de que la longitud del comando más corto que produce un entero particular (o cadena de bits) es de hecho una complejidad Kolmogorov-Chaitin (-Solomonoff) de ese entero / cadena de bits.
Eso es cierto si los “comandos” están escritos en C, ensamblado x86, INTERCAL, Mathematica o una codificación de una máquina de Turing de una sola cinta.
Todo esto da lugar a una complejidad de Kolmogorov. Las diferentes medidas de complejidad están relacionadas porque la diferencia entre ellas está limitada por una constante. Por ejemplo, la complejidad “C” de una cadena de bits no es más que k mayor que la complejidad “Mathematica” de la misma cadena de bits, donde “k” es la longitud de una función C que codifica un intérprete de Mathematica.
- ¿Cuáles son algunas habilidades de programación, algoritmos o marcos que se ven muy bien pero que son muy simples?
- Cómo construir un algoritmo para operar
- ¿Cuál es una explicación intuitiva del ataque de cumpleaños en criptografía?
- ¿Existe un algoritmo informático para detectar 'noticias falsas'?
- ¿Podemos encontrar si la matriz no contiene un elemento mayoritario en un tiempo casi constante?
¡Por supuesto, el límite superior constante puede ser muy grande!
Es importante que la complejidad de Kolmogorov sea el comando más corto que produce una salida particular; de lo contrario, podría tener la complejidad de “7” ser 1 (“7”), 3 (“4 + 3”), 13 (“1 + 1 + 1 + 1 + 1 + 1 + 1”), un googol, etc. Se supone que cada cadena de bits tiene solo una complejidad de Kolmogorov.
