5.1 Gold’s Question
Fix a countable domain. In Gold’s original setting, this is the set of all strings over a finite alphabet \(\Sigma \), and the objects to be learned are formal languages \(L \subseteq \Sigma ^*\). We work in this setting when it clarifies the recursion-theoretic content, and in the general setting of concept classes \(\mathcal{C} \subseteq 2^\mathbb {N}\) when it does not matter.
The learner receives data sequentially, one datum at a time, forever. Two data presentation modes are standard:
Let \(L \subseteq \Sigma ^*\) be a language.
- [leftmargin=*,itemsep=2pt]
A text for \(L\) is an infinite sequence \(t = (t_0, t_1, t_2, \ldots )\) with \(\{ t_i : i \in \mathbb {N}\} = L\). Every element of \(L\) appears at least once; no element of \(\Sigma ^* \setminus L\) ever appears. The text may contain repetitions and need not follow any fixed ordering.
An informant for \(L\) is an infinite sequence of labelled pairs \(((s_0, b_0), (s_1, b_1), \ldots )\) where \(\{ s_i : i \in \mathbb {N}\} = \Sigma ^*\) and \(b_i = 1\) if and only if \(s_i \in L\). Every string is eventually presented together with its membership status.
Text presents only positive examples; informant presents both positive and negative examples. This distinction matters enormously: Gold showed that informant is strictly more powerful than text. We focus on text, which is the harder and more interesting case.
After seeing the first \(n\) data points \((t_0, \ldots , t_{n-1})\), the learner outputs a hypothesis \(h_n\). The hypothesis is an index, a natural number naming a program that computes a language. The learner has no deadline, no accuracy target, and no probability distribution on targets. It simply sees more and more of \(L\) and must eventually guess correctly.