Church's thesis meets the N-body problem
 Warren D. Smith

Abstract
``Church's thesis'' is at the foundation of computer science.  It is
pointed out that with any particular set of physical laws, Church's
thesis need not merely be postulated, in fact it may be decidable.
Trying to do so is valuable.  In Newton's laws of physics with point
masses, we outline a proof that Church's thesis is false. But with
certain more realistic laws of motion, incorporating some relativistic
effects, the Extended Church's thesis is true.  Along the way we prove
a useful theorem: a wide class of ordinary differential equations may
be integrated with ``polynomial slowdown.'' Warning: we cannot give
careful definitions and caveats in this abstract, and interpreting our
results is difficult.

Keywords
Newtonian N-body problem, Church's thesis, computability, numerical
methods for ordinary differential equations.