Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarle el uso de la web mediante el análisis de sus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúa navegando, consideramos que acepta nuestra Política de cookies .

Actualidad científica

Síguenos
  • Google+
  • RSS
  • Investigación y Ciencia
  • Diciembre 2013Nº 447
Panorama

Complejidad

De los universos digitales a la mente

Nuevas herramientas para cuantificar nuestra intuición sobre la complejidad y el azar.

Menear

Considere las siguientes cadenas binarias: 010101010101 y 101101001110. ¿Cuál de ellas le parece más compleja? Muchos diríamos que la segunda, ya que la primera sigue una pauta regular que podríamos describir como «seis repeticiones de 01». En la segunda, en cambio, no resultará tan sencillo identificar un patrón simple para describirla. Si el lector coincide con estas observaciones, entonces maneja una noción intuitiva de complejidad. Pero ¿es posible cuantificarla?

La teoría algorítmica de la información nos ofrece una respuesta. La complejidad de Kolmogórov de un objeto (también conocida como complejidad de Kolmogórov-Chaitin, o complejidad algorítmica) se define como la longitud, en bits, del programa informático más corto que lo produce. Un programa es una secuencia de instrucciones ejecutables por una computadora, algo no muy distinto de una orden como «repite seis veces 01». Pero ¿cuáles son los programas más cortos que generan 010101010101 y 101101001110, respectivamente?

En cierto modo, la longitud del programa más corto dependerá del lenguaje de programación que elijamos. Al igual que «repite seis veces 01» posee 20 caracteres en castellano pero no así en otros idiomas, algo parecido sucede con los programas informáticos. Sin embargo, ello no plantea grandes problemas, ya que puede demostrarse que las diferencias de longitud debidas al lenguaje de programación se hallan acotadas por una constante. El verdadero inconveniente con el que nos topamos es el de la incomputabilidad: no existe ningún procedimiento sistemático que permita encontrar cuál es el programa más corto que genera una cadena numérica dada.

Puede conseguir el artículo en:

Artículo individual

Artículos relacionados

BOLETÍN ACTUALIDAD¿Quieres estar al día de la actualidad científica? Recibe el nuevo boletín de actualidad con nuestros mejores contenidos semanales gratuitos (noticias y posts). Si lo deseas también puedes personalizar tu suscripción. BOLETÍN ACTUALIDAD¿Quieres estar al día de la actualidad científica? ¡Recibe el nuevo boletín de contenidos gratuitos! Ver más boletines.