Converse of Gold's theorem and necessary condition for unlearnability

280 Views Asked by At

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?