Proceedings of the Annual Meeting of the Cognitive Science Society

The aim of this paper is to argue that models in cognitivescience based on probabilistic computation should not be re-stricted to those procedures that almost surely (with probabil-ity 1) terminate. There are several reasons to consider non-terminating procedures as candidate components of cognitivemodels. One theoretical reason is that there is a perfect cor-respondence between the enumerable semi-measures and allprobabilistic programs, as we demonstrate here (generalizinga better-known fact about computable measures and almost-surely halting programs). One practical reason is that the linebetween almost sure termination and non-termination is elu-sive, as well as arbitrary. We argue that this matters not onlyfor theorists, but also potentially for a learner faced with thetask of inducing programs from experience.