11 ms·

One thing I haven't seen being described, at least for dummies like me, is the n-body problem's relation to the halting problem. Also, the difficulty of findin

One thing I haven't seen being described, at least for dummies like me, is the n-body problem's relation to the halting problem. Also, the difficulty of finding a delta-v/time efficient trajectory between two locations in such a system. https://space.stackexchange.com/q/64392/38733 https://space.stackexchange.com/q/64392/38733 It might be cool to see a competition with a problem like that Is the fact that a fully expanded formula branches out exponentially with every step, since each future motion/velocity component of a body depends on all past components of all other bodies, which in turn depend on other components etc. relevant to that?

mock-possum 3y ago
Why should there be a relation between the n-body problem and the halting problem?
- 7373737373 3y ago
  It is possible to write an n-body simulation program that only halts its step-by-step iteration if one body collides with another (specific) body or reaches a specific location. Now, is it possible to tell analytically, without running the program, if it halts (at an arbitrary point in the future, or within a certain number of steps)? If so, the n-body/trajectory finding problem is solved, efficiently. But (n>=3) n-body systems have been shown to be chaotic, depending sensitively on the initial state of the system, so this doesn't seem to be generally possible without brute force computation. So what about this chaos/mathematical-logical-temporal relation/equations between state variables (body positions and velocities) make this halting problem (effectively/efficiently) unsolvable, and how does it relate to other computational systems where the halting problem applies, like turing machines? Edit: https://cs.stackexchange.com/questions/43181/is-the-unsolvability-of-the-n-body-problem-equivalent-to-the-halting-problem https://cs.stackexchange.com/questions/43181/is-the-unsolvab...

mock-possum 3y ago

Why should there be a relation between the n-body problem and the halting problem?

7373737373 3y ago
It is possible to write an n-body simulation program that only halts its step-by-step iteration if one body collides with another (specific) body or reaches a specific location. Now, is it possible to tell analytically, without running the program, if it halts (at an arbitrary point in the future, or within a certain number of steps)? If so, the n-body/trajectory finding problem is solved, efficiently. But (n>=3) n-body systems have been shown to be chaotic, depending sensitively on the initial state of the system, so this doesn't seem to be generally possible without brute force computation. So what about this chaos/mathematical-logical-temporal relation/equations between state variables (body positions and velocities) make this halting problem (effectively/efficiently) unsolvable, and how does it relate to other computational systems where the halting problem applies, like turing machines? Edit: https://cs.stackexchange.com/questions/43181/is-the-unsolvability-of-the-n-body-problem-equivalent-to-the-halting-problem https://cs.stackexchange.com/questions/43181/is-the-unsolvab...