Problema transcomputacional

En teoría de la complejidad computacional, un problema transcomputational es aquel problema que requiere procesar más de 10⁹³ bits de información.​ Cualquier número más grande que 10⁹³ se denomina un número transcomputational. El número 10⁹³, también conocido como límite de Bremermann, es según Hans-Joachim Bremermann, el número total de bits procesados por un ordenador del tamaño de la Tierra en un período de tiempo igual a la edad estimada de la Tierra.​​​ El término transcomputacional fue acuñado por Bremermann.​

Ejemplos de problemas transcomputacionales

Probando circuitos integrados

Probar exhautivamente todas las posibles combinaciones de un circuito integrado con 309 entradas y 1 salida requiere probar de un total de 2³⁰⁹ combinaciones de entradas. Como el número 2³⁰⁹ es un número transcomputacional (i.e., un número más grande que 10⁹³), el problema de probar semejante sistema de circuitos integrados es un problema transcomputacional. Esto significa que no hay ninguna manera de verificar que el circuito ha sido diseñado correctamente para todas las combinaciones de entradas solo a través de un análisis de fuerza bruta.

Reconocimiento de patrones

Considérese una matriz tamaño q×q del tipo tablero de ajedrez, en la que cada cuadrado puede tener uncolor de un conjunto de k colores. En total hay kⁿ patrones de color, donde n = q². El problema de determinar la mejor identificación de patrones, según un criterio elegido previamente, puede solucionarse a través de la búsqueda de todos los patrones de colores posibles. Para dos colores, esta búsqueda se convierte en un problema transcomputacional cuándo la matriz tiene un tamaño 18×18 o mayor. Para una matriz 10×10, el problema se convierte en transcomputacional cuándo hay 9 o más colores.

Esto tiene alguna relevancia en los estudios fisiológicos de la retina. La retina contiene aproximadamente un millón de células fotosensibles. Incluso habiendo solo dos posibles estados por cada célula (i.e., un estado activo y un estado inactivo) el procesamiento de la retina como un todo requiere procesar más de 10³⁰⁰⁰⁰⁰ bits de información. Este caso es un ejemplo de problema más allá del límite de Bremermann.

Problemas de sistemas generales

En un sistema de n variables, en la que cada cual puede tomar k estados diferentes, puede haber kⁿ posibles estados del sistema. Para analizar un sistema como este, se requiere procesar un mínimo de kⁿ bits de información. El problema se convierte en transconmputacional cuándo el número de posibles estados del sistema es kⁿ> 10^93. Esta cota mínima puede obtenerse para los siguientes valores de k y n:

k	2	3	4	5	6	7	8	9	10
n	308	194	154	133	119	110	102	97	93

Implicaciones

La existencia de problemas transcomputacionales en el mundo real implica limitaciones de los ordenadores como herramientas de procesamiento de datos. Esta cuestión se resume en palabras de Bremermann de la siguiente forma:​

"Las experiencias de varios grupos que trabajan en la resolución de problemas, en demostración de teoremas y reconocimiento de patrones parecen apuntar en la misma dirección: Estos problemas son difíciles. No parece haber un camino real o un método simple que de un solo golpe solucione todos nuestros problemas. Mi postura de una limitación última en la velocidad y la cantidad de procesamiento de datos puede resumirse de la siguiente manera: Los problemas que involucran vastas cantidades de posibilidades no serán resueltos a través la pura cantidad de procesamiento de datos. Debemos buscar la calidad, los refinamientos, los trucos y todas las ideas ingeniosas que podamos pensar. Los ordenadores más rápidos que los de hoy serán de una gran ayuda. Los necesitaremos. Sin embargo, si nos preocupamos por los problemas que existen en principio, los ordenadores son tán rápidos como siempre lo serán.

Podemos esperar que la tecnología del procesamiento de datos avanzará paso a paso - como ha ocurrido con la tecnología ordinaria. Hay un desafío ilimitado a la inventiva aplicada a problemas específicos. También hay una necesidad sin fin de nociones y teorías generales que organicen los innumerables detalles.

En la ficción

En la obra Guía del autoestopista galáctico de Douglas Adams, la Tierra es una supercomputadora diseñada para calcular la cuestión conocida como "El sentido de la vida, el universo y todo lo demás" (la respuesta resulta ser el número 42).​

Véase también

• Hipertarea
• Cerebro Matrioshka, una megaestructura computacional teórica.
• Finitismo estricto

Referencias

• Datos: Q4461978