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