Re: Halting Problem for Humans


Daryl McCullough wrote:
The Halting problem is ultimately about the failure of prediction.

No, it isn't. In the TM universe there simply is no time.
The paradigm is functional and abstract. All the strings
in that paradigm bear all their relationships to each other
simultaneously and eternally. There CANNOT be *pre*diction;
there is just diction.

No program can have perfect ability to predict the future behavior of
all other programs.

Or to 'dict it either. In particular, it doesn't even need to
'dict the FULL behavior. It specifically can't predict halting
or not. This matters a lot because UNTIL it halts, the program
truly CANNOT be said TO HAVE "behaved" at all. It could behave
one way or another; the jury is still out. The whole import
of the halting problem is that in the GENERAL case,
Not Halting does NOT COUNT as a
"behavior"! If you (or rather, WHEN you, since you sometimes can)
confirm that TM M does Not halt on input I, then, yes, that
can constitute partial description of M's behavior.
If it does halt (which a great many TMs, i.e. all of them
smarter than the UTM, can ALWAYS confirm), then a much
longer descripton summarizing the contents of its tape,
its head position, its particular halting state, and how long it ran,
can be confirmed. But if it doesn't halt then you may NOT be
able to confirm that,
or to know ANY "behavior".


Here I'm going to illustrate the problems with
perfect prediction using humans instead of programs.

This is going to go very wrong.
The problem is that the humans are time-bound via
natural language in a way that is very difficult for the TMs
to emulate, and they encounter problems that the TMs would
easily get around. The TMs have other simpler deeper problems
of their own.

Suppose that we have game in which two players, call them "Peter" and
"Daryl" are asked yes/no questions. The rules stipulate that the only
legal answers are "yes" and "no" (if neither answer seems appropriate,
then the players must respond with silence).

Again, silence, by definition, IS NOT a response.
Nobody can EVER TELL that anybody's response is silence.
There is no way for any human OR any machine TO TELL THE
DIFFERENCE between "responding with silence" and just thinking
about it for a really long time BEFORE FINALLY responding yes or no.
It does precious little good to allege that some one or some machine
has responded with silence if you can't confirm that that is in fact
the
case. And although you sometimes can, those cases are provably
sparse.

Assume that the players
are intelligent and will attempt to answer the questions correctly,
but most importantly they will never intentionally answer a question
incorrectly---if they are not sure about the answer, then they should
refrain from answering, rather than risk making an incorrect answer.

With TMs this is automatic; every TM gives the answer it was programmed
to give; there can simply be no such thing as an incorrect answer.
This is one more difference between the machine version and the
people version. The answer that the TM (correctly) gives may not be
the answer to the question you wanted to ask, but all that means is
is that THAT TM was programmed to answer a DIFFERENT question from
the one you were asking. This is a difference between the machine
version
and the people version.

The rules are that both players get to see both questions. Afterwards,
they are taken to separate answer rooms to figure out their answers. No
interaction between the players is allowed. So there is no possibility
that one player's answer can influence the answer given by the other.

Of course there is, if one of the players is so smart that he knows
exactly
how the other thinks. E.G., if both players are both extensions of
UTMs
and have, as an input, copies of each other's source code.

Each player must answer only using the knowledge that he brings into
the answer room.

This is intended to be heaping similarity upon similarity between
the human and machine versions, but the difference is quite
irreducible.


Okay, that's the background. Now here are the questions:

Peter is asked: Will Daryl answer "yes"?

Yes to what? When?

Daryl is asked: Will Peter answer "no"?

Yes to what? When?

Both questions are part of both inputs but the human constraint
here that is guaranteed NOT to be present in the TM universe is
that your own answer to THIS PARTICULAR posing of the question
affects the other person's answer, logically, correctness-wise.
It is NOT clear that this occurs in any sort of natural way, TMwise.
If it does then it occurs almost by accident, as a fixpoint that is
hard to construct, at least has hard as the first proof of Godel's
theorem.


I think it is clear that there is nothing paradoxical about
the questions.

You're quite wrong.

Peter must use his knowledge about Daryl in
order to answer the question, and Daryl must use his knowledge
about Peter.

But that is not all. Having used that, Peter must then use his
knowledge about Peter. This doesn't terminate.


We can analyze the possibilities here (and presumably Peter and
Daryl can do the analysis).

This is not presumable at all; in fact it is disprovable.
Peter and Darryl cannot confirm that each other are going to
remain silent. The best they can do is both remain silent,
WHICH PROVIDES NO confirmation to them OR US that
EITHER of them has YET "reached the conclusion" that silence
is the only "allowed" response. For all WE know, they could still
be thinking about it. The question of whether 1) knowing that you
need to remain silent, and 2) being confused about what to say,
ARE EVEN DIFFERENT BEHAVIORS, is VERY problematic here.
For the TMs, they are NOT different. If they are for the people,
then this is simply a bad analogy.

1. If Daryl and Peter give the same answer (either both "yes"
or both "no") then Daryl is mistaken, and Peter is correct.

2. If they give opposite answers (one "yes" and one "no") then
Peter is mistaken, and Daryl is correct.

3. In light of 1&2, if both answer, then one of them is mistaken.

So, it is clearly impossible for both Daryl and Peter to
have perfect ability to predict the future behavior of the
other.

That was already impossible.
The reasons you give for its being impossible here
have precious little to do with the real reasons.
Here, the "future" is critically implicated, and it is
actually NOT the future but RATHER the SIMULTANEITY
that is the problem.

This formulation seems to be completely about the limitations
of knowledge and reasoning ability. There is nothing paradoxical
going on. And in particular, there doesn't seem to be the
escape clause: Daryl (or Peter) knows the answer, but he can't
say it. If he knows the answer, there is nothing at all preventing
him from saying it. One player's answer has no causal effect on
the other player.

Of course it does.
Neither player is at liberty to answer until he thinks he has
in fact computed the other player's answer. Since one player
sees the other player trying to compute one's own answer, the
regress of causality is immediate and obvious.

This game is similar to the following one-player game:

No! You just argued that it was DIFFERENT!

Someone
asks Daryl to answer the following question with "yes" or "no"
(and to make no other responses)

Will the next answer you give be "no"?

In this case, Daryl cannot correctly answer the question, but
it is possible for him to *know* the answer (and keep it to
himself).

This really is a critical difference between people and TMs.
When TMs reach a conclusion, they halt. Of course, they
don't have to; they can loop out of sheer perversity EVEN though
they know. But that would violate some paradigmatic conventions here.
More to the point, here, it matters a lot Who is speaking When.
It is HARD to MAKE those things matter in the TM-world.
By default everyone is proud that they CAN'T matter.

He can refuse to answer at all, in which case, he
can know that the correct answer is "no".

No, it isn't.
If he never gives an answer then his next answer does not
exist, so the question of whether it is or isn't no has a false
presupposition, namely, that there was an answer.
Non-halting IS NOT an answer or a behavior, if you have
to simulate it.


In my two-player version, there is nothing preventing a player
from saying the answer if he knows it.

So, obviously, there is a critical difference.

.

Relevant Pages

  • Halting Problem for Humans
    ... then the players must respond with silence). ... Peter is asked: Will Daryl answer "yes"? ... have perfect ability to predict the future behavior of the ...
    (sci.logic)
  • Re: Halting Problem for Humans
    ... The halting problem is a well defined question while ... your questions to Peter and Daryl are not. ... 'Will Daryl answer 'yes' to the question whether you will answer 'no' ... then the players must respond with silence). ...
    (sci.logic)
  • Re: Halting Problem for Humans
    ... The rules are that both players get to see both questions. ... they are taken to separate answwer rooms to figure out their answers. ... Peter is asked: Will Daryl answer "yes"? ...
    (sci.logic)
  • Re: Halting Problem for Humans
    ... The halting problem is a well defined question while ... Imagine that Peter and Daryl are both robots, ... Will Daryl's response to string S be "yes"? ...
    (sci.logic)
  • Re: Halting Problem for Humans
    ... Peter is asked: Will Daryl answer "yes"? ... of knowledge and reasoning ability. ... that the stipulation you are making is not an additional rule of the ...
    (sci.logic)
Loading