Skip to content Skip to navigation

Beyond Almost-Sure Termination

Thomas Icard
Proceedings of CogSci

Abstract: 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 nonterminating 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 almostsurely 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.