La complejidad de Kolmogórov
Rubén Rodríguez Abril
¿Existe un límite de aprendizaje para la IA, en particular para su capacidad de extraer patrones a partir de datos? Existe. Y se deriva de los postulados la teoría algorítmica de la información, que comenzó a desarrollarse en los años 60 impulsada por los trabajos de Andréi Kolmogórov, Gregory Chaitin, Leonid Levin y Ray Solomonoff. En este marco, la complejidad de Kolmogorov emerge como un concepto central: señala la longitud del algoritmo más corto que puede generar un objeto matemático, como un número, una función o incluso un sistema axiomático al completo.
La teoría de la información es, probablemente, una de las disciplinas científicas más abarcadoras y transversales del conocimiento contemporáneo. Surgida en el marco de la termodinámica y la ingeniería de telecomunicaciones, en la actualidad ha extendido sus raíces hasta ámbitos tan alejados entre sí como los de la física cuántica, la teoría de la computación, la relatividad general o incluso la biología. Y ha sido utilizada por algunos neurocientíficos en su intento de abordar problema duro de la conciencia. Es una disciplina en pleno desarrollo, y que promete transformar de un modo revolucionario a la física del siglo XXI.
Una de sus ramas, la teoría algorítmica de la información busca interpretar la estructura de los números naturales, la naturaleza de la aleatoriedad, la compresibilidad de la información o incluso los teoremas de indecibilidad de Gödel o de Turing desde la perspectiva de la teoría de la computación y los algoritmos. Los algoritmos y su complejidad se transforman en el pilar básico a través del cual describen los objetos del mundo matemático.
Los algoritmos como constructores del mundo matemático
A mi juicio, los fundamentos de la teoría pueden rastrearse en el formalismo matemático de David Hilbert, para quien la existencia de un objeto matemático dependía exclusivamente de que pudiera ser formalizado en un sistema axiomático coherente. Andréi Markov hijo llevó esta idea un paso más allá al postular que la matemática debía restringirse a la construcción de objetos y relaciones computables mediante algoritmos efectivos.
En este enfoque, para una cierta máquina de Turing universal U, cada objeto matemático debe definirse mediante una cadena de entrada (w,v), donde w es el programa a seguir por la máquina y v, si existe, es el conjunto de variables de entrada. Este marco nos permite definir ciertos números irracionales -con expansión decimal infinita o inabarcable- utilizando una fórmula finita. Por ejemplo, el número π, a pesar de ser normal y tener un patrón de expansión decimal aparentemente caótico, es perfectamente definible mediante esta simple fórmula, enunciada en su día por Leibniz, y que se puede codificar en unos pocos bytes:
La complejidad de Kolmogorov
El célebre matemático Andréi Kolmogorov, si bien no abrazó por completo el constructivismo de Hilbert y Markov, usó estas ideas para fundamentar su teoría sobre la complejidad matemática y el azar.
Definición
La complejidad de Kolmogorov K(s) o complejidad algorítmica de un objeto matemático s es la longitud mínima del programa de ordenador que lo genera (expresado mediante una cadena de dígitos). Cuando Kolmogorov formuló esta noción en 1963 no estaba pensando en ningún lenguaje de programación en particular, sino en la teoría de autómatas en su sentido más abstracto.
Así, por ejemplo en el caso del número e, su complejidad algorítmica del número es la cadena más corta (w,v) que consigue generarlo en una máquina universal de Turing. Esa cadena debería de codificar la siguiente serie de potencias:
El caso del número 0,1010101… resulta aun más trivial. Para definirlo algorítmicamente, basta un bucle while que imprima alternativamente unos y ceros, sin pararse jamás.
Paradójicamente, existen objetos matemáticos con una complejidad de Kolmogorov relativamente baja que generan patrones caóticos, impredecibles o incluso estructuras sorprendentemente complejas. Ya hemos citado los casos de los números e y π. Aun más llamativos son los conjuntos fractales como el de Mandelbrot o el de Julia, generados a partir de fórmulas sencillas y que al ser visualizados muestran una cantidad ingente de estructuras y detalles únicos, que no parecen agotarse nunca.
Figura 1. La complejidad algorítmica del conjunto de Mandelbrot es muy baja. Éste es definido a partir de la expresión fc(z)=z2+c, una fórmula compacta que no tiene más que unos pocos de caracteres de longitud. Sin embargo, cuando recreamos este conjunto en un ordenador, a medida que vamos haciendo “zoom” en la imagen aparecen nuevos detalles localmente únicos, que aunque puedan ser similares a los de escalas más grandes, nunca son exactamente iguales. Incluso si exploráramos hasta el infinito, seguiríamos descubriendo patrones nuevos. ¿De dónde procede toda esta información extra?
Incompresibilidad
Decimos que un número s es incompresible cuando su longitud en bits es similar a su complejidad algorítmica K(s), es decir, cuando no hay ningún algoritmo más corto que pueda generarlo.
Una forma elegante deconstruir un número incompresible es utilizando el método diagonal utilizado por Cantor. Ordenamos canónicamente todas las funciones diofánticas fy(x) (funciones polinómicas de número naturales a naturales) que tengan una sola variable x. Y las disponemos en una matriz: una fila para cada función, una columna para los números naturales que sirven como argumentos. Recorremos la línea diagonal (n,n) y en cada posición modificamos el último bit de la función fn(n). De este modo, obtenemos una nueva función que por construcción difiere de todas las anteriores.
Para definir esta última función hemos tenido que determinar ad hoc, uno por uno, todos sus valores para cada uno de los números naturales, utilizando en el proceso la fórmula de todas y cada una de las funciones computables canónicamente ordenadas. No hay, por lo tanto, un único algoritmo genérico, finito, que sea capaz de definir la función. Es incompresible.
Figura 2. La constante de estructura fina es crucial para la existencia de los átomos, la química y la vida. Permite integrar al electromagnetismo con otras interacciones, especialmente cuánticas. Su valor (que aproximadamente equivale a 1/137) ha sido objeto de frecuentes especulaciones, precisamente porque su complejidad de Kolmogorov es desconocida. Richard Feynman lo expresaba con las siguientes palabras: “Inmediatamente querrías saber de dónde sale este número: ¿está relacionado con π, o quizá con la base de los logaritmos naturales? Nadie lo sabe. Es uno de los malditos mayores misterios de la física: un número mágico que nos llega sin que el hombre lo comprenda. Podrías decir que la ‘mano de Dios’ escribió ese número, y ‘no sabemos cómo movió Su lápiz’”.
El teorema de la incompletitud de Chaitin
Definición
El teorema de la incompletitud de Chaitin establece que para cualquier sistema lógico S que sea consistente y capaz de expresar aritmética básica (p.e. axiomas de Peano) existe un límite de complejidad L, más allá del cual no es posible comprobar si la complejidad de Kolmogorov K(x) de cualquier cadena x es mayor que L:
K(x) > L
En otras palabras, a partir de cierto umbral L de complejidad no es posible probar si una cadena x es aleatoria o si, por el contrario, ha sido creada por un algoritmo. La constante L es finita, no computable, y dependiente de la complejidad del sistema lógico S. En cierto modo, se trata de un postulado análogo al primer teorema de Gödel: ambos afirman que existen algoritmos y patrones que, debido a su complejidad, escapan a la capacidad de formalización de un cierto sistema lógico-axiomático. Hay verdades inaccesibles para cualquier sistema finito.
De una manera general, el límite puede aproximarse mediante la siguiente expresión:
L≈K(S)+C
donde K(S) es la complejidad de Kolmogorov del sistema S, concebido como un gigantesco programa de ordenador que codifica todas sus normas y axiomas, y C es una constante, que depende de la máquina de Turing de que se trate y que por lo general no pasa de 100 bits.
Trascendencia del teorema
El teorema de la incompletitud de Chaitin tiene una gran importancia en la teoría de autómatas, puesto que señala que hay un límite finito a partir del cual los sistemas de aprendizaje de máquina no serán capaces de detectar patrones. Ese límite se deriva del juego de instrucciones de código máquina que definen el modelo empleado.
En criptografía el teorema adquiere una relevancia igualmente profunda: a partir de una complejidad límite, no es posible determinar si una cadena de caracteres es verdaderamente aleatoria o ha sido creada por un cifrado y tiene por lo tanto un significado oculto. La distinción entre azar y secreto se difumina a partir del umbral L.
Aun más trascendentales son sus implicaciones a escala física y cosmológica. Supongamos que S es el conjunto de axiomas y herramientas lógico-matemáticas en que se expresa la física moderna (leyes físicas básicas, reglas matemáticas de derivación, constantes físicas, condiciones iniciales, fluctuaciones cuánticas, etc..). Como sistema finito que es, a S posee una complejidad de Kolmogorov(K) y por tanto, un límite asociado. Si codificáramos todo ese conocimiento en un programa informático, su tamaño oscilaría en torno a 105 o 107 bits, dependiendo si tomamos por base a la aritmética de Peano o a la Teoria de Conjuntos. L se situaría en un rango parecido.
Este marco permite imaginar dos escenarios cosmológicos extremos:
-Escenarios de alta complejidad de Kolmogorov (K(Universo) > L): El funcionamiento del Universo es, en su mayor parte, incognoscible a través métodos algorítmicos. En esta franca oscura marcada por L y situada más allá del alcance de nuestros métodos axiomáticos, se desenvuelven fenómenos como el comportamiento caótico, turbulento, así como ciertos fenómenos cuánticos.
-Escenarios de baja complejidad de Kolmogorov (K(Universo) < L): El Universo tiene un funcionamiento determinista, ya sea porque en realidad consiste en un gigantesco autómata celular (Wolfram), en un vasto computador espacial (Zuse) o porque los fenómenos cuánticos aparentemente aleatorios en realidad son manifestaciones de variables ocultas (Bohm).
La complejidad algorítmica del Universo oscila entre dos extremos: por un lado, los 105-107 bits que ocuparía un programa de ordenador S capaz de codificar las leyes de la física y las condiciones iniciales del Cosmos; y por otro lado los 10123 bits que representan la entropía del Universo observable (es decir, su cantidad bruta de información).
Es importante señalar que aunque la complejidad de nuestro sistema formal sea K(S), la complejidad algorítmica real del Universo K(Universo) podría ser considerablemente mayor. Después de todo, no es lo mismo el código con que describimos el Cosmos que el código en el que el Cosmos está escrito en realidad.
Por lo general, la existencia de regularidades a escala macroscópica disminuye la complejidad algorítmica cósmica, mientras que la presencia de fenómenos cuánticos aleatorios o de una hipotética física no computable tienden a incrementarla.
Y sin embargo, dado que la complejidad de Kolmogorov es por su propia naturaleza incomputable, aunque nuestro Universo fuese plenamente regular y computable, no tendríamos manera alguna de demostrarlo.
Figura 3: El Gran Cifrado Cósmico. Se estima que el Universo actual tiene unos 10123 bits de información, frente a los 1030 que tenía en época de la recombinación. Si organizáramos estos 10123 bits en una cadena binaria x, su complejidad de Kolmogorov se revelaría como desconocida e incomputable. Supongamos, no obstante, que esta complejidad excede del límite L derivado de las leyes de la física y la matemática que conocemos. Más allá de este límite reinaría el misterio. ¿Es la información situada más allá de L puramente aleatoria? ¿O por el contrario procede de algún Gran Cifrado Cósmico, un patrón de información que debido a su complejidad queda fuera de nuestro conocimiento? No tenemos manera de saberlo.
Lecturas Recomendadas
– Chaitin, G. (2015). «El número Omega». Tusquets Editores México. ISBN: 978-607-421-656-1.
SERIES
