  As inductive inference and machine learning methods in computer science see
continued success, researchers are aiming to describe ever more complex
probabilistic models and inference algorithms. It is natural to ask whether
there is a universal computational procedure for probabilistic inference. We
investigate the computability of conditional probability, a fundamental notion
in probability theory and a cornerstone of Bayesian statistics. We show that
there are computable joint distributions with noncomputable conditional
distributions, ruling out the prospect of general inference algorithms, even
inefficient ones. Specifically, we construct a pair of computable random
variables in the unit interval such that the conditional distribution of the
first variable given the second encodes the halting problem. Nevertheless,
probabilistic inference is possible in many common modeling settings, and we
prove several results giving broadly applicable conditions under which
conditional distributions are computable. In particular, conditional
distributions become computable when measurements are corrupted by independent
computable noise with a sufficiently smooth bounded density.
