1
$\begingroup$

Background

A class of languages $C$ has Gold's Property if $C$ contains

  1. a countable infinite number of languages $L_i$ such that $L_i \subsetneq L_{i + 1}$ for all $i > 0$
  2. a further language $L_\infty$ such that for any $i > 0$, if $x \in L$ then $x \in L_\infty$.

Then, Gold's theorem is:

Any class of languages with Gold's Property is unlearnable

In other words, Gold's Property is a sufficient condition for unlearnability.

Question

What is the weakest (natural) necessary condition? In other words, I want the weakest property $P$ such that:

Any unlearnable class of languages has property $P$

In particular: is Gold's Property such a property? Can Gold's theorem be strengthened to an if and only if?

Alternatively, as @TsuyoshiIto pointed out in the comments:

What is a sufficient condition for a class of languages to be learnable?

  • 1
    I would ask for sufficient conditions for learnability rather than necessary conditions for unlearnability because the latter sounds confusing.2012-02-03
  • 0
    @TsuyoshiIto thank you for the suggestion, I added it to the question.2012-02-03
  • 0
    Could you point to a definition of "learnable"/"unlearnable"?2012-02-03
  • 0
    You may want to take the question to brand-new [cs.SE](http://cs.stackexchange.com)!2012-03-23

1 Answers 1