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

From: Isaac To (iketo2_at_netscape.net)
Date: 07/18/04 

Date: 18 Jul 2004 23:21:52 +0800

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

    Peter> int WillHalt() will terminate in all cases. It will not go
    Peter> into the infinite loop because it will not determine that
    Peter> LoopIfHalts() will halt. It also does not determine that
    Peter> LoopIfHalts() does not halt, this only leaves UNKNOWN,
    Peter> which is still a halting condition.

I'm really unsure what you are doing. Why any solution of halting
problem can return UNKNOWN given valid input (i.e., a program)? A
program either halts or not halts, it cannot be "in between". If you
have any such program that can return UNKNOWN for any valid input
(i.e., any program that takes no input) it cannot be a correct answer
of the halting problem, by definition. If you neglect that, you have
the simplest solution to the halting problem "int WillHalt(string Src,
string Input) { return UNKNOWN; }".

Regards,
Isaac.

Relevant Pages

  • Peter Olcotts Source of Confusion
    ... Peter Olcott is so thoroughly confused by the proof of the ... to track down exactly what the source of his confusion is. ... code for an alleged program H that solves the halting problem, ... input x, then loop forever, otherwise halt". ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is incorrectly formed
    ... Peter is mixing up several things. ... Now the question (Halting problem) actually is not "Does TM M halt on ...
    (sci.logic)
  • Halting Problem: Give up
    ... The following is one of latest messages of Peter in comp.lang.c++ ... Halting Problem is and what the Proof is and how they are connected. ... >> and in a deterministic way determine if all algorithms ever come to an halt. ... >> cannot be correctly analyzed by this assumed algorithm. ...
    (comp.theory)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... Peter> way to construct a solution to the Halting Problem that can ... Peter> not possibly succeed. ... it cannot be a correct solution to the halting problem, ... machine you gave to neither halt sometime nor never halt. ...
    (comp.theory)
  • Re: simple and beauty strategy
    ... the halting problem is a decision problem ... Alan Turing proved in 1936 that a general algorithm to solve the ... the program will eventually halt when run with that input. ... undecidability of a problem in the lambda calculus had already been ...
    (rec.gambling.lottery)