¿Es la insolubilidad del problema del cuerpo N equivalente al problema de detención?

16

No existe una solución analítica general para el problema del cuerpo n que pueda producir una función analítica que pueda usarse para proporcionar el estado de un sistema n-cuerpo en un tiempo arbitrario t con precisión exacta. Sin embargo, hay algunos casos especiales de sistemas de n cuerpos para los cuales se conoce una función analítica.

De la misma manera, no existe un algoritmo general que pueda predecir el resultado de una máquina arbitraria de Turing. Sin embargo, hay muchos tipos de máquinas de torneado que pueden determinarse para detenerse o funcionar para siempre.

¿Son equivalentes estos dos resultados? ¿La prueba de uno de estos implica el otro? ¿Una máquina mágica capaz de resolver el problema de detención podría predecir el estado de un sistema de n cuerpos con precisión exacta? O viceversa, ¿una solución analítica general para el problema del cuerpo n nos permitiría decidir el problema de detención en una máquina de Turing arbitraria?

Mi conjetura inicial sobre cómo abordar esto sería mostrar que un sistema de n cuerpos bajo gravitación está completo. Sospecho que está considerando que el universo está Turing completo y esencialmente opera bajo gravitación (y algunas otras fuerzas que se comportan de manera similar), pero no tengo idea de cómo probar esto.

Pero soy escéptico de que ese enfoque sea suficiente teniendo en cuenta que encuentro posible (aunque creo que improbable) que la falta de una solución analítica general para el problema del cuerpo n pueda ser independiente de que sea Turing completo.

Editar: Después de leer algunas otras preguntas relacionadas tangencialmente, me di cuenta de que el número de dimensiones en las que opera la gravedad podría ser relevante para la pregunta. Estoy preguntando específicamente sobre la gravedad en 3 dimensiones espaciales. Pero, dados hechos como que necesita al menos 3 reglas para hacer una máquina de Turing universal y la gravedad en 2 dimensiones tendría solo una ley inversa lugar de una ley cuadrada inversa ∝ 1 / r 2 que no resultaría en órbitas cerradas , Puedo ver que resulta que la gravedad en tres dimensiones es Turing completa, pero no en dos o una.∝1/ /r∝1/ /r2

computability turing-machines undecidability computation-models Shufflepants
fuente
1
Es su elección hacer la pregunta que hará, pero me temo que puede estar usando palabras y conceptos técnicos sin preocuparse lo más mínimo de si pueden tener significado en el contexto en el que elige usarlos. Eso no es demasiado científico. No estoy diciendo que esté mal especular, pero requiere cierta precaución. ¿Qué puede significar que un problema de n-cuerpos sea Turing completo? ¿Qué podría ser una enumeración de Gödel de problemas de n cuerpos? Por cierto, Turing siempre deletrea con una T mayúscula, le debemos al menos eso.
babou
Quiero decir que el problema del cuerpo n es Turing completo en el mismo sentido que Conway's Game of Life es Turing completo; que podría configurar un sistema de partículas de punto gravitacional y usar la evolución del estado de ese sistema para realizar el cálculo.
Shufflepants
No sé qué se podría codificar en la posición, velocidad o aceleración de varias partículas puntuales de masas variables o idénticas. Estoy preguntando explícitamente si existe tal codificación porque no lo sé.
Shufflepants
1
El juego de la vida de Conway es un tipo de teoría de autómata celular, una estructura muy discreta, como las máquinas de Turing. Entonces podemos imaginar que es posible codificar uno en el otro. Pero el problema del cuerpo n está en un mundo de ecuaciones diferenciales, funciones continuas y demás ... Dudo un poco en codificar una en la otra. Lo que puede esperar (aunque lo dudo, y de todos modos soy incompetente) es que la inexistencia de una solución analítica al problema del cuerpo n sería consecuencia de una contradicción interna de cualquier teoría que pueda expresar ese problema, un poco como el prueba del problema de detención.
babou
1
En realidad, su mejor oportunidad es como un problema matemático. Los físicos le dirán que el cuerpo n es caótico, sensible a las mariposas, por lo que las fluctuaciones cuánticas matarán cualquier codificación de largo alcance o cualquier predicción de la evolución del sistema, lo que no funciona demasiado bien para una máquina de Turing. Los matemáticos pueden decir algo peor, pero afortunadamente no sé qué es.
babou

Respuestas:

9

norte2

Ver por ej.

vzn
fuente
No he tenido la oportunidad de leer y comprender completamente ese primer artículo, pero parece que probablemente esté tan cerca de responder mis preguntas como uno podría esperar. Entonces, acepto esta respuesta.
Shufflepants