Computational Complexity and Probability Constructions

Abstract

There exist constructive correspondences between Turing machines having finitely determinable behavior and computable probability measures on their output sequences. These correspondences determine limits on the relative accuracies with which different computable probability measures predict events. Using any universal Turing machine as a basis, it is possible to construct an infinite hierarchy of increasingly accurate computable probability measures which are independent of any probability assumptions. The relationship of such measures to real events is considered.