Máquina de Turing + dilatación del tiempo = ¿resolver el problema de detención?

15

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 ?

margarita
fuente
Quizás relevante: researchgate.net/publication/… .
Martín-Blas Pérez Pinilla
1
¿Tendrá el observador de duración infinita acceso a energía infinita para realizar sus pasos de cálculo infinito? (alternativamente, ¿se puede formular un probador de problemas de detención de forma reversible? No lo creo)
user253751
Definitivamente relevante: chiark.greenend.org.uk/~sgtatham/infinity.html
Julio
@immibis: ¡Sí lo hace! Estudié esto en la universidad.
Joshua
Tenga en cuenta que es un error común pensar que una máquina de turing que no se detiene debe "hacer un bucle". Esto implica una especie de estado repetido, o de hacer lo mismo una y otra vez. De hecho, podemos determinar decididamente si una máquina tiene este comportamiento o se detiene, dado que tiene uno de los dos. Las máquinas problemáticas que nos confunden no son las que se repiten, sino las que giran caóticamente en un patrón casi aleatorio, desafiando todo sentido de regularidad.
exfret

Respuestas:

26

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.

Lagarto discreto
fuente
44
Quizás también sea útil que el formalismo de una "máquina de hiper-turing" como una máquina Turong que puede hacer un número infinito de pasos en una cantidad de tiempo finita es de hecho un formalismo común. Puede encontrar mucho material útil allí.
Cort Ammon - Restablece a Mónica el
10

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).

Ariel
fuente
1
Re. "... para que tenga algún efecto en la tesis de la Iglesia-Turing, necesitas que exista en la práctica". ¿No son las máquinas de Turing también máquinas idealizadas que no pueden existir en la práctica?
margarita
1
De hecho, solo refleja (o al menos intenta) nuestra intuición con respecto a lo que es una "máquina informática". Es por eso que la tesis de Church-Turing es una tesis, y no un teorema matemático. Solo informa informalmente que las máquinas de Turing capturan el verdadero poder computacional que existe en nuestro mundo.
Ariel
Mi punto es: ¿por qué debe existir una máquina de Turing de tiempo infinito en la práctica para que tenga algún efecto en CTT, cuando las máquinas de Turing estándar tampoco existen en la práctica?
margarita
1
Una formulación de la tesis de Church-Turing es la siguiente: cada posible modelo computacional realizable en nuestro mundo no excede el poder de la máquina de Turing. La tesis misma se define en relación con algún modelo básico (es decir, la máquina de Turing).
Ariel
Hice una pregunta de seguimiento porque, incluso después de revisar las diapositivas publicadas, no entiendo realmente la afirmación de que no se puede construir una máquina cuántica práctica de Turing. (2ª vez para publicar este comentario, ahora apunta a QC.SE en lugar de CS.SE)
BurnsBA
7

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.

Davislor
fuente
2
"Todavía no hay datos suficientes para una respuesta significativa".
Robert Columbia
Tenga en cuenta que la razón principal por la que mencioné las máquinas de Turing bajo ciclos cerrados similares al tiempo es que existe alguna 'modificación física' del modelo de la máquina de Turing, de modo que el problema de detención es computable por esa máquina. Parece que otros saben más sobre la dilatación del tiempo que yo, pero este ejemplo me hace dudar al menos de hacer tales afirmaciones a menos que se dé una formalización de la dilatación del tiempo.
Lagarto discreto
@Discretelizard Esa fue una gran contribución a la discusión. No estoy seguro de entender completamente la intención del OP, pero la dilatación del tiempo relativista es un concepto real en la física moderna, y respondí suponiendo que estaba usando la definición estándar del término.
Davislor
@Davislor Por supuesto, la dilatación del tiempo está bien definida, dentro de la física . Una máquina de Turing es un objeto matemático . Hasta donde sé, lo mejor que podemos hacer para combinar los dos es crear una 'analogía física' de una máquina de Turing y mostrar formalmente cómo interactúa esto con la dilatación del tiempo. Esto es (un ejemplo de) lo que quiero decir con una 'formalización'. No creo que haya una forma única de formalizar esto y que los resultados puedan diferir, por lo tanto, dudo en decir algo concluyente al respecto.
Lagarto discreto
Dicho esto, podría ser posible que la respuesta sea 'no' para cualquier formalización razonable, pero tal afirmación está más allá de mi experiencia, al menos.
Lagarto discreto
5

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

  • La entropía computacional en la región compacta excede el Bekensteinunido a la entropía (cuyo límite es proporcional al área de superficie de la región), por lo que se colapsa en un agujero negro (instantáneamente) y ninguna señal puede alcanzarlo desde su interior. (La métrica de Kerr describe un espacio-tiempo MH. Solo se observa que el proceso infinito se completa cuando el observador pasa al horizonte de eventos interno. Sin tener en cuenta la incertidumbre actual sobre la física de dicho pasaje, ningún observador remoto tiene acceso al resultado del cálculo - solo el observador que se ha desvanecido en el agujero negro tiene el resultado. Esta no es una descripción de un proceso computacional útil. Parafraseando: "Tenemos un oráculo que produce la respuesta correcta a cualquier pregunta que haga en tiempo constante en tal una forma en que la respuesta existe solo en el instante en que se destruye arrojándola por un agujero negro ".)
  • Una máquina de Turing destruye información cada vez que sobrescribe un símbolo en una cinta, por lo que según el principio de Landauer , se debe observar un cálculo finito en una línea mundial infinita comprimida en un segmento finito en el cono de luz pasado de la observación para requerir potencia y emisión infinitas calor infinito durante el tiempo infinitesimal que se observa para operar. Es decir, dado que se logra un alto en tiempo finito, se logra instantáneamente desde el punto de vista del observador externo, por lo que toda la potencia se consume instantáneamente y todo el calor se desarrolla instantáneamente. Alternativamente, si el cálculo no se detiene, la región compacta consume continuamente energía infinita y emite calor infinito. Resultado neto: un agujero negro, de nuevo.
  • Por otra parte, el principio de Landauer no se aplica a la computación reversible y no son ( universales ) máquina de Turing reversibles . Sin embargo, una máquina de Turing de este tipo requiere la capacidad de representar todo el espacio de estados computacionales potenciales, que es exponencial en el tamaño de la cantidad de cinta utilizada, por lo que rápidamente se encuentra con el límite de Bekenstein. Terminamos siendo capaces de evitar el problema del calor solo restringiendo a cintas de longitud limitada. De manera equivalente, tenemos un límite superior en la longitud de la cinta utilizable controlada por el área de superficie de la región que tiene una línea mundial infinita. Si no tiene en cuenta esto y su cálculo usa demasiada cinta, obtendrá un agujero negro, nuevamente.

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.

Eric Towers
fuente
1

Cita de golpes, crujidos, gemidos y chillidos:

π máquinas y las computadoras platónicas son juguetes de filósofos; solo pueden sobrevivir en la atmósfera de invernadero de las revistas de filosofía. Al final, los espacios espaciales M-H y las supertasks que suscriben pueden ser igualmente una ficción recreativa para relativistas generales sin nada mejor que hacer. Pero para llegar a esta última posición se requiere que primero se resuelvan algunos de los problemas fundamentales más profundos en la relatividad general clásica, incluida la naturaleza de las singularidades y el destino de la censura cósmica. Es esta conexión con problemas reales en física lo que los hace dignos de discusión.
(X1)(X2)...(Xnorte)F(Xl,X2,...,Xnorte)γ1norteγ1cosecha de estas labores un conocimiento del valor de verdad de la afirmación. Pero tan pronto como intervienen cuantificadores mixtos, el método falla. Sin embargo, Hogarth (1994) ha demostrado cómo, en principio, se pueden utilizar disposiciones más complicadas en los espacios-tiempo relativistas generales para verificar el valor de verdad de cualquier afirmación aritmética de complejidad cuantitativa arbitraria. Dentro de ese espacio-tiempo es difícil ver cómo mantener la actitud de que no tenemos una noción clara de verdad en aritmética.
Martín-Blas Pérez Pinilla
fuente