Gregory Chaitin is a mathematician and computer scientist who is best known for his contributions to Algorithmic Information Theory (AIT).

Although Chaitin is often cited as its creator, algorithmic information theory was founded by Ray Solomonoff as part of his researches on artificial intelligence, especially machine learning. Solomonoff's work was inspired by Claude Shannon's mathematical theory of the communication of information, particularly by Shannon's study of the redundancy of letters in English language. A summer research project at Dartmouth organized by John McCarthy , Shannon, and Marvin Minsky is said to be the origin of artificial intelligence.

A typical fragment of English text is partly readable without its vowels. (Semitic languages generally do without any vowel.) When represented as a string of letters, redundancy can be estimated by studying the transition probabilities between letters in English. For example, the probability that "q" is followed by a "u" is nearly unity. .

Chaitin's work can be summarized as saying that the information contained in an arbitrary length string of bits (or digits, or letters) is equal to the shortest possible computer program that can output the string on a universal computing (Turing) machine.

An essential corollary is that if the string is completely random, the information is equal to the length of the string. It cannot be reduced.

The information content of a complex object is extremely difficult to instantiate in another form, a "representation" of the object.

The information content of the observable universe is best represented by the universe itself. It cannot be instantiated anywhere inside the universe.

The shortest program that can represent the information in a string, or in an object, is also known as the Kolmogorov complexity. It is sometimes called algorithmic entropy, which only adds to the confusion between information and entropy. When Andrey Kolmogorov learned of Solomonoff's work, he recognized his priority. In 1968, Chaitin revised his 1966 theorem paper in the Journal of the Association for Computing Machinery to cite the prior work of both Solomonoff and Kolmogorov.

Solomonoff had described the "algorithmic probability" of a hypothesis (an algorithm or program) as the function of its length in bits. The shortest program has the highest inference or predictive value, he said.

Solomonoff's interest in probability made him an outsider in the development of cognitive psychology, most of whom were determinists looking for machine models of the mind.

Chaitin celebrated the appearance of randomness in number strings. A given number cannot be proved to be random, he said. This is an enigma that puts limits on what is possible in mathematics, similar in some ways to Kurt Gödel's incompleteness and inconsistency theorems, as well as modern issues of undecidability and computability (the halting problem).

Chaitin wrote in 1987

God not only plays dice in quantum mechanics, but even with the whole numbers!...I show that to decide if an algebraic equation in integers has finitely or infinitely many solutions is in some cases absolutely intractable. I exhibit an infinite series of such arithmetical assertions that are random arithmetical facts, and for which it is essentially the case that the only way to prove them is to assume them as axioms. This extreme form of Gödel incompleteness theorem shows that some arithmetical truths are totally impervious to reasoning.

Information, Randomness, and Incompleteness, Preface

Are the bits or digits of the irrational number π random? Their distribution is demonstrably random. But they can be generated by an algorithm that has been used to establish their sequence to many trillions of digits. The computer power (matter and energy) and time needed to generate π is vast. If π needs an infinite number of random digits, does it include an infinite amount of information?

We can compare the information in an approximation to π including 30 trillion digits (essentially 10 to the power 30 trillion) to the radius of the observable universe (≈8.8×10²⁶ m ) divided by the smallest known distance - the Planck length (1.6 x 10^-35 m). This cosmic dimension is a mere 1.4 x 10⁶²!

Chaitin is a member of a group of scientists and philosophers pursuing "digital philosophy," They include Gregory Chaitin, Edward Fredkin, Seth Lloyd, Rudy Rucker, Jürgen Schmidhuber, Stephen Wolfram, and Konrad Zuse.

They generally hope to reduce the mind to a computer and even see the whole universe as a computer running some kind of cosmic code.