Re: [PO] Re: Proving a negative is hard

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

Date: Mon, 23 Aug 2004 09:41:44 +0200

Peter Olcott wrote:
> "Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message news:2olpanFc520fU1@uni-berlin.de...
>
>>This is kinda fun. Someone (Turing) claims "You can't do X",
>>you claim that "Your proof is wrong. -And- yes, you can do
>>X", others here claim that "No, -your- counterproof is
>>wrong", and then you respond "No, -your- counter claims
>>about mine are wrong".
>>
>>At this point, I'm really not sure where the burden of proof
>>lies. At any point, where does the burden of proof lie?
>>Is it "turtles all the way down"?
>
> I am familiar with that last reference, that was good.
> Actually Marc Goodman may have stated the burden
> of proof for proving a negative most succinctly. I will
> paraphrase what he said here. I am hoping that this
> paraphrase is accurate.
>
> In order to refute the proposed method for eliminating
> the undecidability of the Halting Problem, one must not
> merely find a contradiction, but, one must find a contradiction
> that shows that no Halt Analyzer can possibly exist.

I don't think you need to go two more levels of refutation
for that. That last clause seems to be the first level
statement of the goal of the proof. But I suppose it could
also be the goal of refuting a refutation (given that the
same original claim is supported weakly).

I'm just trying to figure out how to break the loop of "Yes,
it is.", "No, it isn't".

More to the content, I claim that in order to refute the
undecidability of HP, you either need to produce a
particular TM -and- prove that it does what you claim or
some other way which my imagination is currently unable to
reach. Finding an error in the proof doesn't refute the
claim (things can be true even if a particular proof has
errors). Changing the rules will just change the target. 

-- 
Mitch Harris
(remove q to reply)