[seqfan] Re: True-False text sequence

[Jonathan Post]

That was originally Ulam's problem.  The solution for n=1 was known
quickly,  n=2 took a few years.  n=3 took a few more years.

Then someone saw that the n=3 solution (found ad hoc) used the  binary
Golay code, which is a well-known  perfect linear error-correcting
code.

I have written more about the history and implications of this problem
in some draft papers with professor Philip Vos Fellman, part of a
decade-long research we call "Mathematical Disinformation Theory."

The issue being that wrong answers in generalized "20 questions" games
need not be "random" but may be due to a very clever opponent
misleading you as much as possible, and knowing your Belief Revision
Algorithm. This quickly leads to deep questions in bisimulation and
computability of multi-agent modeling (A knows that B knows that C
knows that A seems to believe B, when B lied about what B knows about
C...".  I have a draft monograph 100 pages long on this issue of
combining Epistemic Logic with Temporal Logic.

Charles Greathouse has been of inestimable value in helping me with
other (merely Propositional) Logic enumeration problems, in a paper
which narrowly was refereed out of one one conference, and shall be
resubmitted elsewhere.

-- Jonathan Vos Post

On Wed, Jan 18, 2012 at 1:20 PM, Charles Greathouse
<charles.greathouse at case.edu> wrote:
> Tanya Khovanova has two blog entries
> http://blog.tanyakhovanova.com//?p=386
> http://blog.tanyakhovanova.com/?p=387
> discussing a sequence.  Is this (or a translate) in the OEIS?  If not,
> would someone add it?
>
> Quick definition: a(n) is the least number of guesses needed, in the
> worst case, to find all the answers to an n-question true-or-false
> test, where a guess consists of answering each question and learning
> the total number of correct guesses.  This is related to Bulls and
> Cows (aka Mastermind).
>
> Knop and Mednikov prove upper bounds on the non-adaptive version,
> which of course give upper bounds on the adaptive version as well.
> Probably both should be in the OEIS.  The text of their paper is in
> Russian,
> http://www.mccme.ru/free-books/matpros/mpe.pdf
> The paper is in Russian, and despite some work at Gould's text I'm not
> able to read it.  There may be more results (or references) beside the
> one Tanya mentions.
>
> Charles Greathouse
> Analyst/Programmer
> Case Western Reserve University
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/