Correspondence between Computability & Learnability Theory
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...