Computational learning theory (CoLT) is a branch of theoretical computer science associated with the mathematical analysis of machine learning. A lot of the early ideas of the field take inspiration from human learning. The field has developed into a very rigorous, mathematical, and precise science, but I have not seen it used much in the cognitive sciences directly. There is some indirect use through CoLT's interaction with statistics and machine learning algorithms (say, analyzing neural networks through VC-dimension).

Are there examples of rigorous uses/applications of CoLT to build theories in psychology, neuroscience, and/or cognitive science?


The only two examples I am familiar with are:

  1. Gold's theorem on the unlearnability in the limit of certain sets of languages, among them context-free ones.

  2. Ronald de Wolf's master's thesis on the impossibility to PAC-learn context-free languages.

The first made quiet a stir in the poverty-of-the-stimulus debate, and the second has been unnoticed by cognitive science.

I am interested in approaches of this flavor. I am relatively comfortable with CoLT as it is studied in mathematics, and am only interested (for this question) in approaches that have direct bearing on theories of human/animal cognition/learning, and not classic machine learning results. I am looking for general mathematical and asymptotic approaches, not the running of specific types of algorithms (be it neural-nets, bayesian, or otherwise) to simulate human performance as is typical in computational modeling in cogsci (which I am relatively familiar with).

I am not interested in arguments that try to trivially undercut the whole approach, even if they have empirical validity. For instance, the whole approach can be derailed by asserting that human brains are finite and thus asymptotic arguments are useless. This is the same as arguing that all of computational complexity theory is pointless because computers (and the whole universe, for that matter) are finite. It is a valid empirical argument, but boring from the point of view of theory building.

Related questions:


2 Answers 2


Related to this is several works on the integration or non-integration of computational models in general to cognitive science. For instance, the Tractable Cognition Thesis basically says that we can improve cognitive modeling if we limit cognitive models to those tractably implementable on a Turing machine.

Van Rooij, I. 2008. The Tractable Cognition Thesis. Cognitive Science 32:939-984. http://staff.science.uva.nl/~szymanik/papers/TractableCognition.pdf

Personally, I disagree with the Tractable Cognition Thesis, and think, similar to Copeland, that a better model would be of an Oracle machine:

Copeland, J. 1998. Turing's O-Machines, Searle, Penrose, and the Brain. Analysis 58(2):128-138.

My own work goes ahead in this regard, and proposes how O-machines can be specifically integrated into cognitive psychology. I give a presentation on it here and the proceedings will be published next year, but message me and I can provide a draft copy if you would like.


  • 1
    $\begingroup$ thanks, but this has very little to do with CoLT, and the first part of your answer is already taken care of by this answer in the links I provide in the question. $\endgroup$ Commented Oct 9, 2012 at 15:05

Recently Bayesian models of cognitive development have been very successful in at least formulating working hypotheses as to how abstract knowledge "regularizes" and guides learning and reasoning from sparse data. I was thinking for instance of the following paper:

  • $\begingroup$ Bayesian models are not traditionally part of CoLT. Can you expand your answer to explain why you think the above work is a rigorous use of CoLT for building a psychological theory? I can see how it is a hand-wavy approach, or a modeling framework, but I don't see rigor as required by the question. $\endgroup$ Commented Jun 28, 2012 at 17:46

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.