16
$\begingroup$

There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, there are some special cases of n-body systems for which an analytic function is known.

In much the same way, there is no general algorithm which can predict the result of an arbitrary Turing machine. Although, there are many kinds of Turning machine which can be determined to halt or run forever.

Are these two results equivalent? Does the proof of one of these imply the other? Would a magic machine that is able to solve the halting problem be able to predict the state of an n-body system with exact precision? Or vice versa, would a general analytic solution to the n-body problem allow us to decide the halting problem on an arbitrary Turing machine?

My initial guess on how to approach this would be to show that an n-body system under gravitation is Turing complete. I suspect that it is considering the universe is Turing complete and essentially operates under gravitation (and a few other forces that behave similarly), but I have no idea how to go about proving this.

But I am skeptical that that approach is sufficient considering I find it possible (though I think unlikely) that the lack of an analytic general solution to the n-body problem could be independent of it being Turing complete.

Edit: After reading some other tangentially related questions, I realized that the number of dimensions in which gravity is operating could be relevant to the question. I'm specifically asking about gravity in 3 spatial dimensions. But, given facts such as you need at least 3 rules to make a universal Turing machine and gravity in 2 dimensions would have just an inverse law $ \propto 1/r $ instead of an inverse square law $ \propto 1/r^2 $ resulting in no closed orbits, I can see it turning out that gravity in three dimensions is Turing Complete, but not in two or one.

$\endgroup$
  • 1
    $\begingroup$ It is your choice to ask the question you will, but I am afraid you may be using technical words and concepts without the least care for whether they can have meaning in the context where you choose to use them. That is not too scientific. I am not saying it is wrong to speculate, but it calls for some caution. What can it possibly mean for an n-body problem to be Turing complete? What might be a Gödel enumeration of n-body problems? By the way, Turing always spells with a capital T, we owe him at least that much. $\endgroup$ – babou Jun 2 '15 at 17:18
  • $\begingroup$ I mean the n-body problem being Turing complete in the same sense that Conway's Game of Life is Turing complete; that you could set up a gravitational point particle system and using the evolution of that system's state to perform calculation. $\endgroup$ – Shufflepants Jun 2 '15 at 18:08
  • $\begingroup$ I don't know what all could be encoded in the position, velocity, or acceleration of a number of point particles of varying or identical masses. I'm explicitly asking if there exists such an encoding because I don't know. $\endgroup$ – Shufflepants Jun 2 '15 at 19:35
  • 1
    $\begingroup$ Conway's game of life is a cellular automaton kind of theory, a very discrete structure, like turing machines. So we can imagine that encoding one into the other is achievable. But the n-body problem is in a world of differential equations, continuous functions and such... I am a bit doubtful about encoding one into the other. What you might hope (though I doubt, and I am incompetent anyway) is that th non-existence of an analytic solution to n-body problem would be consequence of a contradiction internal to any theory that can express that problem, a bit like the proof of the halting problem. $\endgroup$ – babou Jun 2 '15 at 20:13
  • 1
    $\begingroup$ Actually your best chance is as a math problem. Physicists will tell you that n-body is chaotic, butterfly sensitive, so that quantum fluctuations will kill any long range encoding, or any predictiveness of the system evolution, which does not do too well for a Turing Machine. The math people may well say somehing worse, but I fortunately do not know what it is. $\endgroup$ – babou Jun 2 '15 at 21:18
9
$\begingroup$

There is some (somewhat scattered) research into the undecidability of the N-body problem from physics (in line with general study of undecidable phenomena in classical and quantum physics), which asks about calculating future trajectories or orbits of objects all subject to $n^2$ gravitational interactions; it has been studied for centuries including by e.g. Newton and Gauss. It basically reduces to a large array of differential equations and such systems have been proven to contain undecidability scenarios. However, this is a somewhat unusual crosscutting area of physics and mathematics that is not widely cited in either field and there do not seem to be widely cited single references either.

See e.g.

$\endgroup$
  • $\begingroup$ I haven't had a chance to fully read and understand that first paper, but it looks like it's probably as close to answering my questions as one could hope. So, I'm accepting this answer. $\endgroup$ – Shufflepants Jun 4 '15 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.