21
$\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.

Improve this question
$\endgroup$
12
  • 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
    Commented Jun 2, 2015 at 17:18
  • 1
    $\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
    Commented Jun 2, 2015 at 18:08
  • 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
    Commented Jun 2, 2015 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
    Commented Jun 2, 2015 at 21:18
  • 1
    $\begingroup$ @MaiaVictor It seemed to me that that should be so. But it's little more than conjecture unless some one's proven it. It could easily turn out that with only gravity alone, arbitrary calculations can't be computed due to instabilities. It could also turn out that it's only Turing complete in certain dimensions; only in 3 or greater but not in 2. And it might also not be a double implication (though this one I'm highly skeptical of). $\endgroup$
    – Shufflepants
    Commented Nov 17, 2016 at 22:37

3 Answers 3

Reset to default
17
$\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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jun 4, 2015 at 14:13
0
$\begingroup$

The challenge isn’t to prove that you can create a Turing-complete system only by using gravity. You would have to demonstrate that the N-body problem itself arises from an undecidable problem that is equivalent to the halting problem within a Turing-complete system. This goes beyond showing that a computer with a minimal error could be built with heavy objects, as that could still be true even if the N-body problem were entirely predictable and decidable. Instead, you must reduce a problem like the halting problem to the N-body problem, translating it into a question of whether the system's stability or behavior over time can be determined exactly when the reduced problem is decidable.

Improve this answer
$\endgroup$
-2
$\begingroup$

Almost certainly it is possible to build (conceptually) a Turing machine using gravitational components. A google search of "square orbits" shows that the flow of particles in a gravitational field can be manipulated into any desired shape: a stream of particles might correspond to the tape in a Turing machine flowing past the "head". A particle is present for a 1 and missing for a 0. For the logic gates required see the wikipedia article on "Fluidics", under "logic": it is not too hard to imagine a similar scheme working with gravity. For example a particle could be orbiting one of two close spheres: a passing particle on "the tape" could nudge it into the orbit of the other sphere - a flip-flop memory circuit.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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