You missed my point, entirely. I'm talking about integer and/or rational coordinates, not real numbers, so even the 2-body case boils down to drawing conic sections on an integer lattice -- a problem that took computer graphics people tens of years to fully come to grips with. The whole point of mentioning Poincaré was to acknowledge that we weren't going to "solve" a >3-body problem -- merely simulate it. This is no more, and no less, than simulating a Turing Machine computation instead of solving the Halting Problem. I just wanted to figure out a way to simulate such a computation more accurately. It also occurred to me since yesterday that the better proof of unsolveability would be to reduce the 2D N-body (in integers) problem to Hilbert's Tenth Problem, which was found to be unsolveable in 1973; "Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers." http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem I've looked at a lot of papers about N-body simulation codes using floating point arithmetic, and one of the biggest problems is to preserve the various conservation laws during the simulation. Even the slightest losses or gains in one of the conservation laws leads to non-physical behavior over a large number of iterations. These non-conservations are a bigger problem than accuracy if you are looking for the characteristics of long-term behavior -- e.g., whether one or more bodies is ejected from the system & never comes back. BTW, in my description, I talked about the representation of the _position_ coordinates, but not the representation of the _velocity_ coordinates. These, too, would have to be integers or rational numbers. While it probably makes the most sense to represent the position coordinates rather directly, the best representation of the velocity coordinates is very much up in the air. One might want to represent integral _inverse_ velocities, e.g., instead of the velocities themselves. At 08:27 PM 6/10/2011, Cordwell, William R wrote:

The planar Newtonian 2-body problem is solvable exactly by switching to the center of mass coordinate system. It is known that the general N > 2 body system is not solvable exactly.

In the CM coordinate system, the two momentum vectors are opposite, so assuming planar should be no restriction.

----- Original Message ----- From: Henry Baker [mailto:hbaker1@pipeline.com] Sent: Friday, June 10, 2011 07:18 PM To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Exact N-body simulations?

All this talk of Gaussian integers reminded me of a problem that I'd dearly love to see solved.

Consider N bodies, each with integer masses. Start them in initial positions in a 2D (for the moment, there's plenty of complexity in 2D) which are on integer coordinates. The attractive Newtonian gravitation force is proportional to m*m'/(dx^2+dy^2), so this force is rational. We need to compute new positions for each of the bodies in such a way that all the conservation laws are preserved exactly (if this is possible), yet the number of bits required doesn't grow too quickly (see below).

We need to preserve the total energy, we need to preserve momentum & angular momentum, & we might like to preserve information (the system is reversible).

Note that we don't necessarily require that delta-t be constant, although if it isn't, we may need to have another counter to represent the "clock" -- i.e., the global time.

I don't know how to do this even in the 2-body case, but the Minsky circle hack may provide some guidance -- if we could get the two bodies to each draw a Minsky circle while revolving around one another, then we'd have a good start on the problem.

In addition to solving the problem of finite arithmetic, we also need to figure out what happens in collisions. Taking a cue from Fredkin, we should probably have 100% elastic collisions in order to ensure reversibility.

How does this square with Poincaré ? Well, I'm assuming that my N-body problem for finite N is Turing complete, so with enough bodies and enough "tape" (empty space), we should be able to compute any computable function. Minsky already provides one potential representation with his "counter machines". So we want a reasonably "efficient" Turing Machine (or Counter Machine) simulation so that we aren't wasting more than a fixed fraction of the bits required to represent the state (N pairs of integers or N gaussian integers).

Has anyone attempted this sort of exact simulation before?