Re: is induction unformalizable?

From: Hal Finney <hal.domain.name.hidden>
Date: Fri, 15 Jul 2005 09:29:55 -0700 (PDT)

One question I am uncertain about is this: how well could we test a
supposed halting-problem oracle (HPO) box?

In particular I wonder, suppose it turns out that P=NP and that further
there is an efficient algorithm to solve any NP problem. For those
unfamiliar with this terminology P means polynomial time, and we say
that problems in P can be solved efficiently. NP means nondeterministic
polynomial time, and essentially this means that for problems in NP, we
can efficiently test a purported solution for correctness. Whether P
is equal to NP or merely a subset of it is one of the major unsolved
problems of computer science.

But what if the aliens have solved it, and (somewhat to our surprise)
the answer is that every NP problem can be efficiently solved. And they
have embedded this NP solving algorithm (along with some other ones)
in the HPO box.

My concern is that to test the HPO box we could for example give it
a problem we have solved and see if it gets the answer. But success
might just imply that the HPO had substantially (but not astronomically)
greater computing power than the human race can bring to bear. Or we
could give it a problem we can't solve and then check the answer the
HPO gives, but if the answer is testable that would mean it is in NP,
and so even success in this area could be explained if P=NP as above.

It is much less philosophically challenging to imagine that P=NP than
to imagine that a true HPO could exist. Things would be different if
we ever get a proof that P < NP but we aren't in that situation now.

Are there other tests we could give, harder ones, that could give us
evidence that it was a true HPO, that could not be fooled by an NP solver?

My knowledge of these areas is pretty spotty. The only non NP problem I
know of offhand is the travelling salesman problem, finding the shortest
path visiting everyone of a set of cities with specified distances
between each pair. Proposed solutions cannot be tested efficiently,
as far as I know. If the box solved travelling salesmen problems for
us, it might be a boon to salesmen but we would not necessarily know if
we were getting truly optimal paths.

So in Wei's story, when the scientists go to test the HPO box, how strong
is the evidence that they can reasonably expect to get for it being a
real HPO? And I suppose a practical point arises as well; even if it
is not a true HPO, if it is nevertheless able to solve every problem we
give it, it's probably worth the money!

Hal Finney
Received on Fri Jul 15 2005 - 13:27:50 PDT