28
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\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$
    – Steve Huntsman
    Commented Feb 15, 2010 at 3:57
  • 2
    $\begingroup$ @Steve: This question seems relevant to your thoughts mathoverflow.net/questions/8396/… $\endgroup$
    – j.c.
    Commented Feb 15, 2010 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$
    – Joel David Hamkins
    Commented Feb 15, 2010 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$
    – François G. Dorais
    Commented Feb 15, 2010 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
    Commented Mar 5, 2010 at 18:12

2 Answers 2

Reset to default
28
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ The link is broken. $\endgroup$
    – user76284
    Commented Dec 21, 2020 at 6:50
  • $\begingroup$ While I try to dig up the original reference, chemical reaction network ODEs work: arxiv.org/abs/1811.10361 $\endgroup$
    – Steve Huntsman
    Commented Dec 21, 2020 at 13:47
  • 1
    $\begingroup$ Was it Robust simulations of Turing machines with analytic maps and flows (2005) by Daniel Graça, Manuel L. Campagnolo, and Jorge Buescu? I would add the full citation to the answer, in case the link breaks again in the future. $\endgroup$
    – user76284
    Commented Dec 21, 2020 at 19:46
  • $\begingroup$ @user76284-that smells right, adding the DOI $\endgroup$
    – Steve Huntsman
    Commented Dec 21, 2020 at 21:00
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .