# Converse of Gold's theorem and necessary condition for unlearnability

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

-
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

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.

-