Formal Learning Theory Kernel: Blueprint v1

We construct a class \(\mathcal{L}\) that separates \(\mathbf{BC}\) from \(\mathbf{Ex}\).

For each total recursive function \(f : \mathbb {N}\to \mathbb {N}\), define the language \(L_f = \{ \langle n, f(n)\rangle : n \in \mathbb {N}\} \), where \(\langle \cdot , \cdot \rangle \) is a computable pairing function. Let \(\mathcal{L} = \{ L_f : f \text{ is total recursive}\} \).

\(\mathcal{L}\) is \(\mathbf{BC}\)-identifiable. Given a text \(t\) for some \(L_f\), at time \(n\) the learner has seen finitely many pairs \(\langle n_i, m_i\rangle \). Define the partial function \(g_n\) by \(g_n(n_i) = m_i\) for all pairs seen so far, and \(g_n(k) = 0\) for all other \(k\). Output an index for the language \(L_{g_n} = \{ \langle k, g_n(k)\rangle : k \in \mathbb {N}\} \). Once all pairs \(\langle k, f(k)\rangle \) for \(k \leq K\) have appeared (for any \(K\)), the hypothesis computes \(L_f\) correctly on \(\{ 0, \ldots , K\} \). As \(n \to \infty \), \(g_n\) converges pointwise to \(f\). Since \(f\) is total, for every \(k\) there exists a time after which \(g_n(k) = f(k)\). The language computed by the hypothesis is eventually \(L_f\), though the index keeps changing as new pairs are absorbed. This is \(\mathbf{BC}\)-identification.

\(\mathcal{L}\) is not \(\mathbf{Ex}\)-identifiable. Suppose for contradiction that a learner \(M\) \(\mathbf{Ex}\)-identifies \(\mathcal{L}\). We diagonalize against \(M\). Define a total recursive function \(f\) as follows.

Begin presenting pairs \(\langle 0, 0\rangle , \langle 1, 0\rangle , \langle 2, 0\rangle , \ldots \) (corresponding to the zero function). Wait until \(M\) converges to some index \(e\). Since \(M\) \(\mathbf{Ex}\)-identifies \(\mathcal{L}\) and the zero function is total recursive, \(M\) must converge. Now \(W_e = L_{\mathbf{0}}\) (the language of the zero function).

Modify \(f\): set \(f(k) = 1\) for some large \(k\) not yet presented. This changes the target to a different total recursive function, but the text presented so far is consistent with both targets. The learner \(M\) has already committed to index \(e\), which computes \(L_{\mathbf{0}} \neq L_f\). By a careful effectivization of this argument (choosing \(k\) computably based on \(M\)’s behavior), we construct \(f \in \mathcal{L}\) on which \(M\) fails. This contradicts \(M\) \(\mathbf{Ex}\)-identifying all of \(\mathcal{L}\).

The essential point is that \(\mathbf{BC}\)-identification does not require the index to stabilize, only the extension. The class \(\mathcal{L}\) exploits this: the learner must continually update its program as new pairs arrive, and the programs keep changing, but they all eventually compute the same language. \(\mathbf{Ex}\)-identification cannot tolerate this perpetual updating of indices.