En la teoría de la complejidad computacional , un problema transcomputacional es un problema que requiere el procesamiento de más de 10 93 bits de información. [1] Cualquier número mayor que 10 93 se denomina número transcomputacional . El número 10 93 , llamado límite de Bremermann , es, según Hans-Joachim Bremermann , el número total de bits procesados por una computadora hipotética del tamaño de la Tierra dentro de un período de tiempo igual a la edad estimada de la Tierra. [1] [2] El término transcomputacional fue acuñado por Bremermann. [3]
Ejemplos de
Prueba de circuitos integrados
La prueba exhaustiva de todas las combinaciones de un circuito integrado con 309 entradas y 1 salida requiere la prueba de un total de 2 309 combinaciones de entradas. Dado que el número 2 309 es un número transcomputacional (es decir, un número mayor que 10 93 ), el problema de probar tal sistema de circuitos integrados es un problema transcomputacional. Esto significa que no hay forma de que uno pueda verificar la exactitud del circuito para todas las combinaciones de entradas a través de la fuerza bruta solamente. [1] [4]
Reconocimiento de patrones
Considere una matriz q × q del tipo tablero de ajedrez , cada cuadrado del cual puede tener uno de k colores . En total hay k n patrones de color , donde n = q 2 . El problema de determinar la mejor clasificación de los patrones, de acuerdo con algún criterio elegido, puede resolverse mediante una búsqueda a través de todos los patrones de color posibles. Para dos colores, dicha búsqueda se vuelve transcomputacional cuando la matriz es de 18 × 18 o más. Para una matriz de 10 × 10, el problema se vuelve transcomputacional cuando hay 9 o más colores. [1]
Esto tiene cierta relevancia en los estudios fisiológicos de la retina . La retina contiene alrededor de un millón de células sensibles a la luz . Incluso si solo hubiera dos estados posibles para cada celda (digamos, un estado activo y un estado inactivo), el procesamiento de la retina en su conjunto requiere el procesamiento de más de 10 300,000 bits de información. Esto está mucho más allá del límite de Bremermann . [1]
Problemas generales de los sistemas
Un sistema de n variables, cada una de las cuales puede tomar k estados diferentes, puede tener k n estados de sistema posibles. Para analizar tal sistema, se debe procesar un mínimo de k n bits de información. El problema se vuelve transcomputacional cuando k n > 10 93 . Esto sucede por los siguientes valores de k y n : [1]
k | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
norte | 308 | 194 | 154 | 133 | 119 | 110 | 102 | 97 | 93 |
Trascendencia
La existencia de problemas transcomputacionales del mundo real implica las limitaciones de las computadoras como herramientas de procesamiento de datos. Este punto se resume mejor en las propias palabras de Bremermann: [2]
- "Las experiencias de varios grupos que trabajan en la resolución de problemas, la demostración de teoremas y el 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 resuelva Todos nuestros problemas. Mi análisis de las limitaciones finales en la velocidad y la cantidad de procesamiento de datos se puede resumir así: Los problemas que involucran un gran número de posibilidades no se resolverán con la mera cantidad de procesamiento de datos. Debemos buscar calidad, refinamientos, trucos , por cada ingenio que podamos imaginar. Las computadoras más rápidas que las de hoy serán de gran ayuda. Las necesitaremos. Sin embargo, cuando nos ocupamos de los problemas en principio, las computadoras de hoy en día son tan rápidas como siempre .
- Podemos esperar que la tecnología de procesamiento de datos avance paso a paso, tal como lo ha hecho la tecnología ordinaria. Existe un desafío ilimitado para el ingenio aplicado a problemas específicos. También existe una necesidad incesante de nociones y teorías generales para organizar la miríada de detalles ".
En ficción
En La Guía del autoestopista galáctico de Douglas Adams , la Tierra es una supercomputadora, diseñada para calcular la pregunta conocida como "La pregunta fundamental de la vida, el universo y todo" (cuya respuesta se sabe que es 42). [5]
Ver también
- Hypertask
- Cerebro Matrioshka , una megaestructura informática teórica
- Finitismo estricto
Referencias
- ↑ a b c d e f Klir, George J. (1991). Facetas de la ciencia de sistemas . Saltador. págs. 121-128. ISBN 978-0-306-43959-9.
- ^ a b Bremermann, HJ (1962) Optimización a través de la evolución y la recombinación En: Self-Organizing systems 1962, editado MC Yovitts et al., Spartan Books, Washington, DC págs. 93-106.
- ^ Heinz Muhlenbein. "Algoritmos, datos e hipótesis: Aprendizaje en mundos abiertos" (PDF) . Centro Nacional Alemán de Investigación en Ciencias de la Computación . Consultado el 3 de mayo de 2011 .
- ^ Miles, William. "Límite de Bremermann" . Consultado el 1 de mayo de 2011 .Si bien la fuente usa 308 como número de entradas, este número se basa en un error: 2308 <10 93 .
- ^ Ver lugares en La guía del autoestopista galáctico