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.[1] 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.[1][2][3] El término transcomputacional fue acuñado por Bremermann.[3]
Ejemplos de problemas transcomputacionales editar
Probando circuitos integrados editar
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 editar
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 editar
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:
| k | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| n | 308 | 194 | 154 | 133 | 119 | 110 | 102 | 97 | 93 |
Implicaciones editar
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:[2]
- "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 editar
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).[4]
Véase también editar
- Hipertarea
- Cerebro Matrioshka, una megaestructura computacional teórica.
- Finitismo estricto
Referencias editar
- ↑ a b Facets of systems science. Springer. 1991. pp. 121-128. ISBN 978-0-306-43959-9.
- ↑ a b Bremermann, H.J. (1962) Optimization through evolution and recombination In: Self-Organizing systems 1962, edited M.C. Yovitts et al., Spartan Books, Washington, D.C. pp. 93–106.
- ↑ a b Heinz Muhlenbein. «Algorithms, data and hypotheses : Learning in open worlds». German National Research Center for Computer Science. Consultado el 13 de abril de 2017.
- ↑ See Places in The Hitchhiker's Guide to the Galaxy#Earth
Datos: Q4461978
