[Math] Simulating Turing machines with {O,P}DEs.

ap.analysis-of-pdesca.classical-analysis-and-odescomputational complexity

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?

Best Answer

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

Related Question