Hay tiempos espaciales relativistas (por ejemplo, tiempos espaciales MH; ver Hogarth 1994) donde una línea mundial de duración infinita puede estar contenida en el pasado de un observador finito. Esto significa que un observador normal puede tener acceso a un número infinito de pasos de cálculo.
Suponiendo que sea posible que una computadora funcione perfectamente durante un período de tiempo infinito (y sé que es una gran pregunta): se podría construir una computadora HM que viaje a lo largo de esta línea del mundo infinita, calculando el problema de detención para una M. Si M se detiene , HM envía una señal al observador finito. Si después de un número infinito de pasos el observador no recibe una señal, el observador sabe que M realiza un bucle, resolviendo el problema de detención.
Hasta ahora, esto me parece bien. Mi pregunta es: si lo que he dicho hasta ahora es correcto, ¿cómo altera esto la prueba de Turing de que el problema de detención es indecidible? ¿Por qué falla su prueba en estos tiempos espaciales ?
Respuestas:
Tenga en cuenta que la prueba de Turing es matemática, no física. Dentro del modelo de una máquina de Turing definida, la indecidibilidad del problema de detención se ha demostrado y es un hecho matemático. Por lo tanto, la prueba de Turing no 'fallará' en el espacio-tiempo, simplemente no probará nada sobre la relación del problema de detención y la dilatación del tiempo.
Sin embargo, lo que probablemente querrá saber es si una 'máquina de Turing de dilatación del tiempo' puede resolver el problema de detención.
Si desea estudiar esto sobre la influencia de la 'dilatación del tiempo' en una máquina de Turing, deberá especificar un modelo formal mediante el cual podamos comprender formalmente lo que significa que una máquina de Turing haga uso de la dilatación del tiempo. Desafortunadamente, este formato no es adecuado para proporcionar un modelo tan formal (a menos que alguien más haya escrito un artículo sobre él) ya que crear el modelo es demasiado amplio.
Sin embargo, no es improbable que alguna formalización sea capaz de resolver el problema de detención. Este artículo de Scott Aaronson, Mohammad Bavarian y Giulio Gueltrini analiza los modelos computacionales bajo el supuesto de que existen los llamados bucles de tiempo cerrados y concluye que el problema de detención es realmente computable dentro de ese modelo.
fuente
La máquina de Turing es un modelo matemático formal de cómputo, no responde a ninguna limitación física y no le importan los efectos relativistas. Esto significa que la prueba de Turing no falla, ya que la definición estándar de máquina de Turing ni siquiera contiene una noción de "espacio-tiempo".
Lo que puede intentar y hacer es definir un modelo diferente de computación inspirado en la relatividad. Nuevamente, esto solo será un objeto formal, y la cuestión de si puede o no resolver el problema de detención pertenece al ámbito de las matemáticas y depende de su definición específica. Sin embargo, la verdadera pregunta ahora es si este nuevo modelo captura correctamente los efectos relativistas, es decir, ¿refleja realmente nuestra física y puede implementarse en nuestro mundo?
Puede ver tal discusión sobre el cálculo cuántico. Tenemos una definición formal de "máquinas cuánticas de Turing", y su potencia computacional exacta sigue siendo un problema abierto en matemáticas (aunque ni siquiera está cerca del problema de detención). Aún así, puede argumentar que esta definición realmente no refleja nuestra comprensión de la física cuántica, y se necesita una mejor. Hay argumentos que sugieren que tales máquinas ni siquiera pueden construirse, por lo que su poder exacto no tiene efecto en la tesis (fuerte) de Church-Turing.
De vuelta a tu pregunta. Existe una noción formal de una máquina de Turing de tiempo infinito , pero para que tenga algún efecto en la tesis de Turing de la Iglesia, es necesario que exista en la práctica. Quizás te interese Scott's artículo , que tiene una sección sobre cálculos que utilizan efectos relativistas, aunque parece que los argumentos ingenuos son inútiles (en el sentido de que no son prácticos, ya que el costo del tiempo se reemplaza por el costo de la energía).
fuente
La prueba de Turing muestra que ninguna máquina de Turing puede resolver el problema de detención sin importar cuánto tiempo le dedique. Si su nave espacial usó la dilatación del tiempo para darle a una computadora mil millones de años para trabajar, aún así podría no ser capaz de decirle algo más definitivo que "Aún no".
Aparentemente, (¡Gracias, @DiscreteLizard!) Si tiene un viaje en el tiempo que no puede causar paradojas, podría configurar un ciclo de tiempo que podría causar una paradoja si la computadora no puede probar si la máquina de Turing se detiene. O recibe la respuesta del futuro y la transmite de vuelta a sí misma, o se ejecuta para siempre (y, hábilmente, devuelve una superposición cuántica que se resuelve en un bucle de tiempo estable). Pero, antes de intentar esto, asegúrese de que sea seguro causar una paradoja de viaje en el tiempo.
fuente
Una objeción es que ha definido un proceso que puede producir una entropía infinita en una región compacta y que parece hacerlo en un segmento finito del pasado del observador. Esto significa algunas cosas
Es una pregunta abierta interesante si estas restricciones y cómo se aplican a las computadoras cuánticas. Bien puede ser que la complejidad de un cálculo realizado por una computadora cuántica esté limitada por el área de superficie de la computadora. Por lo tanto, es posible que tengamos que duplicar el área de superficie de una computadora cuántica extrema para obtener un qubit de cálculo más utilizable. Esto lleva rápidamente a computadoras prácticamente impracticables.
fuente
Cita de golpes, crujidos, gemidos y chillidos:
fuente