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 ACA(0) in a natural way, and describe a connection with complexity theory. (C) 2011 Elsevier B.V. All rights reserved.
metric structures probabilistic computation computable model theory randomized computation continuous logic