Navier-Stokes Fluid Computers

how-magneto-rheological-suspension-works-8947_2

Smart fluid

Terry Tao posted a very intriguing post on the Navier-Stokes equation, based on a recently uploaded paper Finite time blowup for an averaged three-dimensional Navier-Stokes equation.

The paper proved a remarkable negative answer for the regularity conjecture for a certain variants of the NS equations, namely (or, perhaps, more precisely) the main theorem demonstrates finite time blowup for an averaged Navier-Stokes equation. (This already suffices to show that certain approaches for a positive answer to the real problem are not viable.) The introduction ends with the following words.

“This suggests an ambitious (but not obviously impossible) program (in both senses of
the word) to achieve the same e ffect for the true Navier-Stokes equations, thus obtaining a negative answer to Conjecture 1.1 (the regularity conjecture for 3D NS equation)… Somewhat analogously to how a quantum computer can be constructed from the laws of quantum mechanics [Here Tao links to Benio ff's 1982 paper: "Quantum mechanical Hamiltonian models of Turing machines,"], or a Turing machine can be constructed from cellular automata such as “Conway’s Game of Life” , one could hope to design logic gates entirely out of ideal fluid (perhaps by using suitably shaped vortex sheets to simulate the various types of physical materials one would use in a mechanical computer). If these gates were sufficiently “Turing complete”, and also “noise-tolerant”, one could then hope to combine enough of these gates together to “program” a von Neumann machine consisting of ideal fluid that, when it runs, behaves qualitatively like the blowup solution used to establish Theorem 1.4.[The paper's main theorem] Note that such replicators, as well as the related concept of a universal constructor, have been built within cellular automata such as the “Game of Life.”

Once enough logic gates of ideal fluid are constructed, it seems that the main difficulties in executing the above program are of a “software engineering” nature, and would be in principle achievable, even if the details could be extremely complicated in practice. The main mathematical difficulty in executing this “fluid computing” program would thus be to arrive at (and rigorously certify) a design for logical gates of inviscid fluid that has some good noise tolerance properties. In this regard, ideas from quantum computing (which faces a unitarity constraint somewhat analogous to the energy conservation constraint for ideal fluids, albeit with the key di fference of having a linear evolution rather than a nonlinear one) may prove to be useful. (Emphasis mine.)

Interesting idea!

And what Tao does go well beyond an idea, he essentially implement this program for a close relative of the NS equation!  I am not sure if universal computing is established for these systems but the proofs of the finite-time blow up theorem certainly uses some computational-looking gadget, and also as Terry explains some form of fault-tolerance.

Somewhat related ideas (unsupported by any results, of course,) appeared in the seventh post “Quantum repetition” of my debate with Aram Harrow on quantum computing.  (See, e.g., this remark, and this one, and this one.) The thread also contains interesting links, e.g. to Andy Yao’s paper “Classical physics and the Curch-Turing Thesis.”  In addition to the interesting question:

Does the NS-equation in three-dimension supports universal (classical) computation,

we can also ask what about two-dimensions?

Can NS-equations in two dimension be approximated in any scale by bounded depth circuits?

One general question suggested there was the following: “It can be of interest (and perhaps harder compared to the quantum case) to try to describe classical evolutions that do not enable/hide fault tolerance and (long) computation.”

Another interesting comment by Arie Israel is: “I was surprised to learn that experimental fluid mechanics people had thought of this analogy before. Apparently the key name is ‘Fluidics’ and those ideas date back at least to the sixties.”

cih2

Update: Here is the first paragraph from a nice article by  Erica Klarreich entitled A Fluid New Path in Grand Math Challenge on this development in Quanta Magazine:

In Dr. Seuss’s book “The Cat in the Hat Comes Back,” the Cat makes a stain he can’t clean up, so he calls upon the help of Little Cat A, a smaller, perfect replica of the Cat who has been hiding under the Cat’s hat. Little Cat A then calls forth Little Cat B, an even smaller replica hidden under Little Cat A’s hat. Each cat in turn lifts his hat to reveal a smaller cat who possesses all the energy and good cheer of the original Cat, just crammed into a tinier package. Finally, Little Cat Z, who is too small to see, unleashes a VOOM like a giant explosion of energy, and the stain disappears.

And here is a follow up post on Tao’s blog (and a few more II, III), and a post on Shtetl Optimized.

The flip side

Update (June 14): It is worth noting that while the purpose of Tao’s program is to show finite-time blow up of the 3D Navier Stokes equations (as is often the case) these lines of ideas can potentially be useful also toward a positive solution of the regularity conjectures. Specifically, one can try to show that 3D Navier-Stokes equations do not support universal classical computation and even more specifically do not support classical fault-tolerance and error correction. Also here some analogy with quantum computation can be useful: It is expected that for adiabatic processes computation requires “spectral gap” and that gapped evolutions with local Hamiltonians support only bounded depth computation. Something analogous may apply to NS equations in bounded dimensions.

There are many caveats, of course,  the quantum results are not proved for D>1, NS equations are non-linear which weakens the analogy, and showing that the evolution does not support computation does not imply, as far as we know, regularity.

Three more remarks: 1) On the technical level an important relevant technical tool for the results on gapped systems with local Hamiltonians is the Lieb-Robinson inequality. (See, e.g. this review paper.)  2) for classical evolutions a repetition mechanism (or the “majority function”) seems crucial for robust computation and it will be interesting specifically to test of 3D Navier-stokes support it; 3) If computation is not possible beyond bounded depth this fact may lead to additional conserved quantities for NS, beyond the classical ones. (One more, June 28): It looks to me that the crucial question is if NS equations only support bounded computation or not. So this distinction captures places where circuit complexity gives clear mathematical distinctions.

About these ads
This entry was posted in Analysis, Applied mathematics, Computer Science and Optimization, Open problems and tagged , , , , , . Bookmark the permalink.

11 Responses to Navier-Stokes Fluid Computers

  1. In this context it’s worth mentioning Avi Wigderson’s thesis that P!=NP should be thought of as a proposed law of nature, a restriction on physical systems like the other laws of physics. In other words, the computational complexity of a Turing-complete fluid dynamical system would be very interesting.

    • Gil Kalai says:

      Dear Lior, yes, indeed this will be interesting. I think that so far the issue is that of computability (with some sort of fault-tolerance) and I do not see how coputational complexity comes to play. But surely whenever we can construct a “computer” based on some physical evolution or classes of evolutions the computational complexity issues are very interesting. The Church-Turing thesis regarded as a law of physics and various extensions of it (e.g. the efficient CH thesis, the efficient quantum CT thesis, and just the P!=NP) were considered by various researchers (but probably not by Church or Turing) and indeed it leads to interesting conceptual issues, (Another related issue is the P!=NP as a rule of modeling.) A famous case is the case of protein folding. Here is an interesting post about it in “my Qstate” http://mycqstate.wordpress.com/2014/01/31/simons-bootcamps/ .

    • Gil Kalai says:

      One more comment: If indeed the 3D NS equation (or some other equation of physical importance) supports universal computation we can ask what is the physical principle that forbid fluids from exhibiting memory and computation. We don’t expect, for example, that somewhere deep in the oceans high-quality literature or mathematics was created and stored. Stochasic behavior (or noise) of the initial condition or the equation itself is a commonly proposed answer but there are reasons to regard it as incomplete. (This actually came up in the long discussion after Terry’s 2007 post on the NS equation, for the related issue of using stochastic/quantum noise as a tool for proving regularity.)

      One possible answer (which is the motivating reason for the comments in the quantum repetition post) is that a principle of “no fault tolerance” (classic, in this case) need to be added to explain the no memeory/no computation phenomena. It is not so easy to put “no fault tolerance” on a formal ground and it may be harder in the classical case (where it does not universally apply.) Such a principle has a thermodynamical flavour.

    • John Sidles says:

      Thank you for these fine links, Gil. It’s not so easy to find concise, clear, early statements of the “Extended Church-Turing Thesis” (ECT), also known (?) as the “Efficient Church-Turing Thesis” … one such reference is Andrew Chi-Chih Yao’s Journal of the ACM article “Classical Physics and the Church–Turing Thesis” (2003).

      @article{Yao:2003aa,
      	Author = {Andrew Chi-Chih Yao},
      	Journal = {Journal of the ACM},
      	Number = {1},
      	Pages = {100--105},
      	Title = {Classical Physics and the {C}hurch--{T}uring {T}hesis},
      	Volume = {50},
      	Year = {2003}}

      If anyone knows of better/earlier references, please post them!

  2. John Sidles says:

    Gil, thank you for drawing attention to this outstanding work by Terry Tao. The parallels to quantum computing are indeed striking:

    The Skeptical Postulate is affirmed  For fluid and quantum systems alike, generic initial data can be simulated in PTIME.

    The Traditionalist Postulate is affirmed  For fluid and quantum systems alike, “a very small set of initial data” (in Terry Tao’s phrase) cannot be simulated in PTIME.

    The D-Wave Computational Model is affirmed  For fluid and quantum systems alike, the “Middle Earth” between the Skeptic’s universe and the Traditionalist’s universe is fertile ground for practical computation.

    Mainly for my own edification, I wrote a brief essay upon this affirmative trinity, titled There’s Plenty of Room in the Middle.

    For me it is is very enjoyable — and good news for young researchers too — that fluid dynamics and quantum dynamics are alike in that both provide plenty of room in the middle.

    Thank you Gil (as always) for this fine post.

  3. ashish soni says:

    Thanks for the awesome post. Indeed the parallels to quantum computing are mind blowing.

  4. Seth says:

    this was an excellent read, really enjoyed the parallels

  5. Choro Tukembaev says:

    June 20 Tao acquainted with the new method

    http://terrytao.wordpress.com/2007/03/18/why-global-regularity-for-navier-stokes-is-hard/

    The following article
    Taalaibek D. Omurov, “The Methods of a Problem Decision Navier-Stokes for the Incompressible Fluid with Viscosity” published at

    http://article.sapub.org/10.5923.j.ajfd.20140401.03.html

    claims to provide the proof of the existence and uniqueness of NS system

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s