Learning theory in the arithmetic hierarchy. II. (Q2663335)

In the paper under review the authors determine the arithmetic complexity of the index sets of uniformly computably enumerable (c.e.) families which are learnable according to various criteria of algorithmic learning. A computable function \(M : 2^{<\omega}\rightarrow\omega\), \(EX\)-learns a c.e. set \(A\subseteq\omega\) iff, for any enumeration \(f: \omega\rightarrow\omega\) of \(A,\) \((\exists e) (W_e=A) \& (\forall^{\infty} n)(M(f\lceil n) = e)\). \par A computable machine \(M\) \(EX\)-learns a uniformly c.e. family \(F\) if it \(EX\)-learns every \(A\in F\). A computable function \(M : 2^{<\omega}\rightarrow \omega\) TxtFex\(^{*}_{*}\)-learns a c.e. set \(A\) if, given any enumeration \(f : \omega\rightarrow \omega\) of \(A\), there is a finite set \(F\) such that \\ \((\forall^{\infty}n)(M(f\lceil n)\in F)\) and \((\forall e\in F)(W_e \mbox{ and } A \mbox{ have finite symmetric difference})\). If the symmetric difference \(W_e \bigtriangleup A\) is permitted to have cardinality at most \(a\) and only \(b\) many vacillations are allowed, the resulting learning criterion is denoted TxtFex~\(^a_b\). \par The authors prove that the index set of codes for families that are TxtFex\(^a_b\)-learnable is \(\Sigma_4^0\)-complete and that the index set of TxtFex\(^*_*\)-learnable families is \(\Sigma_5^0\)-complete. For Part I see [the first author, J. Symb. Log. 79, No. 3, 908--927 (2014; Zbl 1355.03033)].