¿Qué es la hipercomputación y cuáles son los conceptos involucrados en ella?

Answer 1

Imagine que tiene una máquina y una tira de papel infinitamente larga que se divide en cajas de una longitud determinada. Nuestra máquina es capaz de un par de cosas. Puede leer símbolos dentro de un cuadro, puede escribir símbolos dentro de un cuadro, tiene una memoria limitada y puede mover, en un momento dado, un cuadro a la izquierda o un cuadro a la derecha. La máquina funciona de acuerdo con una tabla de comportamiento: dado lo que hay en la tira de papel y lo que hay en la memoria de la máquina, sabrá lo que debe hacerse a continuación y lo hará.

Este pequeño experimento mental se llama “máquina de Turing”. Lo que llamamos computadoras son realmente solo implementaciones prácticas de máquinas Turing que no involucran trozos de papel infinitamente largos. Como resultado, hay varios otros sistemas que son equivalentes a las máquinas de Turing: el cálculo lambda de Alonzo Church es uno de los más famosos. Entonces, lo que sea que pueda hacer con una máquina de Turing, puede hacerlo con una máquina que implemente el cálculo lambda y viceversa.

Hay muchos, muchos problemas que puede resolver con las máquinas de Turing y sus equivalentes. Sin embargo, resulta que hay algunos problemas que no puede resolver. Uno de los problemas más famosos que no puede resolver con una máquina de Turing es el problema de detención. El problema de detención es el siguiente: se le da un algoritmo arbitrario y una entrada. Proporcione un algoritmo (llamémoslo H) que determinará si el algoritmo que le han dado alguna vez deja de ejecutarse dada la entrada que le han dado.

Para algunos pares de algoritmo-entrada, esto es trivial. Por ejemplo (usando Python aquí):

def stops(x): return x + 2 >>> stops(0) 

Esto deja de ejecutarse claramente cuando escupe un valor de 2. H(stops, 0) proporciona claramente un valor de “VERDADERO”.

Similar:

 def does_not_stop(x): while True: x += 2 return 2 >>> does_not_stop(0) 

Por inspección, podemos descubrir que este algoritmo se atascará en un bucle infinito, por lo que H(does_not_stop, 0) es “FALSE”.

Sin embargo, resulta que no todos los algoritmos son tan fáciles de descifrar, y no es como si pudieras descubrir si un algoritmo nunca deja de ejecutarse al intentar ejecutarlo (solo puedes demostrar que lleva mucho, mucho tiempo) ejecutar), por lo que el problema de detención no se puede resolver utilizando una máquina Turing.

Por lo tanto, llegamos al concepto de “hipercomputación”: la idea de que existen modelos de computación que no son equivalentes a las máquinas de Turing que pueden resolver problemas que están más allá de las máquinas de Turing. Hay una variedad de tales modelos; sin embargo, si alguno de ellos puede implementarse es otro asunto completamente diferente.

Answer 2

Existe un modelo general de computadoras conocido como máquina de Turing. Todas las computadoras reales solo pueden hacer cálculos permitidos por una máquina de Turing, y hay algo llamado la “tesis de Church-Turing” que dice que algo es computable si y solo si puede ser calculado por una máquina de Turing. Es una “tesis” y no un teorema porque es una definición.

La hipercomputación juega con la idea de que la tesis de Church-Turing está equivocada y que hay cosas que puedes calcular que una máquina de Turing no puede calcular. Nadie sabe cómo hacer eso físicamente, pero esto es una investigación, por lo que las personas están pensando en las matemáticas de algo que puede existir o no y que la mayoría de la gente piensa que no puede existir. Como esto es matemático, pensar en cosas que no pueden existir físicamente está bien, y pensar en este tipo de cosas puede ser útil para comprender cómo funcionan las matemáticas.

La otra cosa que la hipercomputación nos ayuda a hacer es pensar en cómo podría funcionar el universo. Por ejemplo, resulta que si pudieras construir una computadora que usara números reales reales en lugar de números reales “aproximados”, entonces ocurrirían muchas cosas extrañas. Entonces, este puede ser un mensaje de que no puedes construir una computadora que use números reales.