26
$\begingroup$

Is there a result showing that something along the lines of the three body problem is undecidable? Or are they known to be decidable or neither?

I mean problems along the lines of the following formulated in some suitable system:

Given masses, velocities and positions in 3 dimensions and a distance d (assume all expresses in rational multiples of G...ie G=1 so no using G as a non-computable oracle) can one decide whether, acting under the influence of Newtonian gravity only,

  1. Any of the point masses get within d units of another.
  2. Whether any of the masses ever get beyond d units from one of the other masses.
  3. Any of the bodies escapes to infinity relative to one of the others.
If necessary to make the problem well-defined one could stipulate that the initial positions are choosen to avoid ever allowing an exact collision of the point particles (also wonder if that is decidable).

More generally is their some result letting one embed arbitrary computations into a system of bodies acting only under gravity?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
14
$\begingroup$

The paper Undecidability in $\mathbb{R}^n$: Riddled Basins, the KAM Tori, and the Stability of the Solar System by Matthew W. Parker (Philosophy of Science 70 (April 2003), 359–382) comes close to answering your question. A classical problem in the same spirit as your question is the stability of the solar system. As Parker notes, there are quite a few informal claims in the literature that this type of problem is uncomputable, but for the most part, they gloss over the crucial question of how to define computability in the context of real numbers (sometimes referred to as real computation or computable analysis).

Parker offers his own approach to real computation and analyzes the question accordingly. However, as far as I know, neither Parker nor anyone else has analyzed the setup you suggested, which is to restrict the set of initial conditions to the rational numbers, and ask if the subset of (say) "stable configurations" is computable in the traditional sense.

Improve this answer
$\endgroup$
17
$\begingroup$

In Church's thesis meets the N-body problem Warren Smith argues that unsimulable physical systems exist in Newton’s laws of gravity and motion for point masses, because an uncountably infinite number of topologically distinct trajectories are possible in a finite time.

See also Decidability and Undecidability in Dynamical Systems by Emmanuel Hainry.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Ok, that's a good answer for 2 and 3 but I was vaguely aware that that passing close together was an issue and question 1 was designed specifically to deal with that objection as this kind of problem requires arbitrarily close approaches to generate the simulation problem. So I'm still curious about that answer. $\endgroup$
    – Peter Gerdes
    Commented Oct 16, 2021 at 15:15
  • 1
    $\begingroup$ I'm not sure either of these references addresses the stated question. Smith's paper leans heavily on uncountability, but the OP specifies rational initial positions and velocities. Hainry refers to reference [13] for details of the undecidability results, but [13] focuses on analytic functions, which again does not seem to match the OP's setup. $\endgroup$
    – Timothy Chow
    Commented Oct 17, 2021 at 22:54
  • $\begingroup$ That's a very good point about Q. It hadn't occured to me when first reading it but the way Smith's argument works requires finding initial conditions by continually refining some starting conditions to ensure each of infinietly many interactions comes out in the correct way. Smith shows that this process is effective so we can get computable reals as parameters which give rise to this problem but no guarantee it's possible in Q. $\endgroup$
    – Peter Gerdes
    Commented Oct 19, 2021 at 17:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .