Chapter Random sequences, incompleteness and information

Overview & Synopsis

Another mathematically significant development in the research around the phenomenon of incompleteness on which we consider it important to focus attention, is that which has led to highlighting the link between this concept and that of randomness and information. Grigory Chaitin, starting in the 1970s, reformulated the incompleteness theorems within the framework of algorithmic theory of information, presenting his results as a “dramatic extension” of the phenomenon already highlighted by Gödel. He claims that high complexity is the alleged reason of the unprovability of infinitely many true sentences: a true statement that can be expressed in the language of a theory is unprovable because its information content is greater than that of the axioms of that theory itself; or in other words, in a formal system no number can be proved random unless its complexity is less than that of the formal system itself. At the heart of Chaitin’s work, therefore, is the concept of the complexity of an object and the measure of the difficulty of describing it. The mathematical concept of randomness is an attempt to give an idealized model of randomness, as the recursive functions do in the case of computability.