Re: Halting Problem for Humans

Peter Olcott says...

So in order for H to avoid making a mistake its only possible choice is to
refrain from entering either of these two states.

By definition, l(L,L) is the state in which H figures out that
L does not halts on input L. It's not that H figures out, and
then *decides* to enter that state. Figuring out and entering
the state l(L,L) are *equivalent*.

So the only possible correct choice would still be to refrain
from answering the question

The way that I've set it up, all that is important is that
H *know* the answer. If it knows the answer, then that means
that H has entered the state l(L,L). If he has not entered
that state, then that means that H *doesn't* know the answer.

thus showing that the question of halting is ill-formed,
according to the definition of ill-formed questions.

It only shows that H doesn't know the answer.

Since there exists no correct answer within the solution set.

The solution set in this case consists of three possibilities:
(1) H knows that L(L) halts, (2) H knows that L(L) does not halt,
or (3) H does not know whether L(L) halt, or not.

His answer in this case is (3). He doesn't know. That doesn't
mean that the question is ill-formed.

In this case the solution set is narrowly defined not as the
question "Does the program Halt, (YES or NO)?

No, that's exactly the question being posed to H.
In this case, H isn't required to *answer* at all.
It's just supposed to try to figure out the answer.

You are saying that H knows that answer, but refrains
from entering the state l(L,L). But if H knows the answer,
then what was the first moment in which it figured out the
answer? The state he was in at that moment is by definition
l(L,L).

Maybe you are saying that it is undecidable whether H is
in state l(L,L) or not? So you are replacing one unsolvable
problem by another.

--
Daryl McCullough
Ithaca, NY

.

Relevant Pages

  • Re: Peter Olcotts Source of Confusion
    ... Actually when the one mistake is saying that the halting ... >were redefining what the Halting Problem was. ... >the link will halt or not. ... odd nor even. ...
    (sci.logic)
  • Re: Halting problem undecidable or semidecidable?
    ... > There is a fundamental difference between saying yes and saying no. ... > considered it in terms of languages, you can tell if a given program ... > belongs to the language HALT. ... converses are also undecidable. ...
    (comp.theory)
  • Re: Alan Turings halting proof is incorrectly formed PT Herc
    ... > You are right in saying that there could be programs written that will ... > understanding of the rigorous mathematical foundations of a subject and/or ... > regarding HALT. ... Theoretical computer science is not concerned with this, ...
    (sci.math)
  • Re: Alan Turings halting proof is incorrectly formed PT Herc
    ... > You are right in saying that there could be programs written that will ... > understanding of the rigorous mathematical foundations of a subject and/or ... > regarding HALT. ... Theoretical computer science is not concerned with this, ...
    (sci.logic)
  • Re: Alan Turings halting proof is incorrectly formed PT Herc
    ... > You are right in saying that there could be programs written that will ... > understanding of the rigorous mathematical foundations of a subject and/or ... > regarding HALT. ... Theoretical computer science is not concerned with this, ...
    (comp.theory)