Computability and Probability

University Of Hawaii, Honolulu

Investigators

Abstract

The primary part of this project is an investigation of applications of probability to computability theory and algorithmic randomness. The principal investigator has shown that a limited amount of errors in the operation of a random number generator can lead to a loss of randomness that cannot be compensated for using algorithms. A main goal is to determine if at any point true randomness can be reconstructed as the amount of such errors becomes small. The results already obtained were proved using probabilistic potential theory and random closed sets. This approach in conjunction with work by other researchers has lead to a richer picture of the possible notions of randomness for fractional effective Hausdorff dimension, and opened up questions about a link with a statistical-mechanical interpretation of algorithmic information theory. A secondary but also integral part of the project is the computability-theoretic analysis of probability. An example here is the determination of the Kolmogorov complexity of finite strings describing random walks that approximate Brownian motion. The project aims to further the understanding of random objects in computability-theoretic terms, and help clarify the theoretical limitations of random number generation, a field of wide application in science and engineering. In particular, the aim is to understand to what extent one can repair damaged randomness sources, or prove that such a repair is impossible. The goal is not necessarily to reconstruct the original undamaged random data but to obtain some random data. The notion of particular data being random can be made precise using the theory of Turing computability. The idea is that a sequence of 0s and 1s is random for all practical purposes if no computer algorithm can detect any pattern in it. Thanks to the work of Alan Turing and others, this idea can be studied abstractly without worrying about particular physical computers and implementations. Conversely, the theoretical study of algorithms played a large role in the development of modern computers. Turing computability has been used in many areas of mathematics to show that certain tasks cannot be carried out by any algorithm. For example, Matiyasevich showed this for the task of finding an integer root of a polynomial equation. Applying this computability theory to probability and randomness is especially fruitful. The theory of probability predicts what properties the outcome of an experiment will have, without necessarily giving any specific example of a reasonable ?random? outcome. For instance, the experiment of throwing a dart at a dart board can result in any region of the board being hit, but will never result in a perfect bulls-eye or any other predefined point on the board. In theory there will always be a small error, perhaps invisible to the naked eye; this can be expressed by saying that the result of the experiment is an algorithmically random point on the dart board. One can also study how algorithmically random a sequence of observations must be for the scientific method to yield information about the phenomenon underlying the observations via the methods of statistics. The mathematical delineation of the intuitive notion of an individual random object as one having no computable or definable unlikely properties may contribute to a better appreciation of probability and randomness by scientists as well as the general public.