Como han dicho otros y como ya parece consciente, los cálculos exactos de la complejidad algorítmica (Kolmogorov) (que denotaré con K) no son posibles. Sin embargo, K es técnicamente computable semi-inferior, lo que significa que puede aproximarse desde arriba. Por lo tanto, encontrar un programa de computadora corto es una prueba suficiente de aleatoriedad no algorítmica, pero no encontrar un programa de computadora corto no es prueba suficiente de aleatoriedad.
Entonces, como algunos han dicho, basado en lo anterior, el enfoque tradicional ha sido utilizar algoritmos de compresión sin pérdidas populares como gzip y muchos otros, la mayoría basados en el algoritmo LZ original (por ejemplo, todas las aplicaciones numéricas del popular libro Kolmogorov Complexity y sus aplicaciones, y propuestas como la distancia de Google y la distancia de información normalizada de Vitanyi y Li et al.
Sin embargo, los algoritmos de compresión populares se basan principalmente en detectar regularidades estadísticas, es decir, repeticiones en una ventana de longitud fija. Esto significa que, en la práctica, la aplicación de algoritmos de compresión no es mucho mejor que aproximar la entropía (que denotaré con S) de una secuencia que las estimaciones de K de la misma secuencia, cuando precisamente la principal diferencia entre S y K es que K es, en principio, capaz de detectar ‘recursividad’, es decir, firmas algorítmicas más allá de triviales regularidades estadísticas.
- ¿Cómo funciona la ordenación por fusión en C ++?
- ¿Por qué se usa el sistema binario?
- ¿Qué algoritmos básicos debe saber un programador promedio?
- Cómo devolver una matriz multidimensional utilizando dos parámetros en C ++
- ¿Cómo funciona el algoritmo de fijación de precios de Megabus?
Afortunadamente, recientemente se han introducido nuevos esfuerzos que complementan y proporcionan verdaderas alternativas a la aplicación de algoritmos de compresión. Estos se basan en el concepto de probabilidad algorítmica y en encontrar evidencia estadística de que una secuencia es algorítmicamente probable ejecutando una gran cantidad de programas de computadora cortos y construyendo una distribución de salida empírica que la teoría estableció que se aproximará a lo que se llama Distribución Universal (que ha sido llamado ‘milagroso’ debido a las poderosas propiedades y que tiene, en particular al tema de inducción / inferencia) ver:
La distribución universal milagrosa
Los métodos introducidos basados en la probabilidad algorítmica y la distribución universal se explican en el siguiente documento:
Evaluación numérica de la complejidad algorítmica para cadenas cortas: una mirada a la estructura más interna de aleatoriedad
Cálculo de la complejidad de Kolmogorov a partir de las distribuciones de frecuencia de salida de máquinas pequeñas de Turing
Una forma de explicar la idea central es pensar que el método encuentra pequeños programas de computadora que producen parte de la secuencia y luego suma la longitud de la lista de programas que producen la secuencia completa. Aquí explicado en un video animado:
Una herramienta en línea implementa estos métodos:
Calculadora de complejidad algorítmica en línea
