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

From: Isaac To (iketo2_at_netsacpe.net)
Date: 07/19/04 

Date: 19 Jul 2004 08:33:48 +0800

>>>>> "Peter" == Peter Olcott <olcott@worldnet.att.net> writes:

    Peter> You are looking at the original Halting Problem version:
    Peter> {int WillHalt()} here is the corrected version:

    Peter> void WillHalt(string SourceCode, string InputData) { if
    Peter> (TheProgramWillHalt(SourceCode, InputData))
    Peter> SecureOutput("The Program Will Halt"); else if
    Peter> (TheProgramWillNotHalt(SourceCode, InputData))
    Peter> SecureOutput("The Program Will Not Halt"); else
    Peter> SecureOutput("Security Has Been Breached, Take Corrective
    Peter> Action"); }

This doesn't solve the problem at all. Note that the program I give
you is a perfectly valid program (assuming that your WillHalt is a
valid program at all), and you answered "security breached" for it
rather than the supposed "yes" or "no". So your program is not a
solution for the halting problem. Or, put it in another way, if you
restrict the class of programs that your "WillHalt" program will
consider, then you can always find a "solution". E.g., you can say
that the program only detect direct loops like "while (1);" as "no"
and programs with no loops at all as "yes", all others are "security
breach", which would admits a very easy syntactical solution. The
whole point of the halting problem is that *any* program plus
input/output must be given an answer---*including* the ones that
contain the proposed program to solve the halting problem.

Regards,
Isaac.

Relevant Pages