On “external” definitions for computation
I recently stumbled upon a fascinating talk by the physicist Nima Arkani-Hamed on the The Morality of Fundamental Physics. (“Moral” here is in the sense of “morally correct”, as opposed to understanding the impact of science on society. Perhaps “beauty” would have been a better term.)
In this talk, Arkani-Hamed describes the quest for finding scientific theories in much the same terms as solving an optimization problem, where the solution is easy-to-verify (or “inevitable”, in his words) once you see it, but the problem is that you might get stuck in a local optimum:
The classical picture of the world is the top of a local mountain in the space of ideas. And you go up to the top and it looks amazing up there and absolutely incredible. And you learn that there is a taller mountain out there. Find it, Mount Quantum…. they’re not smoothly connected … you’ve got to make a jump to go from classical to quantum … This also tells you why we have such major challenges in trying to extend our understanding of physics. We don’t have these knobs, and little wheels, and twiddles that we can turn. We have to learn how to make these jumps. And it is a tall order. And that’s why things are difficult
But what actually caught my attention in this talk is his description that part of what enabled progress beyond Newtonian mechanics was a different, dual, way to look at classical physics. That is, instead of the Newtonian picture of an evolution of particles according to clockwork rules, we think that
The particle takes every path it could between A and B, every possible one. And then imagine that it just sort of sniffs them all out; and looks around; and says, I’m going to take the one that makes the following quantity as small as possible.
I know almost no physics and a limited amount of math, but this seems to me to be an instance of moving to an external, as opposed to internal definition, in the sense described by Tao. (Please correct me if I’m wrong!) As Arkani-Hamed describes, a hugely important paper of Emmy Noether showed how this viewpoint immediately implies the conservation laws and shows that this second viewpoint, in his words, is
simple, and deep, and will always be the right way of thinking about these things.
Since determinism is not “hardwired” into this second viewpoint, it is much easier to generalize it to incorporate quantum mechanics.
This talk got me thinking about whether we can find an “external” definition for computation. That is, our usual notion of computation via Turing Machines or circuits involves a “clockwork” like view of an evolving state via composition of some basic steps. Perhaps one of the reasons we can’t make progress on lower bounds is that we don’t have a more “global” or “external” definition that would somehow capture the property that a function F is “easy” without giving an explicit way to compute it. Alas, there is a good reason that we lack such a definition. The natural proofs barrier tell us that any property that is efficiently computable from the truth table and contains all the “easy” functions (which are an exponentially small fraction of all functions) must contain many many other functions (in fact more than 99.99% of all functions) . It is sometimes suggested that the way to bypass this barrier is to avoid the “largeness” condition, as for example even a property that contains all functions except a single function G would be useful to prove a lower bound for G if we can prove that it contains all easy functions. However, I think that to obtain a true understanding of computation, and not just a lower bound for a single function, we will need to find completely new types of nonconstructive arguments.