On the way to Heaven you meet a person who sometimes tells the truth and sometimes lies.

Try this:

1.        "Is the gate on the right the gate to heaven?"

2.        "Counting your response to this question and your response to
        the previous question, have you told the truth exactly once?"

If the answers to these two questions are *different*, take the gate
on the right.  If they are the same, take the gate on the left.

For example, assume the person answers "yes" to question 2.  This
necessarily means he was lying in his response to question 1.  (If the
person is telling the truth in question 2, he has told the truth only
once.  Therefore he is lying in question 1.  If the person is lying in
question 2, he has not told the truth once, and therefore he is also
lying in question 1.)  Thus, if the answer to question 1 was "no"
(i.e., different from the answer to question 2), the gate on the right
is in fact the gate to heaven.  If the answer to question 1 was "yes,"
(i.e., the same as the answer to question 2), the gate on the right
leads to hell.

Similarly, if the person answers "no" to question 2, he was telling the
truth in his response to question 1.  Accordingly, the right gate leads
to heaven if the response to 1 was "yes" and to hell if the response to
1 was "no."

-- Michael Moetell <moetell@ix.netcom.com>

[ Editor: further material on this puzzle, edited separately from other collected postings (batch 10); it may repeat some of the above. ]

[ Editor: problem as stated there: ]
On the way to Heaven, I will meet a person who sometimes tells the
truth, and sometimes lies.  There are two gates, one for Heaven and one
for Hell.  I am allowed to ask this person just two questions, which
must have yes/no answers, to decide which gate to try.

Please, can anybody tell me what I should ask?

[ Editor: posted by john allen <etljhan@etlxdmx.ericsson.se> under the
  subject "Equivocator". ]


I'm afraid all of the answers are mistaken.

Maybe Gareth Rees' is good enough.

But note,

> Try this:
>
> 1.      "Is the gate on the right the gate to heaven?"
>
> 2.      "Counting your response to this question and your response to
>         the previous question, have you told the truth exactly once?"
>
> If the answers to these two questions are *different*, take the gate
> on the right.  If they are the same, take the gate on the left.

But how could you actually gain any information this way?

Suppose the person didn't hear what you said.  He just answered to make
you go away.  Or maybe he thought you asked "Is the game on tonight a
bit too heavy?" (Whatever that means.)

Anyone who draws a conclusion about which is the gate to heaven based on
such an answer is taking a shot in the dark.  But the reasoning works
exactly as well for this case.  So the reasoning is wrong.

Now take this answer:

> First point at a door and ask: "Is this the way to heaven?"
> Then ask him: "When you have answered these two questions, have you
> then been lying exactly once?"
> If the answer is Yes, you know that the first answer was a lie,
> if the answer in No, you know that the first answer was correct.

It looks good, but it's subject to the same objection.  (Actually, I
guess it's the same answer in different words.)

To see exactly what goes wrong, we'd have to see the full reasoning made
more explicit.  One potential faulty assumption is bivalence (which is
why Rees' answer is a considerable improvement).  (Or rather, now that I
look more carefully, it's why Rees' *question* is an improvement!)

But that is not the only potential villain.

Here is Rees' answer.  His question instructs us that we may assume
that every answer given is either true or false, and that every answer
will be 'yes' or 'no'.  This is more of a stipulation than we got in the
original puzzle, because it assumes bivalence.

> Ask this question (with P = "the left gate leads to Heaven"):
>
>   If you were to answer the question "Is P true?" with a statement of
>   the same truth-value as the statement with which you will answer
>   this question, would that statement be "yes"?
>
> If the person replies "yes" then P is true; if they reply "no" then P
> is false.

Again, the reasoning is not made explicit enough to see whether it is
perfectly sound.  I would like to see it, myself, because I think this
one really does have a chance at being correct.

In closing, here is a small but powerful argument designed to prove the
statement, P.  I won't say what P actually is.  The argument follows a
natural line of reasoning suggested by a theorem of Lob's.  I hope the
relevance to the Heaven's Gate problem is clear enough.

Consider the following sentence, whose name is "S".

"If S is true, then P."

As a lemma, we demonstrate that S is true.  The proof of the lemma is a
Conditional Proof.

1. S is true.                        (Supposition, to be discharged later.)
2. "If S is true, then P." is true.  (By substitution)
3. If S is true, then P.             (By disquotation)
4. P.                                (By modus ponens, from 3 and 1)
5. If S is true, then P.             (Discharging the supposition, as
                                      promised)
6. "If S is true, then P." is true.  (By re-quotation)
7. S is true.                        (By substitution)

Note that the supposition was discharged at line 5 and not drawn on
again, so the conclusion does not bear it as an assumption.  (This is
hard to follow, and in this particular case hard to swallow, but
Conditional Proof is allowed to be a valid rule in every system of
natural deduction.)

Now we make use of the lemma to prove P itself.

1. S is true.                        (Theorem)
2. "If S is true, then P." is true.  (By substitution)
3. If S is true, then P.             (By disquotation)
4. P.                                (By modus ponens, from 3 and 1)

QED.

-- Jamie Dreier <pl436000@brownvm.brown.edu>

Two questions do not help.  But it can be done with one question.  Ask
"If you were asked which door leads to heaven, what would you answer".
If he lying he'll tell a lie about a lie and if he's telling the truth
its cool.  Just use the door he says, assuming you want to go to heaven
of course.

-- Guy Dyson <fdt@iinet.com.au>

In article <3f3k75$rse@wanda.pond.com>, russotto@wanda.pond.com (Matthew
Russotto) writes:
>Asking him questions won't help much.  Ask him whether or not a given
>gate is the gate to Heaven.  Then grab him and drag him along towards
>that gate (if he said yes) or the other gate (if he said no).  If he
>was lying, he'll change his mind real fast.

As another poster has pointed out, questions do work.  The difference in
assumption is that here when we say that the person "sometimes tells
the truth and sometimes lies," it is not the same as saying that the
person "says anything he wants."  For a counterexample, if I said "This
sentence is false." I am neither lying nor telling the truth.

-- Wei-Hwa Huang <whuang@cco.caltech.edu>

[ Editor: the postings by Gareth Rees and the others quoted by Jamie
  Dreier are not in the collected material except as quoted. ]

[ Editor: further material on this puzzle, edited separately from other collected postings (batch 15); it may repeat some of the above. ]

[ Editor: problem as stated there: ]
On the way to Heaven, I will meet a person who sometimes tells the truth,
and sometimes lies.  There are two gates, one for Heaven and one for
Hell.  I am allowed to ask this person just two questions, which must
have yes/no answers, to decide which gate to try.

-- John Allen <etljhan@etlxdmx.ericsson.se>

Related puzzle: if you knew that every statement by the person is either
true or false, and that they always reply to yes/no questions with "yes"
or "no" if they can, then you can find the way to Heaven (or indeed
answer any other yes/no question) with one question.  What is it?

-- Gareth Rees <gdr11@cl.cam.ac.uk>


[ Editor: no solution to the first (two-question) version was found in
the collected postings.  For the related puzzle: ]

Note that the conditions are not quite the same as in the statement of
the puzzle above.

Ask this question (with P = "the left gate leads to Heaven"):

  If you were to answer the question "Is P true?" with a statement of
  the same truth-value as the statement with which you will answer this
  question, would that statement be "yes"?

If the person replies "yes" then P is true; if they reply "no" then P is
false.

-- Gareth Rees <gdr11@cl.cam.ac.uk>

[ Editor: further material on this puzzle, edited separately from other collected postings (batch 18); it may repeat some of the above. ]

[ Editor: problem as stated there: ]
On the way to Heaven, I will meet a person who sometimes tells the
truth, and sometimes lies.  There are two gates, one for Heaven and one
for Hell.  I am allowed to ask this person just two questions, which
must have yes/no answers, to decide which gate to try.  What should I
ask?

-- John Allen <etljhan@etlxdmx.ericsson.se>


First point at a door and ask: "Is this the way to heaven?"
Then ask him: "When you have answered these two questions, have you then
been lying exactly once?"
If the answer is Yes, you know that the first answer was a lie,
if the answer is No, you know that the first answer was correct.

-- Goran Wicklund <euagwd@eua.ericsson.se>

I can do it in one question:

   "Will your answer to this question be a lie if and only if the
    door on the left leads to Heaven?"

A "yes" answer means that the door on the right leads to Heaven. Let
H be the proposition that the door on the left leads to Heaven, and
Q be the proposition that the person's answer is a lie. There are four
cases to consider:

Case 1: He truthfully answers "yes".
  In this case, Q is false, and he truthfully asserts that Q is
  equivalent to H, therefore H is false and the door on the
  right leads to Heaven.

Case 2: He truthfully answers "no".
  In this case, Q is again false, and he is truthfully asserting
  that Q is not equivalent to H, and so H is true and the door
  on the left leads to Heaven.

Case 3: He falsely answers "yes".
  Q is true (since the person lied), and he falsely asserted that Q
  was equivalent to H, therefore H really is *not* equivalent to
  Q, and H is false, and the door on the right leads to Heaven.

Case 4: He falsely answers "no".
  Q is again true, and the person lied when he said that Q was
  not equivalent to H, therefore H really is equivalent to Q,
  and the door on the left leads to heaven.

In any case, a "yes" answer means the door on the right leads to Heaven,
a "no" answer means the door on the left leads to Heaven.

-- Jonathan Haas <positron@Starbase.NeoSoft.COM>

        Two questions do not help
        But it can be done with one question.
        Ask "If you were asked which door leads to heaven, what would you
        answer"
If he lying he'll tell a lie about a lie and if he's telling the truth
its cool.  Just use the door he says, assuming you want to go to heaven
of course.

-- Guy Dyson <fdt@iinet.com.au>

[ Editor: this is not a yes/no question as the puzzle requires, and the
double-lie argument assumes a person who lies consistently, not one who
lies only sometimes. ]

russotto@wanda.pond.com (Matthew Russotto) writes:
>Asking him questions won't help much.  Ask him whether or not a given
>gate is the gate to Heaven.  Then grab him and drag him along towards
>that gate (if he said yes) or the other gate (if he said no).  If he
>was lying, he'll change his mind real fast.

As another poster has pointed out, questions do work.  The difference in
assumption is that here when we say that the person "sometimes tells the
truth and sometimes lies," it is not the same as saying that the person
"says anything he wants."  For a counterexample, if I said "This sentence
is false." I am neither lying nor telling the truth.

-- Wei-Hwa Huang <whuang@cco.caltech.edu>

I'm afraid all of the answers are mistaken.

Maybe Gareth Rees' is good enough.

But note,

> Try this:
>
> 1.      "Is the gate on the right the gate to heaven?"
>
> 2.      "Counting your response to this question and your response to
>         the previous question, have you told the truth exactly once?"
>
> If the answers to these two questions are *different*, take the gate on
> the right.  If they are the same, take the gate on the left.

But how could you actually gain any information this way?

Suppose the person didn't hear what you said. He just answered to make you
go away. Or maybe he thought you asked "Is the game on tonight a bit too
heavy?" (Whatever that means.)

Anyone who draws a conclusion about which is the gate to heaven based on
such an answer is taking a shot in the dark. But the reasoning works
exactly as well for this case. So the reasoning is wrong.

Now take this answer:

> First point at a door and ask: "Is this the way to heaven?"
> Then ask him: "When you have answered these two questions, have you then
> been lying exactly once?"
> If the answer is Yes, you know that the first answer was a lie,
> if the answer in No, you know that the first answer was correct.

It looks good, but it's subject to the same objection. (Actually, I guess
it's the same answer in different words.)

To see exactly what goes wrong, we'd have to see the full reasoning made
more explicit. One potential faulty assumption is bivalence (which is why
Rees' answer is a considerable improvement). (Or rather, now that I look
more carefully, it's why Rees' *question* is an improvement!)

But that is not the only potential villain.

Here is Rees' answer. His question instructs us that we may assume that
every answer given is either true or false, and that every answer will be
'yes' or 'no'. This is more of a stipulation than we got in the original
puzzle, because it assumes bivalence.

> Ask this question (with P = "the left gate leads to Heaven"):
>
>   If you were to answer the question "Is P true?" with a statement of
>   the same truth-value as the statement with which you will answer this
>   question, would that statement be "yes"?
>
> If the person replies "yes" then P is true; if they reply "no" then P is
> false.

Again, the reasoning is not made explicit enough to see whether it is
perfectly sound. I would like to see it, myself, because I think this one
really does have a chance at being correct.

In closing, here is a small but powerful argument designed to prove the
statement, P. I won't say what P actually is. The argument follows a
natural line of reasoning suggested by a theorem of Lob's. I hope the
relevance to the Heaven's Gate problem is clear enough.

Consider the following sentence, whose name is "S".

"If S is true, then P."

As a lemma, we demonstrate that S is true. The proof of the lemma is a
Conditional Proof.

1. S is true.                         (Supposition, to be discharged later.)
2. "If S is true, then P." is true.   (By substitution)
3. If S is true, then P.              (By disquotation)
4. P.                                 (By modus ponens, from 3 and 1)
5. If S is true, then P.              (Discharging the supposition, as promised)
6. "If S is true, then P." is true.   (By re-quotation)
7. S is true.                         (By substitution)

Note that the supposition was discharged at line 5 and not drawn on again,
so the conclusion does not bear it as an assumption. (This is hard to
follow, and in this particular case hard to swallow, but Conditional Proof
is allowed to be a valid rule in every system of natural deduction.)

Now we make use of the lemma to prove P itself.

1. S is true.                         (Theorem)
2. "If S is true, then P." is true.   (By substitution)
3. If S is true, then P.              (By disquotation)
4. P.                                 (By modus ponens, from 3 and 1)

QED.

-- Jamie Dreier <pl436000@brownvm.brown.edu>

[ Editor: Wei-Hwa Huang replied: ]

>Suppose the person didn't hear what you said. He just answered to make you
>go away. [...]

Then he cannot guarantee that he is either "telling the truth or lying,"
as the original problem stipulated.  The amazing thing here is that we
think the law of the excluded middle is so natural in logic that we actually
cannot distinguish between someone who follows the law and the rest of us.

>Anyone who draws a conclusion about which is the gate to heaven based on
>such an answer is taking a shot in the dark. But the reasoning works
>exactly as well for this case. So the reasoning is wrong.

Or the assumptions are.

-- Wei-Hwa Huang

[ Editor: Jamie Dreier answered: ]

> Then he cannot guarantee that he is either "telling the truth or lying,"
> as the original problem stipulated.

This is a good point, but not, I think, quite good enough.

The problem doesn't say that the person can *guarantee* that he either
tells the truth or lies. It just says, that's what he does.

>  The amazing thing here is that we
> think the law of the excluded middle is so natural in logic that we actually
> cannot distinguish between someone who follows the law and the rest of us.

Wait, I think there are at least two confusions here.

First, I was talking about *bivalence*, not excluded middle. Of course,
they are related, but not the same. Excluded middle says that every
sentence of the form "P or it is not the case that P" is true. Bivalence
says that each sentence is either true or false.

Second, neither of these laws is something that a person *follows*. Each
pertains to sentences, not their speakers.

> Or the assumptions are.

Or both.

-- Jamie Dreier

On the same assumptions made by most of the contributors to this
thread, you could ask a single question which would force this person
to say "Yes":

Is your answer to this question the truth?

(If he decides to lie, then the correct answer to the question will be
"No"; then, in order to lie, he must say "Yes" instead.)

A person who is capable of answering "No" to that question, is also
capable of fooling us about the gates.  What kind of person would that
be?  Someone who is inattentive to his task, or confused by the
question, or who took his mandate (always to tell the truth or else
lie) to mean that it doesn't matter what he says, as long as it's
either yes or no.

-- Gwillim Law <law@glvdev>

pl436000@brownvm.brown.edu (Jamie Dreier) writes:
>Now ask this:
>"Is the following the case: that either I am thinking of an even number,
>or the gate to the left is the gate to heaven?"
>
>The person *cannot* lie, because he cannot guarantee that his answer will
>be false, and to lie he must *knowingly* tell a falsehood. So he must tell
>the truth (according to the ground rules), and this he can do only if the
>gate to the left is the gate to heaven!
>So you know that heaven's gate is to the left, even before the person
>answers.

Sorry.  It is still possible for the person to lie.  It may not be possible
for the person to *know* that he is lying, but he can still tell a falsehood.

If you disagree with that, then you are disagreeing with a claim that
"lie=falsehood."  If that is the case, then I'll accept your argument.

-- Wei-Hwa Huang <whuang@cco.caltech.edu>

Oh, well, I *was* disagreeing with that. I've always thought that lying
involved knowing that one was speaking falsely (or at least having a good
reason to think so).

So, your condition is that the person must speak truly or falsely, right?
I agree that this helps the problem. And we should agree, too, that the
person is not allowed to refuse to answer.

But then my original objection looks good again (to me, at least). Suppose
the person answers the questions without paying attention to what was
asked. (The questions are the ones suggested by a couple of people.) Then
I get no information at all from his answer. But, assuming that he spoke
truly or falsely, one could reason one's way to an answer. Something must
be wrong here.

What happens if I ask him, "If you answered 'yes' to this question, would
you speak falsely?" It looks like he can't answer this question in
accordance with the rules of the puzzle laid down. But according to those
rules, he must answer it. So if I ask that question, the rules are
inconsistent!

-- Jamie Dreier <pl436000@brownvm.brown.edu>