8
$\begingroup$

When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these lines?

For context, I am a researcher who works on physical simulations, so of course I'm aware that many partial differential equations (PDEs) that would arise in nature (e.g. the heat equation, wave equation, etc) can be approximated by numerical methods like finite elements, and that for many PDEs a solution can be estimated to arbitrary accuracy given enough computation (by decreasing the space and time step sizes).

However, I also know that proving convergence of finite element methods is notoriously difficult for PDEs of any appreciable complexity, even "easy" PDEs like the mean curvature flow that describes the shape of a soap film. I also know that many "Zeno-type" situations arise in practice in physical systems, such as Euler's disk or inelastic collapse. Is there reason to believe that the solutions to all PDEs, or at least all PDEs that would arise in nature, are Turing-computable?

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael May 5 '16 at 11:36
4
$\begingroup$

The branch of mathematics and computer science that studies these questions is computable mathematics. The general answer is that things tend to be computable. I would add to that the observation that it often takes some work to establish computability. For instance, you mention finite element methods and the problems with their convergence. This proves absolutely nothing about computability of PDEs because there are, or might be, other methods for solving PDEs.

Some references that migth interest you, in order of relevance:

$\endgroup$
  • $\begingroup$ Thanks! The nlab page mentions that the Schroedinger Equation is computable, and if that result is general enough in the types of Hamiltonians permitted it would more or less completely settle the matter in my mind. I'all have to look into the references. $\endgroup$ – user168715 May 5 '16 at 14:05
  • 1
    $\begingroup$ Does sciencedirect.com/science/article/pii/S0885064X06000446 help? $\endgroup$ – Andrej Bauer May 5 '16 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.