Inductive Coherence
  While probability theory is normally applied to external environments, there
has been some recent interest in probabilistic modeling of the outputs of
computations that are too expensive to run. Since mathematical logic is a
powerful tool for reasoning about computer programs, we consider this problem
from the perspective of integrating probability and logic. Recent work on
assigning probabilities to mathematical statements has used the concept of
coherent distributions, which satisfy logical constraints such as the
probability of a sentence and its negation summing to one. Although there are
algorithms which converge to a coherent probability distribution in the limit,
this yields only weak guarantees about finite approximations of these
distributions. In our setting, this is a significant limitation: Coherent
distributions assign probability one to all statements provable in a specific
logical theory, such as Peano Arithmetic, which can prove what the output of
any terminating computation is; thus, a coherent distribution must assign
probability one to the output of any terminating computation. To model
uncertainty about computations, we propose to work with approximations to
coherent distributions. We introduce inductive coherence, a strengthening of
coherence that provides appropriate constraints on finite approximations, and
propose an algorithm which satisfies this criterion.
