Problema transcomputacional

En teoría de la complejidad computacional, un problema transcomputational es aquel problema que requiere procesar más de 1093 bits de información. Cualquier número más grande que 1093 se denomina un número transcomputational. El número 1093, 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 2309 combinaciones de entradas. Como el número 2309 es un número transcomputacional (i.e., un número más grande que 1093), 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 kn patrones de color, donde n = q2. 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 10300000 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 kn posibles estados del sistema. Para analizar un sistema como este, se requiere procesar un mínimo de  kn bits de información. El problema se convierte en transconmputacional cuándo el número de posibles estados del sistema es kn> 10^93. Esta cota mínima puede obtenerse para los siguientes valores de k y n:

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 

Complejidad computacional