Qiaochu Yuan in his answer to this question recalls a blog post (specifically, comment 16 therein) by Terry Tao:

For instance, one cannot hope to find an algorithm to determine the existence of smooth solutions to arbitrary nonlinear partial differential equations, because it is possible to simulate a Turing machine using the laws of classical physics, which in turn can be modeled using (a moderately complicated system of) nonlinear PDE

  • Is this "it is possible" an application of a Newton thesis, much as the usual Church-Turing thesis, going along the lines of «if something is imaginably doable in real life, one can simulate it with the usual equations of physics», or has the simulation actually been actually carried out?

  • Does one need PDEs to simulate Turing machines, or are ODEs good enough?

  • $\begingroup$ We might consider a generalized "Church-Turing-Wheeler" thesis effectively maintaining that algorithms can describe physical processes, or more glibly, that computational physics is a legitimate activity. In one sense this is not far from Turing’s conception of an algorithm as a “mechanical process”, but at the same time it represents a closing of the putative loop joining physical, computational, and mathematical processes. $\endgroup$ Feb 15 '10 at 3:57
  • 2
    $\begingroup$ @Steve: This question seems relevant to your thoughts mathoverflow.net/questions/8396/… $\endgroup$
    – j.c.
    Feb 15 '10 at 4:07
  • 6
    $\begingroup$ I seem to remember hearing Smale and the dynamicists in Berkeley (his students, etc.) saying that the question of whether a given system was chaotic was undecidable. I think they had very specific equations, with a natural number parameter, and the set of parameters for which the system exhibited various forms of chaos was an undecidable set. $\endgroup$ Feb 15 '10 at 4:19
  • 4
    $\begingroup$ @Joel: I think this is contained in the classic paper by Blum, Shub, and Smale where they describe their model of computation over the reals. $\endgroup$ Feb 15 '10 at 4:35
  • 1
    $\begingroup$ "algorithms can describe physical processes" - what You call "physical processes" is some simplification and synthesis of real processes we observe in nature. It is disputable if physical model describes the whole reality or only important ( and simple) part of it . $\endgroup$
    – kakaz
    Mar 5 '10 at 18:12

ODEs are good enough. Your comment got me started digging.


I believe that the reference is to seminal work of Pour-El and Richards where they measure the computational contents of various types of classical systems of partial differential equations. They have a series of papers where they carry this out; I believe much of it can be found in their book Computability in analysis and physics (Perspectives in Mathematical Logic, Springer-Verlag, 1989). There are other approaches to this, but they all reach essentially the same conclusions. Pour-El and Richards have the advantage that they concentrate on specific systems that actually arise in physics, such as the wave equation.


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.