wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> NEW PROBLEM: The Operators of Boolania
        
(Message started by: Eric Yeh on Aug 19^th, 2002, 9:49pm)

Title: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Aug 19^th, 2002, 9:49pm

Ok, now that the Gibberland posts are pretty much dying down, here is a new problem! As promised, this one is a bit of a breather -- another one I pulled out of my '98 collection. This is the kind that Jon's computer can wail away on, so I highly recommend doing it without computer aid, for the fun of it. Another perspective for those who find this one too easy: Consider it a test of elegance. ;) ;) Don't worry though, I still have some tougher ones for sometime down the line...

-----

THE OPERATORS OF BOOLANIA

There are three omniscient gods sitting in a chamber: And, Or, and Xor. They all answer the truth, but they apply their namesake operations in one of the following ways:

CASE 1 "Backward". The operator is applied to all of the questions that have been asked thus far.

CASE 2 "Universal". The operator is applied to ALL of the questions (you have to pick your questions beforehand).

CASE 3 "Selfless". The operator is applied to all of the questions NOT asked to them (you have to pick your questions beforehand).

For each of the three cases:

Determine with proof the minimum number of questions which will allow you to identify which god is which.

[Notes:

Standard: (Rules that are generally assumed unless otherwise noted.) The gods only answer yes/no questions. Each god answers in the single word of their language as appropriate to the question; i.e. each god always gives one of only two possible responses, one affirmative and one negative (e.g. they would always answer "Yes" rather than "That would be true"). Each question asked must be addressed to a single specific god; asking one question to all the gods would constitute three questions. Asking a single god multiple questions is permissible. The question you choose to ask and the god you choose to address may be dynamically chosen based on the answers to previous questions.

Specific: Because of possible time conflicts, you must determine your questions ahead of time, rather than based on previous answers. However, you are still allowed to choose who you ask each of your three questions to dynamically. Scoping is also dynamic; e.g. the pronoun "you" in a question will always refer to the person to whom you are currently asking a question, not a predetermined person). No time related questions (e.g., "if the answer to my second question was 'no', then X otherwise Y") are permissible, as this could lead to paradoxes within the space-time continuum).]

-----

As usual, I request that no strong spoilers be posted! Thanks!!!

Happy Puzzling!
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Aug 19^th, 2002, 9:57pm

HEY!! How come GLOW doesn't work on my titles any more??!!! ???

(And with my luck, it'll soon be fixed, and everyone reading this post will have no idea what I'm talking about... <SIGH>)

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by william wu on Aug 19^th, 2002, 10:25pm

might be clearer to say "but they *all* apply their namesake operations in one of the following ways", so the reader doesn't think that each god could be using a different operation application style

very cool riddles, as always :)

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Aug 20^th, 2002, 5:18am

Will,

Thanks for the commentary and clarification. Yes, the glow seems to be working fine for me now as well.

Best,
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by jeremiahsmith on Aug 21^st, 2002, 10:08pm

Mr. Yeh, you're quite the puzzle-maker. :) I only wish I had your creativity.

Now, how do the operations work with more than 2 questions?

For example, if you ask 4 questions, how would Xor respond Universally, and the like?

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Aug 22^nd, 2002, 6:35am

Jeremiah,

Many thanks for the warm comments!! They are very much appreciated. :)

If you have four questions which a strictly truth-telling (i.e. non-operating) Xor would answer with Q1, Q2, Q3, and Q4, the "operating" Xor would answer Q1 xor Q2 xor Q3 xor Q4, i.e. "false" iff there are an even number of "true"s in the Qi.

(For "selfless" operation, e.g., if you ask him Q2, he will answer Q1 xor Q3 xor Q4.)

Hope that clarifies the problem!

Best,
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Jonathan_the_Red on Aug 28^th, 2002, 5:38pm

Seeing as how this one is languishing, I'll take a stab...

You obviously can't do better than three questions. Therefore a solution that does it in three needs no proof of minimality.

Here's a solution for case 1: Backward. Hidden by color.

And = A
Or = O
Xor = X

Question 1: [to God A]: Are you Xor?
Question 2: [to God B]: Is 2+2 equal to 4?
Question 3: [to God B if answer to Q2 is Y, God C otherwise] Is And to the left of Or?

Answer YYY: Gods are X,O,A
Answer YNY: Gods are X,A,O

YYN and YNN are not possible (Q3 will be asked of Or in either case)

The remaining cases depend on the truth table of the ternary XOR operator. Going under the assumption that XOR(A, B, C) is true iff an odd number of (A, B, C) are true, they are:

Answer NYY: Gods are A, X, O
Answer NYN: Gods are O, X, A
Answer NNY: Gods are A, O, X
Answer NNN: Gods are O, A, X

If instead A XOR B XOR C is true iff ( (A AND B AND C) OR (~A AND ~B AND ~C) ), just reverse A and O in the above four answers.

I haven't really tried the other two cases yet, but I'll get to 'em.

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Jonathan_the_Red on Aug 28^th, 2002, 5:40pm

Er... I just noticed that the puzzle talks about the Gods answering "in their own language". I don't think the solution above works with the iff trick... Eric, do the Gods not speak English? I'll have to play around a bit if they don't.

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Aug 28^th, 2002, 9:26pm

No, this one's in English. The "standard note" is just that -- a generic one to handle all cases.

Good luck with the next two, the difficulty escalates. ;)

Best,
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Aug 29^th, 2002, 6:02am

Jonathan,

I just had a chance to look at this a little more carefully.

on 08/28/02 at 17:38:15, Jonathan_the_Red wrote:

Seeing as how this one is languishing, I'll take a stab....

Yes, I was starting to get worried! Thanks for playing! :)

on 08/28/02 at 17:38:15, Jonathan_the_Red wrote:

You obviously can't do better than three questions. Therefore a solution that does it in three needs no proof of minimality.

True.

on 08/28/02 at 17:38:15, Jonathan_the_Red wrote:

Question 1: [to God A]: Are you Xor?
Question 2: [to God B]: Is 2+2 equal to 4?
Question 3: [to God B if answer to Q2 is Y, God C otherwise] Is And to the left of Or?

Going under the assumption that XOR(A, B, C) is true iff an odd number of (A, B, C) are true, they are:

Answer NYY: Gods are A, X, O
Answer NYN: Gods are O, X, A
Answer NNY: Gods are A, O, X
Answer NNN: Gods are O, A, X

I'm a little confused here. In the case of AOX, for example, you will get NYY, not NNY as you listed, no? Because Or always responds Y after the 2+2=4. Similarly, AXO seems to answer NNY rather than NYY (the second response being Y xor Y, and the third being N or Y or Y). Am I misunderstanding your question set?

on 08/28/02 at 17:38:15, Jonathan_the_Red wrote:

The remaining cases depend on the truth table of the ternary XOR operator.

If instead A XOR B XOR C is true iff ( (A AND B AND C) OR (~A AND ~B AND ~C) ), just reverse A and O in the above four answers.

Interesting, I have never seen it defined that way. Is that something that is sometimes done?? It doesn't even generalize to the binary operator case!

on 08/28/02 at 17:38:15, Jonathan_the_Red wrote:

I haven't really tried the other two cases yet, but I'll get to 'em.

Good luck!
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Jonathan_the_Red on Aug 29^th, 2002, 1:58pm

on 08/29/02 at 06:02:17, Eric Yeh wrote:

No, I was just being a gimboid, yet again. I think I mistranscribed my solution, and I've unfortunately discarded my notes. I'll reconstruct it and repost it later.

Quote:

Interesting, I have never seen it defined that way. Is that something that is sometimes done?? It doesn't even generalize to the binary operator case!

Er, what I meant was:

If instead A XOR B XOR C is ~~true~~false iff ( (A AND B AND C) OR (~A AND ~B AND ~C) ), just reverse A and O in the above four answers.

This does generalize to the binary case. It's basically saying that XOR(p1, p2, p3, p4, ... pn) is true when at least one of the propositions is true, but not all of them. So which version of XOR did you have in mind?

My track record for posting working solutions isn't the greatest, but here's what I believe to be a valid solution for the Universal case, hidden by color:

Since each God will answer all of the questions, there's absolutely no benefit in asking any single God more than one question (unless you need more than three, which we don't.) So ask these questions to three different Gods:

Q1: Is two plus two equal to four?
Q2: Is two plus two equal to five?
Q3: Is God B Xor if and only if And is to the left of Or?

This produces the following unique answers:

A O X N Y Y O A X Y N N A X O N N Y O X A Y Y N X A O Y N Y X O A N Y N

By the way, my solutions so far have been done without the aid of a computer. I'm going to try to keep it kosher this time :)

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Aug 29^th, 2002, 2:05pm

Fair enough -- and ye, I figured most likely you just meant "false iff..." instead of "true iff...". Still, I've never heard of the operator being defined in that way. Can anyone else corrobrate?

In any case, I did indeed intend the former -- see my Reply #5. ;)

I don't have time to check your soln right now, but will get around to it some time. :)

Best,
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Jonathan_the_Red on Aug 29^th, 2002, 3:50pm

Clarification re. Selfless:

The Gods are A, B, and C. I ask three questions, directing them to A, A, and B respectively.

B will answer Q1 op Q2. Will A twice answer Q3, or will he answer Q2 op Q3 followed by Q1 op Q3?

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Aug 29^th, 2002, 3:56pm

The latter. Thanks for the clarification.

Title: Is Boolania too easy??
Post by Eric Yeh on Sep 9^th, 2002, 6:59am

Hey guys,

Hope I didn't scare everyone off with my request not to post solutions! I'd still love to know how people are doing with this one!! Let me know if it was too easy!!! Or if everyone who was interested is already done with it. In either case, I would be happy to post a new puzzle... ;) (But I'm also happy to wait if people are still mopping up on this one! :) )

Happy puzzling,
Eric

Title: Backward case
Post by TimMann on Sep 11^th, 2002, 12:19am

To avoid spoilers I could just post some inane comment like "that was easy", but instead I'll post a solution hidden by color. :)

Here's one solution, which was pretty
much the first thing I tried.

1) Left: Is AND on the left?

2a) If answer 1 was yes, AND is on the left,
and the "yes" anded with his next answer
will leave that answer unchanged, so next ask:
"Left: Is OR in the middle?"
This resolves the other two positions; done.

2b) If answer 1 was no, OR or XOR is on the left,
and the "no" ored or xored with his next
answer will leave that answer unchanged, so
next ask "Left: Is XOR on the left?"

3a) If answer 2b was no, OR is on the left,
and the two nos ored with his next answer
will leave that answer unchanged, so
next ask "Left: Is AND in the middle?"
This resolves the other two positions; done.

3b) If answer 2b was yes, XOR is on the left,
and the no + yes xored with his next answer
will complement that answer, so next ask
"Left: Is AND in the middle?" Complement
the answer you get to resolve the other
two positions; done.

Title: Universal case
Post by TimMann on Sep 11^th, 2002, 1:17am

Jonathan's solution to the Universal case checks out, but here's a different one that I think is interesting because it points toward an approach to the Selfless case as well.

Consider this question.

Q1: Is the following true?
a) You are on the left and AND is sitting leftward of OR, or
b) You are in the middle and OR is sitting leftward of XOR, or
c) You are on the right and XOR is sitting leftward of AND.

Note: "sitting leftward" here is strictly linear: AOX, AXO, and XAO are the cases where AND is sitting leftward of OR.

One solution is to ask Q1 once and ask "Q2: Are you AND?" twice. You must speak to a different god each time, but it doesn't matter in what order you speak to them or in what order you use the questions.

Why does this work? AND's answer to Q2 is yes, so when you speak to him, what he says is the answer to (Q1 AND Q2 AND Q2) = (Q1 AND yes AND yes) = Q1. On the other hand, for OR, Q2's answer is no, so what he says is (Q1 OR no OR no) = Q1. For XOR, Q2's answer is no, so what he says is (Q1 XOR no XOR no) = Q1 as well.

Thus you've gotten each god to answer Q1 truthfully. Due to the guards ("you are on the left and..."), the question gives you different information from each god, just enough to identify them. The inner questions could have been any set of three questions that distinguish the 6 seating orders, but I liked the symmetry of the three given above.

Next to think about: what else could you do with question Q1?

More on the above:

A second way to use Q1 would be to ask it three times. Since (p AND p AND p) = p, (p OR p OR p) = p, and (p XOR p XOR p) = p for any truth value p, again this gets each god to simply answer Q1 itself.

Title: Selfless case
Post by TimMann on Sep 11^th, 2002, 1:26am

This follows on from my previous post. I don't yet have a clue whether or not it is optimal, but extending the previous solution to Universal gives a solution to Selfless.

Note that Eric's clarification to Selfless is very important. To state it another way, in Selfless, each god's answer is his operator applied to all questions on your list other than the one you are addressing to him right now, including questions you may address to him in the past or future. The statement on the main puzzle page (and the name "Selfless") makes it sound like questions you ask(ed) of this god in the past or future are also excluded. But that would create temporal paradoxes, so it wouldn't make sense as part of the rules.

Now a spoiler -- a possibly non-optimal solution to Selfless:

Question Q1 from my previous post immediately provides a 4-question solution to Selfless. Simply ask Q1 four times, at least once of each god. Then each answer is again the xor of three copies of Q1, which is just Q1 again.

The second time you ask Q1 of the same god, you already know what he's going to say (same as last time you asked!), but you have to ask it anyway. If you had the question on your list but you walk away without asking it, the gods will strike you down in wrath. Well, or at least they'll bill you for the 4 questions that were on your list anyway. :)

I don't know yet if there is a 3-question solution to Selfless. Must sleep now...

Eric, thanks for the cool puzzles.

Title: Selfless case improved
Post by TimMann on Sep 11^th, 2002, 2:20am

Guess I didn't need to sleep on that one. Here is a better solution to Selfless.

Ask this question once of each god:
"Q3: Is OR not sitting in the next position cyclically after yours?" By "cyclically after" I mean that the next position after the last position is the first position again.

XOR's reply is (Q3 XOR Q3) = No.

Because OR is sitting in his own position, not in the position cyclically after his own, Q3 is true for him, so he replies (Q3 OR Q3) = (Yes OR Yes) = Yes.

AND's answer to Q3 distinguishes the cases AOX, XAO, OXA (where he says No) from the cases OAX, XOA, AXO (where he says Yes). His reply is (Q3 AND Q3) = Q3.

Making a table, this works:

A O X -> N Y N
A X O -> Y N Y
O A X -> Y Y N
O X A -> Y N N
X A O -> N N Y
X O A -> N Y Y

Comment on my thought process: this was inspired by Jonathan's solution to Universal -- not by the particular questions, but by the structure of the mapping between yes/no replies and positions -- combined with my previous idea (spoiler: i.e., asking the same question all three times).

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Sep 11^th, 2002, 6:22am

Tim,

Nice job with all the answers! Very elegant.

Some follow-up questions:

1) Can you solve the Backward scenario without dynamic questions?
2) Find with proof the minimum number of Gods you need to speak to in each scenario.

BTW, "is not cyclically after" == "is cyclically before". ;)

Have you solved my other three posted puzzles?

Best,
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Jonathan_the_Red on Sep 11^th, 2002, 11:11am

on 09/11/02 at 06:22:01, Eric Yeh wrote:

1) Can you solve the Backward scenario without dynamic questions?

I can.

1) Is A AND? (asked of A)
2) Is A XOR? (asked of A)
3) Is B XOR? (asked of B)

OAX N N N
OXA N N Y
XOA N Y Y
XAO N Y N
AOX Y N Y
AXO Y N N

Quote:

BTW, "is not cyclically after" == "is cyclically before". ;)

Not exactly.

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Jonathan_the_Red on Sep 11^th, 2002, 11:19am

Here's a slightly slicker Backwards solution:

Ask all of these of A.

1) Are you AND?
2) Are you not OR?
3) Is XOR next cyclically left of AND?

OAX N N N
OXA N N Y
XOA N Y Y
XAO N Y N
AOX Y Y N
AXO Y Y Y

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Sep 11^th, 2002, 11:27am

Yep, now you're talking!! The cool thing is that, within some reasonable definition of equivalence, I believe this solution is unique!! (So I wouldn't say just "slightly" ;) )

Ye ye, I guess what I said about those cyclicals isn't quite true, my mistake. :P :P I just thought it sounded funny grammatically.

Best,
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by TimMann on Sep 11^th, 2002, 11:23pm

on 09/11/02 at 06:22:01, Eric Yeh wrote:

1) Can you solve the Backward scenario without dynamic questions?

I'll resist looking at the spoiler and give that one a try later on.

Quote:

2) Find with proof the minimum number of Gods you need to speak to in each scenario.

Backward follows trivially from my dynamic-question solution:

My solution speaks to only one god. Speaking to no gods is obviously out, so 1 is minimal.

Universal is easy:
a) Since you need more than 2 bits of information, and each answer supplies at most one bit of information, you need at least three answers.

b) Every time you speak to a god in the Universal scenario, he must say the same thing, because his answer is always his operator applied to all your questions. So speaking to the same god more than once provides no additional information.

Therefore you have to speak to all three gods at least once each. We have solutions that do that, so 3 is minimal.

For Selfless, I need to think about it some more. Solutions like mine clearly require talking to all three gods. (Since all three questions are the same, talking to the same god more than once gives you the same answer each time, as with Universal.) But I don't have a proof that a solution to Selfless has to work that way.

Quote:

Have you solved my other three posted puzzles?

I solved Past/Present/Future and Gibberland. PPF was a nice hard puzzle, though it's too bad the solution wasn't pretty or unique. Gibberland was excellent, a real mind-wrecker. Was there another problem of yours too? I don't think I found it.

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Sep 12^th, 2002, 6:00am

Tim,

Yup, nice job so far; enjoy those two last follow-ups.

(For the min q's q, I actually meant non-dynamically when possible, but it's too much of a bother to ask you to keep trying these minor variations so I'll refrain! But my general "hierarchy" of responses is:

1) Min questions
2) Non-dynamic questions
3) Non-dynamic answerers
4) Min answerers

Regarding my other puzzle: see the "Puzzle Forum" new problem in the hard threads. Will hasn't promoted it to being shown on the main page yet, perhaps because of the tastelessness. ;) ;) ;)

Best,
Eric

Title: Static backward, etc.
Post by TimMann on Sep 12^th, 2002, 11:48pm

On the static solution to Backward, it was pretty easy to come up with one. Mine turned out to be similar in structure to Jonathan's, as you suggested it must be:

Ask of the leftmost guy:

1) Are you AND?
2) Is XOR leftward of OR? (note: not next leftward cyclically)
3) Is AND in the middle?

AOX YNN
AXO YYN
OAX NNY
OXA NNN
XAO NYN
XOA NYY

Note that you have the opportunity to get some extra information. Since these guys are omniscient, you might as well change question 3 to "Is either of the following true? (a) AND is in the middle, or (b) you are AND and Willywutang wears boxer shorts." If you luck out and the arrangement is AXO, you can find out about Willy's underwear, or any other deep secret of the universe you care to ask about.

The design prinicple I used in the above was to avoid making AND say no or OR say yes until I no longer needed any more information, since their giving those answers "pegs" their answers afterward. It looks like Jonathan was doing that too. In fact, he actually avoiding having AND say no or OR say yes until the last question.

However, you don't really have to do that at all:

Ask of the leftmost guy:

1) Is AND leftward of XOR?
2) Is OR leftward of XOR?
3) Is OR leftward of AND?

AOX YYN
AXO YNN
OAX YYY
OXA NYY
XAO NNN
XOA NNY

Notice that OR says yes to question 1 in the OAX case, so he's pegged at "yes" thereafter, but we get enough information to solve the puzzle anyway. I'm sure you can also construct a solution where OR gets pegged to YYY in one case and AND gets pegged to NNN in another.

The above solution has a different cute property, though. Can you see what it is? (Spoiler: Every answer given is always the correct answer to the question being asked. That is, you'd get the same results if AND, OR, and XOR all forgot to apply their namesake operations and simply answered the questions at hand!)

By the way, since my previous dynamic solution was static in who it asked each question of, there's a mechanical way to convert it to fully static by putting the conditions into the questions themselves instead of into the procedure for deciding what to ask. But that would make an unwieldy solution.

Finally, since these solutions are fully static and involve talking to only one god (like Jonathan's did), that of course establishes the lower bound for min answerers in static solutions.

Title: Selfless minimum answerers
Post by TimMann on Sep 13^th, 2002, 1:56am

Here's a way to show the minimum number of distinct answerers for static Selfless:

Ask the leftmost guy:

1) Is grass red?
2) Is XOR not the rightmost?
3) Is the order not XOA?


seating  true    given
 order  answers answers 
------- ------- -------
  AOX     nny     NNN
  AXO     nyy     YNN
  OAX     nny     YYN
  OXA     nyy     YYY
  XAO     nyy     NYY
  XOA     nyn     YNY

Thus 1 is the minimum number of distinct answerers.

There may be a more elegant set of questions, but I got tired. I still like my previous solution better: it has a minimal number of distinct questions. :P

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Sep 13^th, 2002, 6:13am

have very little time -- but took a glace. why does anyone answer Y to "is grass red?"??!

e

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Jonathan_the_Red on Sep 13^th, 2002, 10:00am

Here's a "perfect" answer to Universal. Yep... static questions, asking one God. Really.

For 1 <= n <= 3, let N be the proposition: "I am currently asking question #n" (this is the secret!) Let O be the proposition: "You are not OR."

Note that "not-N implies O" is true if you're asking question n. If you're not asking question n, "not-N implies O" is true if you're speaking to AND or XOR, but false if you're asking OR.

Let P be any proposition. You can then ask: "Does N imply P and does not-N imply O?" and get a truthful answer to P. Suppose for the three questions, you'll use propositions P1, P2, and P3. When you're asking question 1, this becomes

P1 AND TRUE AND TRUE for AND,
P1 XOR TRUE XOR TRUE for XOR,
P1 OR FALSE OR FALSE for OR

... all of which are equivalent to P1.

So the problem reduces to the easy task of finding three static questions that will produce unique answers for the six possible arrangements. One such arrangement that works is:

Are you AND?
Are you OR?
Is XOR next cyclically left of AND?

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by TimMann on Sep 13^th, 2002, 9:06pm

on 09/13/02 at 06:13:40, Eric Yeh wrote:

have very little time -- but took a glace. why does anyone answer Y to "is grass red?"??!

They don't, of course. As the middle section of the table shows, the correct answer to "is grass red?" is always no. This doesn't keep the solution from working, because the gods don't answer the questions p, q, r that you ask them. They answer questions like p AND q, q OR r, p XOR s, etc. -- as you know very well, of course!
;D

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by TimMann on Sep 13^th, 2002, 9:17pm

on 09/13/02 at 10:00:56, Jonathan_the_Red wrote:

Here's a "perfect" answer to Universal. Yep... static questions, asking one God. Really.

Neat, another kind of dynamic binding. I only considered the binding of "you" to "the god I'm talking to as I ask this question". I never thought about "the number of the question I'm currently asking" as a dynamic element that would be substituted into the other two questions as well as the one I'm actually currently asking. I think I failed to think in this direction because of the warning against paradoxes, which rules out things like references to "the next question" or "your answer to this question", etc. -- but what you've done doesn't cause a paradox. I like it. I wonder if Eric thought of that. :D

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Sep 16^th, 2002, 11:58am

on 09/13/02 at 21:06:06, TimMann wrote:

Tim,

Ye, I read your two posts too quickly, I suppose -- I didn't notice the transition from the Backward case to the Selfless case.

I certainly agree w most of your reply #25 -- as usu there are wasted part-bits, but it is rare to not have those (as per Knight, Knave, Random). I could have had them speak Gibberish to save an additional .1335 of a bit, but to me it's not quite worth it as a tradeoff for the character of the puzzle.

Yes, you can do the "pegging", as you call it, to the response sets other than the ones which allow continually meaningful responses, but I have yet to see one that I consider elegant, or even intuitively constructed. (I agree that your "cute property" is cute, but not necessarily intuitive :) )

Lastly, yes, I agree the mechanical conversion is possible but unwieldy. Like I said in the beginning of this topic, this particualr set of puzzles is very much about elegance. :)

Regarding your reply #26, nice job! Out of curiosity, was there a method to the madness?

Best,
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Sep 16^th, 2002, 12:12pm

on 09/13/02 at 10:00:56, Jonathan_the_Red wrote:

Here's a "perfect" answer to Universal. Yep... static questions, asking one God. Really.

Jonathan,

With no slight intended toward the cleverness of your solution (which there certainly is! :) ), this kind of solution was to me, as Tim mentioned, off-limits.

The general rule I in my mind is that questions cannot be self-referential in any sense, and this includes in the sense of the timing of the questions. For example, we would not want to allow PPF questions to directly involve "when they are being answered". Another point is that this kind of solution requires a sort of "implementation-dependent" assumption regarding how the gods "hear" and "interpret" the questions. One could imagine a PPF-like world where the gods live out-of-phase with human perception of time, in which case phrases such as "the question I am currently asking" would not make sense.

In any case, I appreciate both your interest in my puzzle and your clever solution to it, be it outside the intended bound or not. So I certainly mean no offense, and hope none is taken! :)

Best,
Eric

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by TimMann on Sep 16^th, 2002, 9:08pm

on 09/16/02 at 11:58:03, Eric Yeh wrote:

Regarding your reply #26, nice job! Out of curiosity, was there a method to the madness?

I started out by making a list of the possible reply sequences that could be given by each god if he happened to be the one you asked. XOR's 3rd answer has to be the XOR of his first two answers, AND can't say yes exactly once, and OR can't say no exactly once. I assigned feasible response sequences to orderings in what seemed a likely way, then played around looking for questions that would generate those responses, mostly working from the top of the table to the bottom, and sometimes switching around the response sequences when it looked like what I was trying wouldn't work. I came up with something that worked before long. It was not pretty, but I was tired, so I typed it in and went to bed.
:)

Title: Re: NEW PROBLEM: The Operators of Boolania
Post by Eric Yeh on Sep 17^th, 2002, 5:24am

Well, good job! Ye, the first half of your analysis (re: A&O) is exactly like mine. (I got a little extra structure out of it by placing a further condition on X, but that was not as important.)

Best,
Eric