Hipercomputación

El término hipercomputación se refiere a los diferentes métodos propuestos para el cálculo de funciones no calculables . Fue introducido originalmente por Jack Copeland . También se utiliza el término supercomputación de Turing , aunque el término hipercomputación puede connotarse por la atractiva posibilidad de que una máquina de este tipo sea físicamente factible. Se han propuesto algunos modelos, como las redes neuronales con números reales como peso, la capacidad de realizar un número infinito de cálculos simultáneamente o la capacidad de realizar operaciones no calculables por Turing, como límites o integraciones.

Historia

Alan Turing introdujo un modelo más poderoso que las máquinas de Turing en su artículo "  Sistemas de lógica basados ​​en ordinales  " en 1939. Este artículo examina los sistemas matemáticos en los que tenemos un oráculo capaz de calcular una única función arbitraria (no recursiva). de natural a natural. Utilizó esta máquina para demostrar que incluso en estos sistemas más potentes está presente la indecidibilidad . Este texto de Turing destacó el hecho de que las máquinas oráculo eran solo abstracciones matemáticas y no podían realizarse físicamente.

El desafío de la hipercomputación

Hoy en día, la teoría algorítmica de la información nos permite comprender mejor lo que requiere la hipercomputación. El sello distintivo de una hipercomputadora es su capacidad para resolver el problema de apagado , para sus programas, lo que una computadora común (una máquina de Turing) es incapaz de hacer. Sin embargo, una computadora convencional puede determinar si un programa se detiene o no si conoce el númeroΩ{\ Displaystyle \ Omega} , que es un número aleatorio Y, por lo tanto, contiene información infinita. es, por tanto, un oráculo para el problema de cierre. La representación de esta cantidad requiere una secuencia infinita de bits y no existe un programa para calcularla de manera exhaustiva. Por lo tanto, una hipercomputadora debería poder obtener datos por otros medios que no sean un cálculo en el sentido de las máquinas de Turing. Ω{\ Displaystyle \ Omega}Ω{\ Displaystyle \ Omega}

Existe un procedimiento de aproximación para computadoras discretas (computadoras ordinarias) que permite la aproximación utilizando un programa simple de tiempo compartido. Por otro lado, no es posible saber qué tan cerca está este programa del número en un momento dado. Ω{\ Displaystyle \ Omega}Ω{\ Displaystyle \ Omega}

Posibilidades teóricas y conceptuales de las hipercomputadoras

• Una computadora discreta con acceso a la probabilidad de apagado puede resolver el problema de apagado. Para un programa de bits de entrada, la lectura de los primeros bits del número da el número de programas que terminan entre los programas. Luego procedemos de la siguiente manera: en cada paso se ejecutan las primeras instrucciones de cada uno de los programas. Incrementamos de esta manera hasta que los programas hayan terminado. Solo tienes que comprobar que el programa de entrada forma parte del mismo.Ω{\ Displaystyle \ Omega}no{\ Displaystyle n}no{\ Displaystyle n}Ω{\ Displaystyle \ Omega}k{\ Displaystyle k}2no{\ Displaystyle 2 ^ {n}}I{\ Displaystyle i}I{\ Displaystyle i}2no{\ Displaystyle 2 ^ {n}}I{\ Displaystyle i}k{\ Displaystyle k}
• Una máquina de Turing capaz de realizar un paso de infinito (ver supertâche  (en) ).
• Una computadora real (una especie de calculadora analógica ideal) podría realizar hipercomputación si la física permitiera variables reales en el sentido amplio (no solo números computables reales ) y se encontrara alguna forma de domesticarlas para la computación. Esto requeriría algunas leyes físicas bastante confusas (por ejemplo, una constante física medible con un valor oracular, como la constante de Chaitin ) y requeriría poder medir un valor físico real con precisión arbitraria a pesar del ruido térmico y los efectos cuánticos del ruido .
• Un sistema de mecánica cuántica que utiliza (por ejemplo) una superposición infinita de estados para calcular una función no computable . Tal sistema no podría ser una calculadora cuántica ordinaria, porque se ha demostrado que las computadoras cuánticas son reducibles por Turing (podrían acelerar los programas para resolver ciertos problemas pero no permitirían resolver nuevos problemas).
• Una computadora digital ubicada en un espacio-tiempo , llamada espacio-tiempo-Malament Hogarth  (In) , podría lograr un número infinito de operaciones mientras permanece dentro del cono de luz de un determinado evento espacio-temporal.

Ver también

• Tesis de Church-Turing
• Oracle (máquina de Turing)

Notas

1. Jean-Paul Delahaye , Información, complejidad y azar , Hermès [ detalle de la edición ] , p.  87-88.
2. simple hecho de poder realizar infinitos pasos (es decir, nunca detenerse) no es suficiente. Por otro lado, la noción de cálculo de límites funciona. Considere nuevamente el procedimiento de aproximación numérica , que converge lenta y monótonamente. Aunque cada término de esta secuencia es computable, el límite no lo es. Si una calculadora pudiera realizar todos estos pasos de aproximación de números infinitos, obtener y almacenar su infinidad de dígitos, podría resolver fácilmente el problema de parada.Ω{\ Displaystyle \ Omega}Ω{\ Displaystyle \ Omega}Ω{\ Displaystyle \ Omega}

Referencias

• Alan Turing , Sistemas de lógica basados ​​en ordinales , Proc. Matemáticas de Londres. soc., 45 , 1939

• Tien Kieu, algoritmo cuántico para el décimo problema de Hilbert , int. J. Theor. Phys., 42 (2003) 1461-1478, archivo de impresión electrónica quant-ph / 0110136 ( PDF )

• Boris Tsirelson  (en) , El algoritmo cuántico de Kieu no resuelve el décimo problema de Hilbert . archivo de impresión electrónica quant-ph / 0111009 ( PDF )

• Tien Kieu, Respuesta a "El algoritmo cuántico de Kieu no resuelve el décimo problema de Hilbert" . archivo de impresión electrónica quant-ph / 0111020 ( PDF )

• Hava Siegelman  (en) , Redes neuronales y computación analógica: más allá del límite de Turing Boston: Birkhäuser.

• Hava Siegelmann, La dinámica simple de las teorías de súper Turing ; Theoretical Computer Science Volume 168, Número 2, 20 de noviembre de 1996, páginas 461-472. (el enlace es a la copia del sitio web de ScienceDirect)

• Keith Douglas, Super-Turing Computation: a Case Study Analysis ( PDF ), Tesis de maestría, Universidad Carnegie Mellon, 2003.

• Lenore Blum , Felipe Cucker , Michael Shub , Stephen Smale , Complexity and Real Computation , Springer-Verlag 1997. Desarrollo general de la teoría de la complejidad para máquinas abstractas que calculan en números reales o complejos en lugar de bits.

• Thomas Natschläger y col. la "Computadora líquida": una estrategia novedosa para la computación en tiempo real en series de tiempo

• http://www.nature.com/nsu/010329/010329-8.html Un artículo de Nature sobre lo anterior.

• “  Sobre el poder computacional de las redes neuronales  ” ( Archivo • Wikiwix • Archive.is • Google • ¿Qué hacer? )