Could someone give a brief explanation of the computability & learnability theory & the correspondence betwwen them if any? (pointers to good sources of info. on this other than wikipedia are welcome) Thank You.

  • 2
    $\begingroup$ this is a rather open ended question. Not sure if it's appropriate. $\endgroup$ Apr 8, 2011 at 21:52
  • $\begingroup$ actually, I couldn't understand the paper by Leslie Valiant "A Theory Of The Learnable' which tries to establish a theory of learnability of class of concepts (Boolean Expressions/functions) just as there exists a theory of computability of functions. So, with reference to this paper, could you guide me? $\endgroup$
    – amitlan
    Apr 9, 2011 at 5:45
  • 1
    $\begingroup$ you need to formulate more specific questions along these lines. your current question is far too open ended. Ask a specific question about Valiant's paper, and then we can see. $\endgroup$ Apr 10, 2011 at 2:06

1 Answer 1


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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.