La hipercomputación se refiere a modelos de computación que no son posibles de simular usando máquinas Turing. (¡Las hipercomputadoras no son necesariamente realizables físicamente!) Algunas hipercomputadoras tienen acceso a un recurso que permite resolver el problema de detención de las máquinas Turing estándar. Llame a esto una "superpotencia": una hipercomputadora con una superpotencia puede decidir si una máquina Turing estándar termina.
¿Qué tipos de "superpoderes" utilizan los hipercomputadores?
La tesis de Ed Blakey establece un marco formal para clasificar algunos de los principales tipos de recursos utilizados en la hipercomputación, pero no trata de proporcionar una encuesta exhaustiva de superpotencias. No estoy interesado en una lista de hipercomputadoras (hay una buena lista en el artículo de Wikipedia), pero en entender qué "salsa especial" usa cada modelo, tal vez considerado como un tipo único de recurso.
Esta pregunta está inspirada en ¿Cuán fundamental es la indecidibilidad? . También relacionado está ¿Qué significaría refutar la tesis de Church-Turing? lo que generó mucha discusión interesante, y ¿Hay algún modelo de computación actualmente en estudio con la posibilidad de ser más poderoso que las máquinas de Turing? .
fuente
Respuestas:
En el artículo sobre el poder de la multiplicación en máquinas de acceso aleatorio, Hartmanis ha demostrado que, si agregamos instrucción de multiplicación de costo unitario en una RAM (llamada MRAM), entonces para este modelo P = NP. Además, los idiomas decididos en tiempo polinómico en el modelo MRAM son exactamente los idiomas en PSPACE.
Como se indica en el documento, estos resultados muestran que la multiplicación tiene la misma complejidad que la suma si P = PSPACE.
Un resultado más relacionado del que he oído hablar es que si agregamos una instrucción de división con precisión infinita en una RAM, podemos resolver problemas indecidibles. Sin embargo, no pude encontrar el documento que prueba este resultado. Si alguien está familiarizado con él, comente y actualizaré la respuesta.
fuente
¡Entonces has descubierto que los TM no pueden resolver todos los problemas! El primer paso que Turing tomó y es altamente lógico (aunque no es trivial si se considera el estado de la computación en ese momento) fueron los oráculos.
Informalmente, está agregando a su máquina un nuevo módulo de caja negra que puede "de alguna manera" resolver el problema que su máquina no puede, digamos el problema de detención. Por supuesto, los oráculos son solo una abstracción matemática y no hay ningún secreto detrás de su funcionamiento interno. Personalmente, no veo ninguna forma en que un oráculo pueda usarse para descubrir un modelo que refuta la tesis de la Iglesia-Turing.
Conozco otros modelos, pero creo que simplemente amplían las ideas que he presentado aquí o son construcciones matemáticas puras, por lo que son más como "trucos ingeniosos" que algo que podría refutar la tesis de la Iglesia-Turing.
fuente
No es exactamente lo que pediste, pero Scott Aaronson tiene un artículo, bien explicado aquí, sobre las máquinas Turing con la capacidad de viajar en el tiempo, pero con requisitos de autoconsistencia (es decir, no puedes regresar para cambiar el pasado. Puedes observar el futuro , pero debe ser coherente con el presente).
fuente