 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
So according to my calculations, a game of 20 questions can distinguish
between up to 1,048,576 things, assuming only yes/no questions. Not bad...
--
Tim Cook
http://home.bellsouth.net/p/PWP-empyrean
-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GFA dpu- s: a?-- C++(++++) U P? L E--- W++(+++)>$
N++ o? K- w(+) O? M-(--) V? PS+(+++) PE(--) Y(--)
PGP-(--) t* 5++>+++++ X+ R* tv+ b++(+++) DI
D++(---) G(++) e*>++ h+ !r--- !y--
------END GEEK CODE BLOCK------
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> So according to my calculations, a game of 20 questions can distinguish
> between up to 1,048,576 things, assuming only yes/no questions. Not
> bad...
Thinking up the actual questions to distinguish between 1048576 things is
another matter though... ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
That's just plain bad thinking all round. I assume you meant yes/no answers not
questions. I don't think yes/no as a question will help you identify anything
and of course there's no fixed number of questions, they can be different at
every level so you have many many many more permutations. Or is it just
fortunate that I've always picked something of that list! ;)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
MattM wrote:
> and of course there's no fixed number of questions, they can be different at
> every level so you have many many many more permutations. Or is it just
> fortunate that I've always picked something of that list! ;)
Au contrare... If 20 questions will be asked yielding 20 yes/no answers,
than 2^20 things can be distinguished. The fact that the questions on
one branch may or may not be the same as the ones on another branch is
irrelevant. There are still the same number of branches. [Although
obviously as a *practical* matter being able to have more relevent
quenstions on the different branches helps a lot.]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Question 1. Is it a fish?
Answer 1. Yes
Question 2. Is it a cat?
Answer 2. (Are you stupid?)
I think Question 1 (in this universe) usually drives question 2. So at the start
of the game Question 2 can still be anything as we don't know what the answer to
one is yet. In fact question 1 can be anything. (Are you Hilary Clinton? are you
an vegetable? Do your ears turn purple when listening to Pearl Jam?) So off the
bat we have '2^However many questions you can think of' and that's just
question 1.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> [Although obviously as a *practical* matter being able to have more
> relevent quenstions on the different branches helps a lot.]
You just need to think of a question that will exactly split the remaining
outcomes in half each time. For 2^3 or 2^4 items this is doable, but for
2^20...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> [Although obviously as a *practical* matter being able to have more
>> relevent quenstions on the different branches helps a lot.]
>
> You just need to think of a question that will exactly split the
> remaining outcomes in half each time. For 2^3 or 2^4 items this is
> doable, but for 2^20...
Question: Is the set of possible outcomes recursively enumerable?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
No, next question. (Is this a game now?)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Can a set exist that has a finite cardinal number and yet is not
recursively enumerable?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I'm afriad that won't split this problem 50/50. That's the problem with this
game, sometimes yes/no is not enough. I really want to say, you're making an
assumption. Is your question even related? Who said anything about finite?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
MattM wrote:
> Is your question even related? Who said anything about finite?
http://en.wikipedia.org/wiki/Recursive_set
"A subset S of the natural numbers is called recursive if there exists..."
"Every finite or cofinite subset of the natural numbers is computable."
Thus, the answer to my question is no. In order words, there exist no
finite sets which are not recursively enumerable.
Thus, as we have agreed the set of possible things to classify is not
recursively enumerable, we can conclude that it is not finite.
It is impossible to decide on an element of an infinite set using a
finite number of questions.
Thus, we can conclude that the game is in fact impossible to solve in
general.
Goodbye.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thank goodness, someone got there in the end.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> It is impossible to decide on an element of an infinite set using a
> finite number of questions.
Hmm, that's not entirely true.
Presumably it *is* however true for a set that isn't computable though.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> It is impossible to decide on an element of an infinite set using a
>> finite number of questions.
>
> Hmm, that's not entirely true.
>
> Presumably it *is* however true for a set that isn't computable though.
Damnit, where's Darren?? I'm sure he knows...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
MattM wrote:
> Question 1. Is it a fish?
> Answer 1. Yes
> Question 2. Is it a cat?
> Answer 2. (Are you stupid?)
Catfish! MMMmmmmm...
--
Darren New / San Diego, CA, USA (PST)
It's not feature creep if you put it
at the end and adjust the release date.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Catfish! MMMmmmmm...
Oh God - and now the squid...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> You just need to think of a question that will exactly split the
> remaining outcomes in half each time.
I think as long as there's *something* down either branch, you're OK. I
don't think it has to split things in half.
I did see one fun variant, where you start without having in mind
anything in particular, and the asker tries to guess what it is, and the
answerers each take a turn answering. The trick is that each answerer,
after hearing the previous questions and answers, has to come up with
something that matches the previous questions and answers.
--
Darren New / San Diego, CA, USA (PST)
It's not feature creep if you put it
at the end and adjust the release date.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>>> It is impossible to decide on an element of an infinite set using a
>>> finite number of questions.
>>
>> Hmm, that's not entirely true.
>>
>> Presumably it *is* however true for a set that isn't computable though.
>
> Damnit, where's Darren?? I'm sure he knows...
20 questions doesn't pick out elements of a set. It picks out
categories. "Is it a zebra?" "Yes." End of game. Tens of thousands of
possible zebras, along with an infinite number of possible-to-imagine
zebras, all qualify as "the" correct answer.
--
Darren New / San Diego, CA, USA (PST)
It's not feature creep if you put it
at the end and adjust the release date.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> 20 questions doesn't pick out elements of a set. It picks out
> categories. "Is it a zebra?" "Yes." End of game. Tens of thousands of
> possible zebras, along with an infinite number of possible-to-imagine
> zebras, all qualify as "the" correct answer.
"What do you mean? Is that an African Swallow or a European Swallow?"
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> You just need to think of a question that will exactly split the
>> remaining outcomes in half each time.
>
> I think as long as there's *something* down either branch, you're OK. I
> don't think it has to split things in half.
I meant that to be able to recognise 2^20 things, you need to ask a question
at each step that will split the set in half. Otherwise you will end up not
having enough questions left to uniquely identify each item.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"MattM" <mat### [at] hotmail com> wrote in message
news:web.476129ae74e493e34ef43cef0@news.povray.org...
> Question 1. Is it a fish?
> Answer 1. Yes
> Question 2. Is it a cat?
> Answer 2. (Are you stupid?)
> Do your ears turn purple when listening to Pearl Jam?)
But what does Apple Butter sound like?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>>> You just need to think of a question that will exactly split the
>>> remaining outcomes in half each time.
>>
>> I think as long as there's *something* down either branch, you're OK.
>> I don't think it has to split things in half.
>
> I meant that to be able to recognise 2^20 things, you need to ask a
> question at each step that will split the set in half. Otherwise you
> will end up not having enough questions left to uniquely identify each
> item.
Oh, right. But if there are 2^50 possible items, 2^20 can be identified
without splitting things exactly in half, methinks.
--
Darren New / San Diego, CA, USA (PST)
It's not feature creep if you put it
at the end and adjust the release date.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Ross wrote:
> "MattM" <mat### [at] hotmailcom> wrote in message
> news:web.476129ae74e493e34ef43cef0@news.povray.org...
>> Question 1. Is it a fish?
>> Answer 1. Yes
>> Question 2. Is it a cat?
>> Answer 2. (Are you stupid?)
>
>> Do your ears turn purple when listening to Pearl Jam?)
>
> But what does Apple Butter sound like?
>
>
Totally Jam-ing
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Oh, right. But if there are 2^50 possible items, 2^20 can be identified
> without splitting things exactly in half, methinks.
Well yes almost, actually if you have 2^50 items the last thing you want to
do is split in half at each stage. You'll end up not being able to identify
anything after 20 questions!
Assuming you want to maximise the number of identifiable items, you arrange
your questions so that all of the 2^20 outcomes point to a unique object,
apart from one which is the "unknown" branch. Then you can uniquely
identify 2^20-1 items, the rest being lumped in the "unknown" branch.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kind of fun =)
http://www.20q.net/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Attwood wrote:
> Kind of fun =)
> http://www.20q.net/
Darn it! You beat me to it!
--
Lisa: Oedipus killed his father and married his mother.
Homer: Who payed for THAT wedding?
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> Well yes almost, actually if you have 2^50 items the last thing you want
> to do is split in half at each stage. You'll end up not being able to
> identify anything after 20 questions!
Most 20Q games don't identify individual objects, tho. The identify
classes of objects. "Is it a zebra?" "Is it a cloud?" Stuff like that.
Otherwise, yes, if you're trying to cut it down to proper nouns, the
analysis is correct. :)
--
Darren New / San Diego, CA, USA (PST)
It's not feature creep if you put it
at the end and adjust the release date.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Darren New wrote:
>
>> Catfish! MMMmmmmm...
>
> Oh God - and now the squid...
>
No, no, no, no, no, no, and no. Squid??? With catfish???
And now the HUSH PUPPIES...
--Sherry "Knows How To Serve Catfish" Shaw
--
#macro T(E,N)sphere{x,.4rotate z*E*60translate y*N pigment{wrinkles scale
.3}finish{ambient 1}}#end#local I=0;#while(I<5)T(I,1)T(1-I,-1)#local I=I+
1;#end camera{location-5*z}plane{z,37 pigment{granite color_map{[.7rgb 0]
[1rgb 1]}}finish{ambient 2}}// TenMoons
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Cook <z99### [at] bellsouthnet> wrote:
> So according to my calculations, a game of 20 questions can distinguish
> between up to 1,048,576 things, assuming only yes/no questions. Not bad...
What if the answer were a specific person you've never heard of and will never
guess by elimination, and it's required to get a 20-letter proper name correct.
You're hosed, aren't you?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Invisible wrote:
>>>> It is impossible to decide on an element of an infinite set using a
>>>> finite number of questions.
>>>
>>> Hmm, that's not entirely true.
>>>
>>> Presumably it *is* however true for a set that isn't computable though.
>>
>> Damnit, where's Darren?? I'm sure he knows...
>
> 20 questions doesn't pick out elements of a set. It picks out
> categories. "Is it a zebra?" "Yes." End of game. Tens of thousands of
> possible zebras, along with an infinite number of possible-to-imagine
> zebras, all qualify as "the" correct answer.
>
Categories can be elements. After all, you can have a set of
categories. The only difference between "zebra" and "Betty-the-Zebra at
our local zoo" is the level of specificity. The question answerer could
choose either in this game.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> scott wrote:
>> Well yes almost, actually if you have 2^50 items the last thing you
>> want to do is split in half at each stage. You'll end up not being
>> able to identify anything after 20 questions!
>
> Most 20Q games don't identify individual objects, tho. The identify
> classes of objects. "Is it a zebra?" "Is it a cloud?" Stuff like that.
That's not the way I remember it. Hmm.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
