Computability and Mathematical Definability

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Slaman proposes to investigate the effective, and more generally definable, aspects of mathematical phenomena such as genericity, compactness, and randomness. One central question in this investigation is to give necessary and suffcient conditions on an infinite binary sequence X which ensure that there is a continuous measure m such that X is effectively or arithmetically random relative to m. This is a classic mathematical problem, given an individual data set determine a distribution which would generate it. By results of Reimann and Slaman, for all but countably many X there is such an m. The argument is highly meta-mathematical. Necessarily so, as Reimann and Slaman have also shown that this co-countability theorem cannot be proven without invoking infinitely many iterations of the power set of the reals. In the emerging picture, there is a close interaction between a sequence's failure to have a random ingredient and it's being structurally definable, which should be studied more deeply. Slaman's proposal can be viewed in the context of the continuing investigation of computability and mathematical definability. With quantitative mathematical analysis of these phenomena, one can answer questions of the form ``Is there an algorithm to solve all problems of a this type?'', ``Is there a simple example with specific properties'', ``Is there a concrete classification of all structures with these properties?''. One can also address questions of the sort ``Are these techniques adequate to resolve this question?'' or ``How random must a sequence be in order to exhibit a particular typical behavior?'' One must develop a detailed theory of computation to show that there is no algorithm of a certain type. Similarly, one must develop a detailed theory of definability to show that there is no simple example with certain properties or to show that certain phenomena do not have concrete classifications.