Hispanopedia WikiEn la teoría de la complejidad computacional , un problema transcomputacional es aquel que requiere el procesamiento de más de 10⁹³ bits de información. [ 1 ] Cualquier número mayor que 10⁹³ se denomina número transcomputacional . El número 10⁹³ , 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 en 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
Pruebas de circuitos integrados
Probar exhaustivamente todas las combinaciones de un circuito integrado con 309 entradas booleanas y 1 salida requiere probar un total de 2³⁰⁹ combinaciones de entradas. Dado que el número 2³⁰⁹ es un número transcomputacional (es decir, un número mayor que 10⁹³ ) , el problema de probar dicho sistema de circuitos integrados es un problema transcomputacional. Esto significa que no hay forma de verificar la corrección del circuito para todas las combinaciones de entradas solo mediante fuerza bruta . [ 1 ] [ 4 ]
Reconocimiento de patrones
Consideremos una matriz q × q del tipo tablero de ajedrez , donde cada casilla puede tener uno de k colores . En total , existen k n patrones de color , donde n = q² . El problema de determinar la mejor clasificación de los patrones, según algún criterio elegido, puede resolverse mediante una búsqueda entre todos los patrones de color posibles. Para dos colores, dicha búsqueda se vuelve transcomputacional cuando la matriz es de 18 × 18 o mayor. 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 fotosensibles . Incluso si solo hubiera dos estados posibles para cada célula (por ejemplo, un estado activo y un estado inactivo), el procesamiento de la retina en su conjunto requiere el procesamiento de más de 10³ 000 bits de información. Esto supera con creces el 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 posibles estados del sistema. Para analizar dicho 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 para los siguientes valores de k y n : [ 1 ]
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 diversos 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 fácil ni un método sencillo que resuelva todos nuestros problemas de un solo golpe. Mi análisis de las limitaciones últimas en la velocidad y la cantidad de procesamiento de datos puede resumirse así: los problemas que implican un gran número de posibilidades no se resolverán simplemente con la cantidad de procesamiento de datos. Debemos buscar la calidad, los refinamientos, los trucos, toda la ingeniosidad que podamos imaginar. Las computadoras más rápidas que las actuales serán de gran ayuda. Las necesitaremos. Sin embargo, cuando nos ocupamos de problemas de principio, las computadoras actuales son tan rápidas como lo serán jamás.
- Podemos esperar que la tecnología de procesamiento de datos avance paso a paso, al igual que lo ha hecho la tecnología convencional. Existe un desafío ilimitado para el ingenio aplicado a problemas específicos. Asimismo, existe una necesidad constante de nociones y teorías generales para organizar la infinidad de detalles.
Véase también
- Hipertarea
- Cerebro Matrioshka , una megaestructura de computación teórica
- Finitismo estricto
Referencias
- 1 2 3 4 5 6 Klir, George J. (1991). Facetas de la ciencia de sistemas . Springer. págs. 121–128 . ISBN 978-0-306-43959-9.
- 1 2 Bremermann, HJ (1962) Optimización a través de la evolución y la recombinación En: Sistemas autoorganizados 1962, editado por MC Yovitts et al., Spartan Books, Washington, DC pp. 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. "El límite de Bremermann" . Consultado el 1 de mayo de 2011 .Si bien la fuente utiliza 308 como número de entradas, este número se basa en un error: 2 308 < 10 93 .
- Teoría de la computación
- Teoría de la complejidad computacional
- Límites de la computación
