Language identification in the limit

Gold, ‘Identification’

0.1. Theorem.  

0.2. Definition.   Let $𝐴$ be a finite alphabet and $𝐿\subseteq {𝐴}^{\ast }$ a language.

0.3. Definition.   A text for $𝐿$ is a sequence $⟨{𝑥}_1,\dots$ such that $\left\{{𝑥}_1,\dots \right\}=𝐿$.

0.4. Definition.   A test for $𝐿$ is a procedure to decide whether some string $𝑠\in {𝐴}^{\ast }$ is a member of $𝐿$.

0.5. Definition.   Suppose we are given a language $𝐿$ from some class of languages $𝐶$ and the task is to construct a Turing machine that tests membership of $𝐿$.

The way the Turing machine is constructed is that the text is read over the strings ${𝑥}_1,{𝑥}_2,\dots$. Each time a string is presented, some hypothesis Turing machine ${𝑔}_{𝑡}$ is generated.

We say that $𝐿$ is identifiable in the limit if there is some $𝑠$ such that for all $𝑡⩾𝑠$, ${𝑔}_{𝑡}$ is a (correct) test for $𝐿$.

We now state the main result.

Suppose that the class of languages $𝐶$ contains all finite languages and at least one infinite language. Then $𝐶$ is not identifiable in the limit from texts.

References

Gold, E Mark, ‘Identification’: ‘Language identification in the limit’, Information and Control 10.5 (1967), pp 447–474.