5.4.4 Trial and Error
A trial-and-error predicate for a set \(A \subseteq \mathbb {N}\) is a computable function \(f : \mathbb {N}\to \{ 0, 1\} \) such that \(\lim _{s \to \infty } f_s(n)\) exists for all \(n\) and equals the characteristic function of \(A\). The learner may “retract” previous outputs: it learns by making mistakes and correcting them.
Trial-and-error learning connects identification in the limit to the arithmetical hierarchy. A set \(A\) is trial-and-error learnable if and only if \(A \in \Delta ^0_2\), the class of sets that are both \(\Sigma ^0_2\) and \(\Pi ^0_2\). This is the precise recursion-theoretic characterization, due to Putnam [ and Gold: the limit-computable functions are exactly the \(\Delta ^0_2\) functions. This connection places Gold-style learning firmly within the landscape of classical recursion theory.