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

stephen_at_nomail.com
Date: 06/27/04 

Date: 27 Jun 2004 15:12:15 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
:> : bool LoopIfHalts (bool YouSayItHalts)
:> : {
:> : if (YouSayItHalts)
:> : while(true)
:> : ;
:> : else
:> : return false;
:> : }
:>
:> : This function would both compile and run correctly.
:>
:> But this function does not solve the Halting problem. This function

: It is not supposed to SOLVE the Halting Problem it is supposed
: to be a simplified EXAMPLE OF the Halting Problem.

But it is not an example of the Halting Problem. The Halting Problem
is supposed to determine if a program halts or not by examining the
program and the input.

: The point is that the Halting Problem has been defined to have
: no possible correct answer. Daryl tried to cheat for a while
: and re-define the problem so that his solution would fit, but
: I have already called him on this cheating.

No, the Halting Problem has a correct answer. Every program either
halts or does not halt for a given input. There is no other option.
You are confusing things by bringing up the Liars Paradox. The Liars
Paradox demonstrates that some statements are neither true nor false.
By comparing the Halting Problem and the Liars Paradox you seem to be
claiming that some programs neither halt nor loop, but that is simply
not possible.

: It is incorrectly formed specifically because it has been defined
: to have no possible correct solution, and all problems that are
: defined to exclude all possible solutions are incorrect problems.

It has a solution. We just cannot compute what the solution is.
This is different than the Liars Paradox which has no solution.

Stephen

Relevant Pages

  • Re: Is the Halting Problem merely an ill-formed question?
    ... It either halts or it doesn't; ... THEY CAN write on their tapes. ... if (MalignantSelfReference(SourceCode, InputData)) ... that the Halting Problem is solvable, I am only at most attempting to show the ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... It does not go into an infinite loop if and only if it halts. ... >>This is how the Halting Problem is defined. ... It is not the analogy that is crucial. ... >>the student's could determine their own grades. ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... It does not go into an infinite loop if and only if it halts. ... >>This is how the Halting Problem is defined. ... It is not the analogy that is crucial. ... >>the student's could determine their own grades. ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is incorrectly formed (PART-TWO)
    ... [halting problem without assuming the existence of a machine solving the ... Where did I assume the existence of a machine solving the ... > which we mean that it outputs 1 if E halts when given. ... the construction goes trough no matter what "hypothetical" ...
    (sci.logic)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... of the Halting Problem ever actually existed. ... Proving a positive provides only showing a single example. ... presumed the third step from the incorrect second step. ... > TM with impossible properties (it halts iff it doesn't). ...
    (sci.logic)