 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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
|
|
| |
| |
|
|
|
|
| |
