**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 effect 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 Benioff'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 difference 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.”

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 post on Shtetl Optimized.

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.

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/ .

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

provingregularity.)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.

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 ACMarticle “Classical Physics and the Church–Turing Thesis” (2003).If anyone knows of better/earlier references, please post them!

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 affirmedFor fluid and quantum systems alike, generic initial data can be simulated in PTIME.The Traditionalist Postulate is affirmedFor 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 affirmedFor 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

bothprovide plenty of room in the middle.Thank you Gil (as always) for this fine post.

Dear John, your question reminded me of a paper I wrote in 2002 “Social choice without rationality http://www.najecon.org/naj/cache/391749000000000455.pdf where there is one example of “middle-ground based rationality” rather than “optimization-based rationality.” Formally, individuals have a “utility function” on alternatives but when they have to choose between a subset of alternatives they choose the one in the middle. I found this example appealing and I also had an idea to devise a certain sport based on it.

Gil: Has any progress been made on the open questions in this “social choice” paper?

Dear Joe, For conjecture A beside Shelah’s result there was a very nice result by Eyal Beigman Extension of Arrow’s theorem to symmetric sets of tournaments For conjecture B beside my paper on social indeterminacy there is a recent result by Mossel and me Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory .

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

this was an excellent read, really enjoyed the parallels