Re: Can you find anything wrong with this solution to the Halting Problem?

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 07/14/04 

Date: Wed, 14 Jul 2004 04:01:01 GMT

In sci.logic, Peter Olcott
<olcott@worldnet.att.net>
 wrote
on Tue, 13 Jul 2004 03:08:13 GMT
<xmIIc.88218$OB3.37345@bgtnsc05-news.ops.worldnet.att.net>:
>> It tells the owner of the private key that a program halts.
>> No other program -- including LoopIfHalts() -- would be able
>> to do much with that information, though part of the problem
>
> Yet even though this proof is not refined, it still does prevent
> LoopIfHalts() from providing the means to show that WillHalt()
> will not always work correctly. In other words no matter how
> inelegant my proof may be, it still proves its point.

Not quite.

If your blocker is what I think it is, you've merely made the
problem more computationally intensive, requiring LoopIfHalts().
to crack the key prior to proceeding with the contradictory
construct.

It's always possible to crack a key by brute force, if one has
enough time. Of course, 2^128 picoseconds = 3.403 * 10^26 years,
which is well beyond the predicted heat death of the Universe
(5 * 10^10 years).

>
>> with the proof is that it doesn't say how long LoopIfHalts()
>> (or, for that matter, WillHalt()) will take, it merely says
>> that it can or cannot be done.
>
> To correctly refute the original proof, all that I am required
> to do is to show how I can remove the basis of the original
> proof. The details that you cited do not make any difference
> in this end.

But you have not removed them.

>
>> A halting test that takes until the heat death of the
>> Universe to figure out whether 'while(1) {}' halts or not
>> isn't going to be that useful. :-)
>>
>> I'm not entirely sure what to make of it beyond the fact that
>> Peter has not refuted the proof, merely inserted an interesting
>> blocker into one of the proof's tactics (namely, the duplication
>> of the input).
>
> No, I have eliminated its entire basis. If I have not
> eliminated its entire basis, then show what is left of
> its basis, and quit the red herrings. Even if it the
> WillHalt() function takes one second less than forever,
> this still refutes the original proof.
>

But you have not eliminated its entire basis. If
LoopIfHalts() can deduce what the result of WillHalts(),
the proof fails -- though it might take till the heat
death of the Universe squared to do so.

Such is mathematics. 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages