Correspondence between Computability & Learnability Theory Could someone give a brief explanation of the computability &amp; learnability theory &amp; the correspondence betwwen them if any? (pointers to good sources of info. on this other than wikipedia are welcome) Thank You.
Let's stick to the classical PAC (supervised learning) setting.
The short answer is that if computability is not an issue, then any class of functions with finite VC-dimension is PAC learnable via the Empirical Risk Minimization algorithm (just pick the hypothesis with the minimal sample error).

Of course, in many cases of interest ERM is computationally hard (e.g., if your class of functions is 3-term DNFs; see book by Kearns and Vazirani.

As Suresh commented above, the question is too vague and open-ended to give a comprehensive answer, but hopefully the above is a start...