[PRL] Newton's Laws of Computation?

[Joe Marshall]

On 3/21/07, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>
> 6. I like Joe's suggestion but I will frankly admit that I am not
> sure how to use it. Perhaps the program synthesis people are the
> answer to this quest for the Floyd-Hoare world and HtDP plus NUPRL
> are the pieces of the puzzle for the Gödel-Church world.
>
> 6a. Joe: I take "Newton's laws" as a metaphorical question here, not
> as a full-fledged distinction. But it's worth thinking about
> Hamiltonian and Lagrangian. Perhaps the way engineers use it suggests
> something for the constructive part.

I thought that it might be metaphorical, but let me try another metaphor.

Suppose I posited the `laws of physics' as these:

  1.  F = ma

  2. Maxwell's equations

  3. The Navier-Stokes equation

These are all fine laws, all fundamental, all true, and almost
completely useless
in the context presented here.  You really can't go anywhere by trying
to combine
the Navier-Stokes equation with Maxwell's equation unless you already have a
very deep background in physics and a truly perverse desire to increase
complexity.

Instead of collecting a bunch of unrelated laws together, it is *much* more
interesting to contrast and compare unrelated *systems* of laws.  We learn
Newton's laws in high school, we may learn Lagrangian mechanics in college.
Newton's laws are based on a fundamental concept of force acting upon objects
with mass.  Lagrangian mechanics is based on the fundamental concept of
`least action' (minimizing the difference between the kinetic and potential
energy over time).  We can derive Newton's laws from the principle of
least action.
We learn a small amount of quantum mechanics in college.  We find that
Newton's laws are no longer valid when the quantities involved are extremely
small, so we have a different set of laws.  If we go further, we find
that we can
derive both Newton's laws and quantum mechanical laws from Hamiltonian
physics.  Going even further we end up with Noether's theorem, which gives us
some truly profound truths about physics that cannot be captured by simply
listing our favorite fundamental laws.

So I'm going to claim that you don't want to identify `Newton's laws
of computing'.
It is the wrong level of abstraction.  You want to identify the major systems of
computational theory.  *Then* in each theory, you want to find the fundamental
laws of that theory.  Finally, you want to compare and contrast the laws.

-- 
~jrm