Church’s thesis meets the N-body problem

摘要

“Church’s thesis” is at the foundation of computer science. We point 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; physics is unsimulable. 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–you must read the full text—and interpreting our results is not trivial.