Re: Is the Halting Problem merely an ill-formed question?


Peter Olcott wrote:
"R. Srinivasan" <sradhakr@xxxxxxxxxx> wrote in message
news:1161613846.883708.234520@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


On Oct 23, 6:03 pm, "Peter Olcott" <NoS...@xxxxxxxxxxxxx> wrote:
"R. Srinivasan" <sradh...@xxxxxxxxxx> wrote in
messagenews:1161586978.148178.180730@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx



On Oct 22, 7:09 pm, "Peter Olcott" <NoS...@xxxxxxxxxxxxx> wrote:
An ill-formed question is any question that requires an answer from a
solution
set where no correct answer exists within this solution set. One example
of
an
ill-formed question is the following: "How tall are you green or blue?".

At the instant the question is asked, neither YES nor NO is a correct
answer that can be made accessible. But *later*, it turns out that
there will be an answer that is either YES or NO

I don't think so. Not for the scenario that I am envisioning.

int WillHalt(string SourceCode, string InputData) {
if ( TheProgramWillHalt(SourceCode, InputData) )
return TRUE;
else
return FALSE;

}void LoopIfHalts(string SourceCode) {
if ( WillHalt(SourceCode, SourceCode) == TRUE )
while (TRUE) // loop forever
;
else
return;

}LoopIfHalts(LoopIfHalts);

In this case neither TRUE nor FALSE ever provides a correct answer. The
result
of any answer is ALWAYS toggled to make the result incorrect.

You say the result is made "incorrect". That means you have already
conceded that there is a determinate"result", It is just that this
result cannot be correctly predicted. If you think of the program
execution as a time-dependent process, what happens is that a certain
prediction is made by WIllHalt and then LoopifHalts proceeds to do the
opposite later on, *after* "seeing" this prediction. This is what I
mean by saying that *after* the prediction has been made, there is a

Yet a correct form of WillHalt() would be required to forever refrain from
making such a prediction, determining in advance that any such prediction must
ALWAYS fail.

final outcome, either Halt or not-Halt, that contradicts the prediction
(making it incorrect, in your words). The problem is that classical
logic requires that a determinate truth value, reflecting the final
outcome (either Halt or not-Halt) must exist at *all* times, even
*when* the prediction is being made by Willhalt (in say, any particular
execution). So the paradox is why WIllHalt cannot get it right even by
guesswork -- after all, one of either Halt or not-Halt must be correct

Because within the specific context of its two possible states there exists
neither state that forms a correct answer. Since the answer is required to be
provided only in terms of its two possible states, and neither state forms a
correct answer, therefore the question of halting meets the definition of an
ill-formed question. An ill-formed question is any question where a correct
answer does not exist within the required solution set.

even when the question is being asked of WIllHalt.

The NAFL position is completely different. If the outcome is truly not
predictable (as either Halt or not-Halt), then there is no determinate
truth value till the human mind perceives in some way that one of these
outcomes must be true (maybe by actually conducting a computational
experiment,though this is not necessary). NAFL would take the stand
that prior to this perception by the human mind, the TM neither halts
not non-Halts.,i.e., there is no determinate truth value independent of
the human mind, unlike classical logic. But this would be a

Is this something like the quantum paradox?
http://www.faqs.org/docs/qp/chap08.html

Yes. Actually NAFL provides a resolution of the quantum paradoxes, like
the Schrodinger cat paradox, by explaining what the superposed state of
alive-and-dead actually means. But in the case of a TM, a superposed
state of halts-and-not-halts cannot possibly exist, because a TM must
either halt or not-halt by definition.

Regards, RS

.

Relevant Pages

  • Re: Is the Halting Problem merely an ill-formed question?
    ... set where no correct answer exists within this solution set. ... prediction is made by WIllHalt and then LoopifHalts proceeds to do the ... one of either Halt or not-Halt must be correct ... truth value till the human mind perceives in some way that one of these ...
    (sci.logic)
  • Re: Is the Halting Problem merely an ill-formed question?
    ... prediction is made by WIllHalt and then LoopifHalts proceeds to do the ... final outcome, either Halt or not-Halt, that contradicts the prediction ... truth value till the human mind perceives in some way that one of these ...
    (sci.logic)
  • Re: Implausibility continued (in C)
    ... sufficiently large number and seeing if the program is in the halt state. ... explanation is incomplete and the behavior is not predictable. ... you would never get the prediction of it halting ... inability to predict the behaviour a finite amount of steps in the ...
    (talk.origins)
  • Re: Implausibility continued (in C)
    ... sufficiently large number and seeing if the program is in the halt state. ... explanation is incomplete and the behavior is not predictable. ... you would never get the prediction of it halting ... inability to predict the behaviour a finite amount of steps in the ...
    (talk.origins)
  • Re: Implausibility continued (in C)
    ... sufficiently large number and seeing if the program is in the halt state. ... predict potentially an infinite amount of steps ahead. ... you would never get the prediction of it halting ... x being the number of further iterations that would ...
    (talk.origins)