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.
Asked By : Shufflepants
Answered By : vzn
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.
On an Undecidable Problem Related to Difference Equations with Parameters / Abramov
Decidability and Undecidability in Dynamical Systems 2.2.2 n-body problem / Hainry
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43181
0 comments:
Post a Comment
Let us know your responses and feedback