Abstract

A formal introduction to Kolmogorov complexity is given, along with its fundamental theorems. Most importantly the theorem of undecidability of a random string and the information-theoretic reformulation of Gödel’s first theorem of incompleteness, stated by Chaitin. Then, the discussion moves on to inquire about some philosophical implications the concept randomness has in the fields of physics and mathematics. Starting from the notion of “understanding as compression” of information, as it is illuminated by algorithmic information theory, it is investigated (1) what K-randomness has to say about the concept of natural law, (2) what is the role of incompleteness in physics and (3) how K-randomness is related to unpredictability, chance and determinism. Regarding mathematics, the discourse starts with a general exposition of the relationship between proving and programming, to propose then some ideas on the nature of mathematics itself; namely, that it is not as unworldly as it is often regarded: indeed, it should be considered a quasi-empirical science (the terminology is from Lakatos, the metamathematical argument by Chaitin) and, more interestingly, random at its core. Finally, a further proposal about the relationship between physics and mathematics is made: the boundary between the two disciplines is blurred; no conceptual separation is possible. Mathematics can be seen as a computational activity (i.e. a physical process), the structure of such a type of process is analyzed.