Metric structures and probabilistic computation

Continuous first-order logic is used to apply model-theoretic analysis to analytic structures (e.g. Hilbert spaces, Banach spaces, probability spaces, etc.). Classical computable model theory is used to examine the algorithmic structure of mathematical objects that can be described in classical first-order logic. The present paper shows that probabilistic computation (sometimes called randomized computation) and continuous logic stand in a similar close relationship.The main result of this paper is an effective completeness theorem, showing that every decidable continuous first-order theory has a probabilistically decidable model. We also show that probabilistically computable structures give rise to a model of in a natural way, and describe a connection with complexity theory.