We exhibit a family of computably enumerable sets which can be learned within polynomial resource bounds given access only to a teacher but which requires exponential resources to be learned given access only to a membership oracle. In general, we compare the families that can be learned with and without teachers and oracles for four measures of efficient learning.

Jockusch and Lewis proved that every DNC function computes a bi-immune set. They asked whether every DNC function computes an effectively bi-immune set. We construct a DNC function that computes no effectively bi-immune set, thereby answering their question in the negative.

The present work determines the arithmetic complexity of the index sets of u.c.e. families which are learnable according to various criteria of algorithmic learning. Specifically, we prove that the index set of codes for families that are TxtFex\-learnable is \-complete and that the index set of TxtFex\-learnable and the index set of TxtFext\-learnable families are both \-complete.

Given any oracle, A, we construct a basic sequence Q, computable in the jump of A, such that no A-computable real is Q-distribution-normal. A corollary to this is that there is a Δn+10 basic sequence with respect to which no Δn0 real is distribution-normal. As a special case, there is a limit computable sequence relative to which no computable real is distribution-normal.