We propose to conduct a mathematical and philosophical investigation into the interplay of the notions of structure, randomness, and mutual information in mathematics, as informed by the theory of computation. While the standard definitions of these notions are purely mathematical, they have significant philosophical implications for such topics as the nature of computation and the incompleteness phenomenon. In our study, we plan to investigate a principle formulated by Levin, the so-called "Independence Postulate" (IP), which states that given two infinite objects X and Y, where X is physically obtainable and Y is mathematically definable, the mutual information between X and Y is negligible (i.e. finite). Using the IP, Levin derives a general version of Gödel's theorem: no physical procedure can produce a consistent completion of Peano arithmetic.
Levin's work raises many challenging questions. First, there are questions about the meaning of the IP: Which objects should be counted as physically obtainable? Which are mathematically definable? Which definition of mutual information is operative in the IP? Second, there are questions of the status of the IP: What attitude should one take towards the IP? Should it be accepted outright? Should one provisionally accept it as a general stance that is taken in mathematical practice? Or should it be wholly rejected? Third, there are questions about the applications of the IP: What are the consequences of the IP in the theory of computation and in metamathematics? Does Levin's result still hold without the IP, or assuming weaker version of the IP? How does the IP help us better understand structured mathematical objects such as consistent completions of arithmetic?
The project aims to make progress on these questions (and related ones) and to bring awareness of their importance to the mathematical and philosophical communities by multiple journal publications and the organization of two specialized conferences.
