L'insolvabilité du problème N-Body est-elle équivalente au problème d'arrêt

16

Il n'y a pas de solution analytique générale au problème des n-corps qui puisse produire une fonction analytique qui peut être utilisée pour donner l'état d'un système à n-corps à un temps arbitraire t avec une précision exacte. Cependant, il existe certains cas particuliers de systèmes à n corps pour lesquels une fonction analytique est connue.

De la même manière, aucun algorithme général ne peut prédire le résultat d'une machine de Turing arbitraire. Cependant, il existe de nombreux types de machines de tournage qui peuvent être déterminées pour s'arrêter ou fonctionner pour toujours.

Ces deux résultats sont-ils équivalents? La preuve de l'un implique-t-elle l'autre? Une machine magique capable de résoudre le problème d'arrêt pourrait-elle prédire l'état d'un système à n corps avec une précision exacte? Ou vice versa, une solution analytique générale au problème des n-corps nous permettrait-elle de décider du problème d'arrêt sur une machine de Turing arbitraire?

Ma conjecture initiale sur la façon d'aborder cela serait de montrer qu'un système à n corps sous gravitation est Turing complet. Je soupçonne qu'il considère que l'univers est Turing complet et fonctionne essentiellement sous gravitation (et quelques autres forces qui se comportent de la même façon), mais je n'ai aucune idée de la façon de procéder pour le prouver.

Mais je suis sceptique sur le fait que cette approche est suffisante, étant donné que je trouve possible (bien que je pense peu probable) que l'absence d'une solution analytique générale au problème des n-corps puisse être indépendante du fait que Turing soit complet.

Edit: Après avoir lu d'autres questions liées de manière tangentielle, je me suis rendu compte que le nombre de dimensions dans lesquelles opère la gravité pourrait être pertinent pour la question. Je pose spécifiquement des questions sur la gravité en 3 dimensions spatiales. Mais, étant donné des faits tels que vous avez besoin d'au moins 3 règles pour fabriquer une machine de Turing universelle et la gravité en 2 dimensions aurait juste une loi inverse au lieu d'une loi carrée inverse ∝ 1 / r 2 résultant en aucune orbite fermée , Je peux voir que la gravité en trois dimensions est Turing Complete, mais pas en deux ou une.∝1/r∝1/r2

computability turing-machines undecidability computation-models Shufflepants
la source
1
C'est votre choix de poser la question que vous voudrez, mais je crains que vous n'utilisiez des mots et des concepts techniques sans le moindre souci pour savoir s'ils peuvent avoir un sens dans le contexte où vous choisissez de les utiliser. Ce n'est pas trop scientifique. Je ne dis pas qu'il est faux de spéculer, mais cela appelle à la prudence. Qu'est-ce que cela peut éventuellement signifier pour un problème à n corps d'être Turing complet? Qu'est-ce qui pourrait être une énumération de Gödel des problèmes à n corps? Soit dit en passant, Turing épelle toujours avec un T majuscule, nous lui devons au moins autant.
babou
Je veux dire que le problème à n corps est Turing complet dans le même sens que Game of Life de Conway est Turing complet; que vous pourriez mettre en place un système de particules ponctuelles gravitationnelles et utiliser l'évolution de l'état de ce système pour effectuer le calcul.
Shufflepants
Je ne sais pas ce que tout pourrait être encodé dans la position, la vitesse ou l'accélération d'un certain nombre de particules ponctuelles de masses variables ou identiques. Je demande explicitement s'il existe un tel encodage parce que je ne sais pas.
Shufflepants
1
Le jeu de la vie de Conway est une sorte de théorie de l'automate cellulaire, une structure très discrète, comme les machines de Turing. Nous pouvons donc imaginer que l'encodage de l'un dans l'autre est réalisable. Mais le problème des n-corps est dans un monde d'équations différentielles, de fonctions continues et autres ... Je doute un peu de l'encodage de l'un dans l'autre. Ce que vous pourriez espérer (bien que je doute, et je suis incompétent de toute façon), c'est que la non-existence d'une solution analytique au problème des n-corps serait la conséquence d'une contradiction interne à toute théorie qui peut exprimer ce problème, un peu comme le preuve du problème d'arrêt.
babou
1
En fait, votre meilleure chance est un problème de mathématiques. Les physiciens vous diront que le n-corps est chaotique, sensible aux papillons, de sorte que les fluctuations quantiques tueront tout codage à longue portée ou toute prédictivité de l'évolution du système, ce qui ne fait pas trop bien pour une machine de Turing. Les maths pourraient bien dire quelque chose de pire, mais je ne sais heureusement pas ce que c'est.
babou

Réponses:

9

n2

Voir par exemple

vzn
la source
Je n'ai pas eu la chance de lire et de comprendre pleinement ce premier article, mais il semble qu'il soit probablement aussi proche de répondre à mes questions qu'on pourrait l'espérer. Donc, j'accepte cette réponse.
Shufflepants