Halting Problem for Humans
Daryl McCullough
No program can have perfect ability to predict the future behavior of
all other programs. Here I'm going to illustrate the problems with
perfect prediction using humans instead of programs.
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). 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.
The rules are that both players get to see both questions. Afterwards,
they are taken to separate answwer 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.
Each player must answer only using the knowledge that he brings into
the answer room.
Okay, that's the background. Now here are the questions:
Peter is asked: Will Daryl answer "yes"?
Daryl is asked: Will Peter answer "no"?
I think it is clear that there is nothing paradoxical about
the questions. Peter must use his knowledge about Daryl in
order to answer the question, and Daryl must use his knowledge
about Peter.
We can analyze the possibilities here (and presumably Peter and
Daryl can do the analysis).
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.
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.
This game is similar to the following one-player game: 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). He can refuse to answer at all, in which case, he
can know that the correct answer is "no".
In my two-player version, there is nothing preventing a player
from saying the answer if he knows it.
--
Daryl McCullough
Ithaca, NY
abo
<snip>
I'm not sure I agree. As you state about the one person game, there
may be a difference in what either believes and what is said. So it
seems to be possible, contra your claims of impossibility, that both
Daryl and Peter do have the ability to predict the future behaviour of
the other. If, for instance, both are told that Daryl will be rewarded
if he answers "yes" and Peter will be rewarded if he answers "no", then
Daryl will answer "yes" and Peter will answer "no", regardless of the
sense of the answer. What is more, Daryl will know (under the usual
meaning of "know" - i.e. not using the sceptic's) that Peter will
answer "no" and Peter will know that Daryl will answer "yes". Sure
Peter is the mistaken in the answer that he gave, but he didn't give
the answer that he believed.
Sure there are situations where Daryl won't know what Peter will answer
- the simplest situation would be that Daryl doesn't know the question
Peter is answering and doesn't know anything about Peter, in which case
he has no grounds for believing anything about Peter's answer; so he
cannot know. But there's nothing special here. So, if your claim is
simply about the limitations of knowledge, then there are simpler
examples.
Daryl McCullough
>Daryl McCullough wrote:
>> Okay, that's the background. Now here are the questions:
>>
>> Peter is asked: Will Daryl answer "yes"?
>> Daryl is asked: Will Peter answer "no"?
...
>> So, it is clearly impossible for both Daryl and Peter to
>> have perfect ability to predict the future behavior of the
>> other.
>>
>> 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.
>
>I'm not sure I agree. As you state about the one person game, there
>may be a difference in what either believes and what is said.
There *could* be a difference, but part of the assumption
here is that Peter and Daryl are both attempting to answer
correctly, and that they know that the other is attempting
to correctly, etc.
In such a circumstance, there is no reason for there to
be a difference between what one believes and what one
says. It can never be to one's advantage to refrain from
saying what one believes.
>So it seems to be possible, contra your claims of impossibility,
>that both Daryl and Peter do have the ability to predict the
>future behaviour of the other. If, for instance, both are told
>that Daryl will be rewarded if he answers "yes" and Peter will
>be rewarded if he answers "no", then Daryl will answer "yes"
>and Peter will answer "no", regardless of the
>sense of the answer.
But they *weren't* told that. I stipulated that each is
attempting to answer correctly. If you want to spell out
rewards and punishments, we can say that each is rewarded
for making a correct answer and punished for making an
incorrect answer. Making no answer produces neither
reward nor punishment.
>Sure there are situations where Daryl won't know what Peter will answer
>- the simplest situation would be that Daryl doesn't know the question
>Peter is answering and doesn't know anything about Peter, in which case
>he has no grounds for believing anything about Peter's answer;
But I stipulated that each *does* know the question given to the
other, and that they know as much as they like about the other's
motivations, intelligence, reasoning ability, etc.
>so he cannot know. But there's nothing special here. So, if your
>claim is simply about the limitations of knowledge, then there
>are simpler examples.
An example in which someone lacks a certain piece of information
is *not* an example of a limitation of knowledge, because a lack
of information can be remedied by giving the person more knowledge.
In the scenario as I have stipulated it, there *is* no remedy.
No amount of knowledge given to Peter and Daryl will be enough.
abo
Okay. Sorry I realized belatedly that you made this stipulation, and a
follow-up post which I made doesn't seem to have made it onto
sci.logic, so I'll answer here.
You can, of course, stipulate what you like. But it should be noted
that the stipulation you are making is not an additional rule of the
game; it is stipulating how the game must be played. That is, you are
not simply adding the rule, "Players must try to answer correctly,"
because that, as any rule to a game, could be broken, and does not
ensure that players will answer correctly. You are making a
stipulation about the world and the environment in which the game is
played. That may tell us something about knowledge and reasoning, but
the interest of what it tells us seems to depend strongly on the nature
of the stipulation.
>
> >Sure there are situations where Daryl won't know what Peter will answer
> >- the simplest situation would be that Daryl doesn't know the question
> >Peter is answering and doesn't know anything about Peter, in which case
> >he has no grounds for believing anything about Peter's answer;
>
> But I stipulated that each *does* know the question given to the
> other, and that they know as much as they like about the other's
> motivations, intelligence, reasoning ability, etc.
>
> >so he cannot know. But there's nothing special here. So, if your
> >claim is simply about the limitations of knowledge, then there
> >are simpler examples.
>
> An example in which someone lacks a certain piece of information
> is *not* an example of a limitation of knowledge, because a lack
> of information can be remedied by giving the person more knowledge.
> In the scenario as I have stipulated it, there *is* no remedy.
> No amount of knowledge given to Peter and Daryl will be enough.
>
Well, you could give information to either Peter or Daryl (but not
both) which would be enough. The problem is that you've constructed an
example where the information given to one changes the information that
the other needs. But I'm not sure your example is telling us anything
about knowledge or reasoning, in the same way that one doesn't learn
about God when one considers whether he can make a stone he cannot
lift, or one doesn't learn about one can be said by imagining the
situation where Daryl and Peter are both instructed to say "x" plus
whatever the other person has said (obviously one person would lose
this game).
LauLuna
halting problem. The halting problem is a well defined question while
your questions to Peter and Daryl are not.
Each of them is circularly defined. Trying to complete the text of the
question to Peter (which I suppose you think contextually completed) we
would obtain:
'Will Daryl answer 'yes' to the question whether you will answer 'no'
to the question whether Daryl will answer 'yes' to the question
whether...?'
Of course, you can block the infinite regress by substituting 'this
question' for the infinte phrase 'the question whether you will
answer...' and obtain:
'Will Daryl answer 'yes' to the question whether you will answer 'no'
to this question?'
Now the self-reference only makes the circularity still more evident.
The halting problem contains no circularity in its definition because
it poses a purely syntactical or mechanical question with no semantic
or intentional dimension. Mechanical or merely syntactical states of
affairs (states of affairs about machines, symbol strings, etc.) are
always possible objects for any thinking subject whoever, they are
always out there, so to say, already objectified.
In contrast, and using phenomenological terms, we can say that no
intentional act of thinking can be its own intentional object; call
'PNS' that proposition; so according to PNS, it is not the case that
any intentional act is a possible object for any thinking subject.
This is why your questions to Peter and Daryl cannot be well defined
questions for none of them: trying to answer them correctly would force
them to consider their own attempt to answer and this would be
phenomenologically impossible.
Maybe we've met here an essential difference between thinking behaviors
and machines: only the latter are always possible objects for the
former.
Regards
Peter Olcott
news:ehdog...@drn.newsguy.com...
> This game is similar to the following one-player game: 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). He can refuse to answer at all, in which case, he
> can know that the correct answer is "no".
>
This is exactly and precisely one aspect of the line-of-reasoning that I have
provided showing that there are some issues with calling at least some of the
variations of the Halting Problem un-decidable. Daryl can decide the answer,
yet, Daryl can not provide the answer.
Daryl McCullough
>There is a crucial difference between the case you propose and the
>halting problem. The halting problem is a well defined question while
>your questions to Peter and Daryl are not.
Not really. Imagine that Peter and Daryl are both robots,
and their behavior is completely specified by a computer
programs, and that both Peter and Daryl have access to
each other's programs. In that case, it is exactly analogous
to the halting problem.
In the case of real humans, it only becomes fuzzier because
we lack perfect knowledge about the mechanisms by which each
of us makes decisions.
>Each of them is circularly defined. Trying to complete the text of the
>question to Peter (which I suppose you think contextually completed)
The question was already complete. Peter was asked whether
Daryl's next utterance will be "yes". Daryl was asked whether
Peter's next utterance will be "no". That's a complete question.
>we would obtain:
>
>'Will Daryl answer 'yes' to the question whether you will answer 'no'
>to the question whether Daryl will answer 'yes' to the question
>whether...?'
Yes, you can expand any question into an equivalent longer question.
The point is, there is no ambiguity about what each is asked to do.
>'Will Daryl answer 'yes' to the question whether you will answer 'no'
>to this question?'
>
>Now the self-reference only makes the circularity still more evident.
What difference does it make whether it is self-referential or not?
There is no ambiguity in what each is being asked to do.
If they were completely described by computer programs, then
it is clear what is being asked:
Daryl is being asked: Will Peter's response to string S be "no"?
Peter is being asked: Will Daryl's response to string S be "yes"?
where string S is just the description of the game. There is no
uncertainty or ambiguity here, other than the fact that (in the
case of humans) we each only have partial knowledge of the behavior
of others.
>The halting problem contains no circularity in its definition because
>it poses a purely syntactical or mechanical question with no semantic
>or intentional dimension.
There is no semantic dimension here, either. Human beings are physical
systems that work through natural laws. If we had perfect understanding
of those laws (and of the initial conditions), then we would know what
Peter's response will be (or else, his response could be nondeterministic,
in which case we could make probabilistic predictions).
>In contrast, and using phenomenological terms, we can say that no
>intentional act of thinking can be its own intentional object; call
>'PNS' that proposition; so according to PNS, it is not the case that
>any intentional act is a possible object for any thinking subject.
I'm not sure what you are talking about. The question of what
Peter's response to the game will be is a purely physical question.
There is a causal chain from the act of Peter being told the rules
to Peter producing certain sounds from his mouth. We only have partial
knowledge of that causal chain, but I don't see how in principle there
is any difference between asking a question about the response of
a human being and asking a question about the behavior of a computer
program.
>This is why your questions to Peter and Daryl cannot be well defined
>questions for none of them:
They are completely well-defined questions. Either Peter's response will
be "no", or it won't. Either Daryl's response will be "no" or it won't.
There is no third possibility. (Well, actually, the third possibility
is that they will not answer, or will answer using an illegal reply
such as "I don't know"---but in that case, it is false that the answer
is "yes" and it is also false that the answer is "no").
>trying to answer them correctly would force them to consider their
>own attempt to answer and this would be phenomenologically impossible.
No, that's not correct. For Daryl to answer the question, he only
needs to know how *Peter's* mind works. It's not self-referential
in that respect. Daryl only needs to know what Peter *believes*.
Those beliefs may not be correct.
>Maybe we've met here an essential difference between thinking behaviors
>and machines: only the latter are always possible objects for the
>former.
I think that's incorrect.
Daryl McCullough
>
>"Daryl McCullough" <stevend...@yahoo.com> wrote
>> This game is similar to the following one-player game: 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). He can refuse to answer at all, in which case, he
>> can know that the correct answer is "no".
>>
>
>This is exactly and precisely one aspect of the line-of-reasoning that I have
>provided showing that there are some issues with calling at least some of the
>variations of the Halting Problem un-decidable. Daryl can decide the answer,
>yet, Daryl can not provide the answer.
But the halting problem can be phrase in a way to eliminate
this possibility.
Daryl McCullough
>Daryl McCullough wrote:
>> I stipulated that each is
>> attempting to answer correctly. If you want to spell out
>> rewards and punishments, we can say that each is rewarded
>> for making a correct answer and punished for making an
>> incorrect answer. Making no answer produces neither
>> reward nor punishment.
>You can, of course, stipulate what you like. But it should be noted
>that the stipulation you are making is not an additional rule of the
>game; it is stipulating how the game must be played. That is, you are
>not simply adding the rule, "Players must try to answer correctly,"
>because that, as any rule to a game, could be broken, and does not
>ensure that players will answer correctly.
Yes, you're right. It's possible that Peter and Daryl both
correctly know how each will behave, but one or the other
chooses to answer incorrectly, anyway.
However, as I said, if we assume that each will try to answer
correctly, then it follows that they cannot have perfect ability
to predict the other's behavior.
>> An example in which someone lacks a certain piece of information
>> is *not* an example of a limitation of knowledge, because a lack
>> of information can be remedied by giving the person more knowledge.
>> In the scenario as I have stipulated it, there *is* no remedy.
>> No amount of knowledge given to Peter and Daryl will be enough.
>>
>
>Well, you could give information to either Peter or Daryl (but not
>both) which would be enough.
That's right. It's possible for one of them to answer correctly,
but it is not possible for both of them. We can arrange things
so that Peter has perfectly ability to predict Daryl's behavior,
or vice-versa, but we can't arrange things so that both have such
ability.
>The problem is that you've constructed an example where the
>information given to one changes the information that the other
>needs.
Yes, that's exactly what happens in the proof of the unsolvability
of the halting problem.
You can think of the halting problem in terms of a similar
game. One person is given the job of designing a HaltDetector.
This program is supposed to look at the source code of a
second program and return "true" if that program halts, and
"false" otherwise. The second person is given the job of
designing a program LoopIfHalts that will defeat the first
person's program (that is, produce the wrong answer).
The unsolvability of the halting problem amounts to the
claim that there is no ideal strategy for the first
player. (There obviously is no ideal strategy for the
second player, either. No matter what program he
builds, there is the possibility that the first
player will produce a detector that guesses right,
just by chance.)
In the halting problem, the two players roles are not
completely symmetric, because if the second player
is given complete knowledge of the first player's
program, then he can win.
>But I'm not sure your example is telling us anything
>about knowledge or reasoning
It shows that perfect prediction is impossible, when
the prediction is about things as complicated as humans.
Peter Olcott
Give it a shot, try and show this.
abo
Daryl McCullough wrote:
>
> >But I'm not sure your example is telling us anything
> >about knowledge or reasoning
>
> It shows that perfect prediction is impossible, when
> the prediction is about things as complicated as humans.
>
impossible that rules are broken.
Daryl McCullough
I'm not sure what you mean. Yes, there were artificial
assumptions at work in my scenario. However, if there
*were* a perfect algorithm for predicting the future
behavior of human beings, what would prevent the
algorithm from being used in the way I described?
Daryl McCullough
>"Daryl McCullough" <stevend...@yahoo.com> wrote
>>>This is exactly and precisely one aspect of the line-of-reasoning
>>>that I have provided showing that there are some issues with
>>>calling at least some of the variations of the Halting Problem
>>>un-decidable. Daryl can decide the answer, yet, Daryl can not
>>>provide the answer.
>>
>> But the halting problem can be phrase in a way to eliminate
>> this possibility.
>
>Give it a shot, try and show this.
First of all, for a computer program it doesn't make any
sense to say that the program knows something but can't
say it. The only sense in which a computer program can
be said to "know" some piece of information is if has
entered into a particular state associated with that
piece of information.
So let H(p,x) be any program that takes two string arguments,
p (a source code for a program of one string argument) and x
(an input to p). If you claim that H can "know" that the program
whose source code is p will halt on input x, then there must be
some point in the execution of H(p,x) where H enters into the
"knowing" state. Let's call the state in which H knows that
p will halt on input x, h(p,x), and call the state in which
H knows that p will not halt on input x, l(p,x).
Now, we construct a second program, L(p), with one string
input p. L(p) behaves as follows:
L(p) simulates the execution of H(p,p).
1. If H ever enters the state l(p,p), then
L(p) quits the simulation and halts.
2. If H ever enters the state h(p,p), then
L(p) enters into an infinite loop.
3. If H ever halts without having entered
state l(p,p), then L(p) enters into an
infinite loop.
4. The simulation of H will continue until
the simulation halts, or until H enters the
state l(p,p).
Now, consider the execution of H(L,L).
If H ever figures out that L(L) will not halt,
then it must enter into the state l(L,L).
But if H ever enters into that state, then
the simulation of H by L will enter that state.
But if the simulation enters the state l(L,L),
then L will halt. So H is wrong.
It doesn't work to say that H knows something
but it can't show it. To know something *means*
to enter a particular state, and if H enters
that state, then that fact will be detectable.
The alternative is to say that the program's
mind can know something that isn't reflected
in the program's state. That's a pretty mystical
notion, don't you agree?
abo
Perhaps I just misunderstand what you meant by "perfect prediction." I
took it to mean that one cannot have perfect prediction in the world as
it is. You seem to mean it in such a way that, to have perfect
prediction, one must be able to predict perfectly even in scenarios in
which the world only might be.
That is, your example makes an assumption about the world: in the game
proposed the players *must* play honestly. If they believe "yes", they
must say "yes"; and if they believe "no", they must say "no". The
world might be like that but it is not, or at least not often.
But anyway, I am perhaps too harsh, because most people find convincing
the familiar argument, "if there were perfect prediction, then if you
knew you were going to have an accident, then you would avoid the
situation in which the accident occurred," and your reasoning uses the
same lines, whereby information created by the perfect prediction
impacts what is being predicted.
Peter Olcott
> Peter Olcott says...
>
>>"Daryl McCullough" <stevend...@yahoo.com> wrote
>
>>>>This is exactly and precisely one aspect of the line-of-reasoning
>>>>that I have provided showing that there are some issues with
>>>>calling at least some of the variations of the Halting Problem
>>>>un-decidable. Daryl can decide the answer, yet, Daryl can not
>>>>provide the answer.
>>>
>>> But the halting problem can be phrase in a way to eliminate
>>> this possibility.
>>
>>Give it a shot, try and show this.
>
> First of all, for a computer program it doesn't make any
> sense to say that the program knows something but can't
> say it.
Since there is a scenario where this could be construed to make sense, this
statement is incorrect.
Within the specific context of TM's it may make less sense, yet probably still
some sense. The TM could enter a state where it secretly knows the answer, yet
this answer depends upon knowing the purely arbitrary encoding of these results.
The TM could halt on one of many possible integer values that vary for each
unique input, the value indicates halting or not halting, yet, only the TM knows
which is which.
> The only sense in which a computer program can
> be said to "know" some piece of information is if has
> entered into a particular state associated with that
> piece of information.
I agree with this completely.
So in order for H to avoid making a mistake its only possible choice is to
refrain from entering either of these two states. So the only possible correct
choice would still be to refrain from answering the question, thus showing that
the question of halting is ill-formed, according to the definition of ill-formed
questions.
Since there exists no correct answer within the solution set. In this case the
solution set is narrowly defined not as the question "Does the program Halt,
(YES or NO)? (because refraining from answering the question causes the program
to halt), but "Does the program Halt {l(L,L) or h(L,L)}?" This is still an
ill-formed question according to the definition of ill-formed questions.
LauLuna
They are completely well-defined questions. Either Peter's response
will
> be "no", or it won't. Either Daryl's response will be "no" or it won't.
> There is no third possibility.
Yes, that's right. I should have reflected on it more carefully.
Please, consider the following.
If you want to prove anything about limits of human knowledge, you have
to suppose your proof goes through for the the best possible human
thinkers and knowers.
So suppose Peter and Daryl are ideal thinkers and knowers; then each of
them knows they are. We do not need to suppose they are honest and
observe the rules of the game when answering; it suffices if each of
them knows that the answer of the other will be in some way determined
by his attempt to know. The situation that they are honest and they
both know they both are is a particular case of my approach.
Each of them will try to figure out what the other will think, but
since each of them knows the other will do the corresponding, each of
them will be compelled to consider his own attempt to answer while
performing that attempt.
So, ideal thinkers would find themselves trapped in circularity. And
knowing the other is also trapped won't help them. None of them will
ever work out what the other is going to say because it would imply
taking into account his own thinking in order to decide what his own
thinking should be.
Exactly this I said was phenomenologically impossible. So, what I
thought worked against your proposal actually works for it.
Now suppose one (or both) of our ideal thinkers does not observe the
rules of the game and answers even if he doesn't know the correct
answer. Well, that won't change the fact that no one knows what the
other will answer. Fortuitous success is here of no interest, I think.
By splitting into a two isolated person game the single person game you
have produced a beautiful piece where the 'escape' clause seems out of
order. It seems there is a possible situation in which ideal knowers
won't be able to know. I do think your example shows something
interesting.
I believe circularity lies in the core of the halting problem, for
humans and for machines. But I think it is quite different for humans;
for humans it is a question of 'intentional circularity': for humans
the relevant fact is that no intentional act can be its own
intentional object. E. g. when I'm thinking that it will rain I cannot
be thinking at the same time that I'm thinking it will rain. It is easy
to see that if an intentional act were its own intentional object, that
object would be of infinite complexity.
I think you have shown that an ideal thinker is not just incapable of
always having his own thought as an object but also incapable of always
having as an object the thought of other ideal thinker: no one can set
his thought at a higher level than the other's, as no one can set his
thought at a higher level than itself.
Now, there is neither logical nor scientifical proof that human
behavior is only determined by physical causality and that mental
states are causally inert. This can only be a philosophical (or
ideological) assumption.
Suppose the ideal attempt of our ideal thinkers could be represented as
a physical process completely determined by physical causes. Then, if
each of them is provided with a computer that has previously collected
sufficient information about the other's brain (and a relevant part of
its environment) and can calculate physical causality, each of them
should be able to know what the other would say.
Nevertheless, this seems impossible: what would prevent them from
answering what they know?
Regards
Daryl McCullough
>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.
george
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.
stevendaryl3016@yahoo
>> 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?
I thought I made it clear how the game works.
Each player is carried off to a room, and allowed
to think about his response. At some point, the
player comes out of the room and makes an utterance.
By the rules of the game, the legal utterances are
"yes" and "no".
Peter is being asked: Will Daryl's utterance
be "yes". Daryl is being asked: Will Peter's
utterance be "no".
There is really no ambiguity in the interpretation
of these questions.
>> I think it is clear that there is nothing paradoxical about
>> the questions.
>You're quite wrong.
No, there is nothing at all paradoxical going on. None of the
possible outcomes leads to any kind of contradiction.
> 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)...
> He can refuse to answer at all, in which case, he
> can know that the correct answer is "no".
>No, it isn't.
Well, it depends on the precise phrasing. If the question
is phrased as "Will Daryl give the answer 'no'"?, then
the lack of any answer means in particular that Daryl did
not answer "no".
LauLuna
> >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.
That's right. This is why in the case of humans there are semantical
dimensions involved that are absent from the TM version. Daryl
McCullough claims there aren't any by humans either. Well, then the
whole matter gets nonsensical since it goes on the possibility for
humans to CORRECTLY decide human behavior. It's worth remarking that it
is al, the same nonsensical to say that a TM cannot know or decide the
halting problem instead of saying that nobody can solve that problem by
using a TM.
For the rest, I believe Daryl's questions are well defined, contrary to
what I said in an earlier post. What cannot be *well defined*, so to
say, is the process of thought of Peter and Daryl, in the sense that it
will be circular and non terminating until they jump into a
meta-circular level when they know of their unavoidable circularity at
the lower level. Even this won't be of any help to them in order to
correctly know what the other will answer. All this provided they are
both ideal thinkers and knowers.
I now think this circularity does not imply that the questions are
ill-defined.
Regards
george
> LauLuna says...
> >There is a crucial difference between the case you propose and the
> >halting problem. The halting problem is a well defined question while
> >your questions to Peter and Daryl are not.
>
> Not really.
Daryl McCullough wrote:
Yes, really, if by "not-well-defined" we mean "not reasonably
translatable into a TM-like paradigm" (which is, after all, a very
powerful definitional framework).
> Imagine that Peter and Daryl are both robots,
> and their behavior is completely specified by a computer
> programs,
That means we might was well call them the PTM and the DTM.
And, imagine further that they are THE SAME program, except for
a version-code (P in one case, D in the other)
that doesn't affect the behavior of either program,
but simply suffices to ensure that their names and source-codes are
different strings. This STRONGLY highlights the difference between
the TM world, which does NOT have indexicals or demonstratives,
and the natural-language one, which does. If you give EITHER of
the PTM or the DTM *any* input-
string whatsoever, THEY ALWAYS produce THE SAME output. BUT if
you ask of them, "What is your output when you are given YOUR OWN code
as an input-string?" then despite the fact that you are asking what
looks
like "the same question" to both of these machines, you may get
DIFFERENT outputs (assuming 'P' and 'D' are in both input-alphabets)
because the natural-language "your own code"
translates to DIFFERENT input-strings for the two machines, when
you cross over to the other paradigm.
> and that both Peter and Daryl have access to
> each other's programs. In that case, it is exactly analogous
> to the halting problem.
No, NOT exactly, because it asks about "the next" response AS OPPOSED
to the response for some known input string, which is a thing that
CANNot be "next".
> In the case of real humans, it only becomes fuzzier because
> we lack perfect knowledge about the mechanisms by which each
> of us makes decisions.
>
> >Each of them is circularly defined. Trying to complete the text of the
> >question to Peter (which I suppose you think contextually completed)
>
> The question was already complete. Peter was asked whether
> Daryl's next utterance will be "yes".
That is NOT complete. It is not even TM-translatable AT ALL.
If you try to take the time out of it (and put it back into TM-speak)
then you will see that you get a mutual recursion (NON-founded).