For this talk we represent knowledge simply as computer program. A program for a function f represents knowledge of how to compute f - and it may contain additional information, perhaps implicit and needing to be extracted.
Our setting is Gold-style computational learning theory in which all the data points from the graph of a function f are successively fed into an algorithmic learning device, and that device outputs a corresponding sequence of computer programs - in the "hope" those output programs will converge to a program or programs which successfully compute f. Investigated are some surprising and delicate tradeoffs between the generality of an algorithmic learning device and the quality of the successful programs it converges to.
Two classes of results are presented.
There are results to the effect that, with small increases in generality of the learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal.
Importantly, there are also results in which the complexity of successfully learned programs is optimal and the learning device is quite general, but some of those optimal, learned programs are provably unalterably information deficient - in fact, deficient as to safe, algorithmic extractability of even the fact that they are approximately optimal. For these results, the safe, algorithmic methods of information extraction will be by proofs in arbitrary, true, recursively axiomatizable extensions of Peano Arithmetic.
This is joint work with Keh-Jian Chen, James Royer, and Sanjay Jain.