Beyond Almost-Sure Termination


The aim of this paper is to argue that models in cognitive science based on probabilistic computation should not be restricted to those procedures that almost surely (with probability 1) terminate. There are several reasons to consider non-terminating procedures as candidate components of cognitive models. One theoretical reason is that there is a perfect correspondence between the enumerable semi-measures and all probabilistic programs, as we demonstrate here (generalizing a better-known fact about computable measures and almost-surely halting programs). One practical reason is that the line between almost sure termination and non-termination is elusive, as well as arbitrary. We argue that this matters not only for theorists, but also potentially for a learner faced with the task of inducing programs from experience.

Back to Table of Contents