Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
I would ask for sufficient conditions for learnability rather than necessary conditions for unlearnability because the latter sounds confusing. –  Tsuyoshi Ito Feb 3 '12 at 11:54
    
@TsuyoshiIto thank you for the suggestion, I added it to the question. –  Artem Kaznatcheev Feb 3 '12 at 12:10
    
Could you point to a definition of "learnable"/"unlearnable"? –  Henning Makholm Feb 3 '12 at 13:37
    
You may want to take the question to brand-new cs.SE! –  Raphael Mar 23 '12 at 23:37

1 Answer 1

Gold's property does not characterize languages learnable in the limit from positive examples. However, Angluin (1980; pdf) does give a property that is both necessary and sufficient:

An indexed family $C$ of nonempty languages $\{L_1,L_2,..\}$ has Angluin's Property if there exists a Turing Machine which on any input $i \geq 1$ enumerates a finite set of strings $T_i$ such that $T_i \subseteq L_i$ and for all $j \geq 1$ if $T_i \subseteq L_j$ then $L_j$ is not a proper subset of $L_i$.

Informally, this property says that for every language $L$ in the family, there exists a "telltale" finite subset $T$ of $L$ such that if another language $L' \neq L$ in the family contains $T$ then there is some positive example $x \not\in L$ but in $L'$.

Angluin (1980) proves that:

An indexed family of nonempty recursive languages is learnable from positive data (in the sense of Gold) if and only if it has Angluin's Property.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.