From: "Perry E. Metzger" <perry@imsi.com>
Date: Tue, 19 Jul 94 07:11:03 PDT
To: Jim choate <ravage@bga.com>
Subject: Re: GUT and P=NP
In-Reply-To: <199407191356.IAA28134@zoom.bga.com>
Message-ID: <9407191410.AA00961@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



Jim choate says:
> Ok Perry, I am not going to let you off that easily. Could you elucidate why
> you feel that such a GUT would not solve this problem even in
> principle?

Because the question "does P=NP" is a question made with respect to an
abstract mathematical model that has nothing to do with the laws of
physics or the "real world". The models it is based on are complete in
and of themselves. Even in a Newtonian universe in which all things
are deterministic, the mathematical concept of a non-deterministic
Turing machine is possible. The notion that physics breakthroughs
might help the problem is based on a complete and utter ignorance of
the way mathematics works. It is as though one could show that the
concept of one half doesn't "work" because in the real world you can
never cut something perfectly in half.

The notion also shows a complete ignorance of automata theory and
its motivations. Turing machines are ALREADY impossible. They exist
only in mens minds.  A real Turing machine could never be built,
period, because they require infinite tapes. A Turing machine is a
MODEL of computation. The notion of a non-deterministic Turing machine
was never based on the concept that such a thing could actually exist,
but on the idea of asking the question "assuming one existed, what
could one do with one that one couldn't do with a "normal" Turing
machine." It is a common exercise in automata theory -- one sees
many exercises of the form "what could you do with an N head M tape
Turing machine, and how much faster can it compute". Did you suppose
that just because one can't build oracles for unsolvable problems that
the mathematics of oracles would suddenly disappear into the void?

> If a GUT could answer definitively whether there were a many-worls
> interpretation this would definately address at least peripheral
> aspects of the P=NP problem.  It would also, necessarily, describe
> some limitations on computations and problem complexity.

It would not have the least effect, any more than one could settle the
question of whether the continuum hypothesis is true.

Perry