Re: Alan Turing's Halting Problem is incorrectly formed (PART-TWO)

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 06/27/04 

Date: 27 Jun 2004 06:57:42 -0700

Dave Seaman says...

>> bool LoopIfHalts (bool YouSayItHalts)
>> {
>> if (YouSayItHalts)
>> while(true)
>> ;
>> else
>> return false;
>> }
>
>If YouSayItHalts is supposed to be a function, and if it is supposed to
>be able to predict whether I will say that LoopIfHalts halts, then it is
>not computable.

I think what Peter meant was something like this: Peter tells
you that he is going to ask a yes/no question, and that he will
provide the answer you give as input to the program LoopIfHalts
(translating "yes" into "true" and "no" into "false"). Then he
tells you that the question is: "After I feed your answer into
LoopIfHalts, will it halt?"

I think his point is to show that there are yes/no questions that
you can't answer---but that was pointed out to *him* long ago. Somebody
suggested

    Will Peter answer this question negatively? 

--
Daryl McCullough
Ithaca, NY

Relevant Pages