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?

  • 0
    You may want to take the question to brand-new [cs.SE](http://cs.stackexchange.com)!2012-03-23

1 Answers 1

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.