Docs / Studies / Studies.Gold1967

Language identification in the limit

Gold, E. M. (1967). Information and Control, 10(5), 447–474

A learner receives information about an unknown language at each moment and guesses the language; it succeeds if its guesses are eventually constant and correct. From a text, which presents only members of the language, the finite languages can be identified but no proper superclass of them can, so that not even the regular languages are identifiable, and so not the context-free languages. From an informant, which also says which strings are not members, any countable class can be identified, by guessing the first language in an enumeration that agrees with the information so far. Since children appear to learn from positive instances alone, Gold concludes that if a text is all they have, the possible natural languages, if they include an infinite one, cannot include all the finite ones.

Implementation notes

Identifiability here is what Gold calls ineffective: a guessing rule is any function, so the choice of naming relation does not arise and only arbitrary text and arbitrary informant are considered. Table I's positive results for effective guessing rules are not formalized, nor is its anomalous row, which turns on primitive recursive text.

References

  • Gold 1967, Language identification in the limit

Text

Theorems I.8 and I.9 as stated for ineffective identification in §8: every proper superclass of the finite languages is not identifiable from text, so the class of possible natural languages, if it contains languages of infinite cardinality, cannot contain all languages of finite cardinality when a text is all the child receives (§4).

theorem not_identifiable_of_finite_ssubsetL55–62
{α : Type u_1} [Countable α] {𝓛 : Set (Set α)} (h : {L : Set α | L.Finite} ⊂ 𝓛) :

The classes of Table I

Every finite language is regular: its left quotients are subsets of the finitely many suffixes of its members.

theorem isRegular_of_finiteL70–76
{σ : Type u_2} {L : Set (List σ)} (hL : L.Finite) :
Language.IsRegular L
L78–81

Informant

L97–100

From an informant every countable class is identifiable, by identification by enumeration: guess the first language of an enumeration that agrees with the information. Whereas a language properly containing the unknown one is never contradicted by a text, an informant eventually contradicts every other language.

theorem exists_identifiesFromInformant_of_countable§8L124–163
{α : Type u_1} {𝓛 : Set (Set α)} (hc : 𝓛.Countable) :
∃ (φ : List (α ⊕ α) → Set α), ∀ L ∈ 𝓛, IdentifiesFromInformant φ L

Built from