A Computational Perspective on Reasoning about Probability Spaces

The aim of this talk is to give a survey of the computational aspects of quantified probability logics. More precisely, we shall be concerned with what might be called the elementary theories of natural classes of probability spaces, and for each such theory its complexity will be measured by its degrees of algorithmic undecidability. For example:

• the theory of atomless spaces turns out to be decidable;
• the theory of finite spaces is computably isomorphic to the complement of the halting problem for Turing machines;
• the theory of discrete spaces — as well as the theory of infinite spaces — is computably isomorphic to complete second-order arithmetic, which can be identified with elementary analysis.

We shall discuss these and other results, and also take a brief look at the underlying mathematical machinery.