Complejidad algorítmica (Kolmogórov-Solomonoff-Chaitin)
Kolmogorov complexity
- Fecha
- 1965 · fiabilidad alta
- Lugar
- Moscú, URSS
- Autoría
- Andréi Kolmogórov (1965), Ray Solomonoff (1960) y Gregory Chaitin (1966), independientes
- Personas
- 👤 Andréi Kolmogórov1903–1987👤 Gregory Chaitin1947–👤 Ray Solomonoff1926–2009
- Ámbito
- Saber y símbolos
⚠️ Dato en discusión: las fuentes no coinciden.
Qué se descubrió
La complejidad de una cadena es la longitud del programa más corto que la produce; define rigurosamente la aleatoriedad y es incomputable. Une información, computación y probabilidad.
Triple descubrimiento independiente en la URSS y en Estados Unidos.
A qué dio paso
- teoría algorítmica de la información
- inferencia inductiva y principio de longitud mínima de descripción
- teorema de incompletitud de Chaitin
Se apoya en
- Máquina de Turing (concepto de computación universal)1936
- teoría de la información de Shannon
Hizo posible
- Constante de Chaitin1975
- compresión y clasificación por compresión