Re: Proving a negative is hard

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 08/19/04 

Date: Thu, 19 Aug 2004 09:46:16 +0200

Peter Olcott wrote:
> "wgempel" <wgempel@yahoo.com> wrote in message news:d6b61672.0408180940.2a041d24@posting.google.com...
>
>>The key point you seem to be missing is that there is no "calling"
>
>>In any event LOOPIFHALT would have the desired properties just by not
>>including the sections of HALT that implement these measures. You
>>haven't even come up with measures which influence the output of HALT.
>> They are simply extraneous code that can be removed in the
>>construction of LOOPIFHALT.
>>
>>To be even more clear:
>>
>>There is no mechanism for constructing HALT which can prevent the
>>construction of LOOPIFHALT. We could play intricate games of
>>extending the model and then trying to find the correct counterploys,
>>but it would be a waste of time. Unless you wish to dispute the
>>Church-Turing Thesis, you should recognize that no modification of the
>>TM model will help.
>
> It seems that you are merely yet another one of the dozen's of people
> that just don't quite get the idea of proving a negative. You must not
> merely derive a means whereby Halt can be thwarted. You must
> derive the reasoning to show that halt can not exist.

Right. The main way to do this is, for any possible assumed
arbitrary unspecified generic TM that supposedly computes
the Halt function, show that that assumption results in a
contradiction.

> In other words you must show that halt can not possibly avoid
> being thwarted by any means what-so-ever. I only have to prove
> that it can work in one case.

I'm not sure what you mean by "one" case. One way to prove
an existence thm is by constructing an example and proving
that the example satisfies all the necessary properties.
The problem is that this "one" case, happens to take a
parameter (OK, two params) which means it has to work over
all possible instantiations of the parameters.

Another way to do it is to deny a forall of a negative, but
that involves more cases.

> You must show that it is impossible in each and every case.

The assumption of "arbitrary" takes care of that. 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages