Skip to content

Gregory Chaitin

Abstract

Gregory Chaitin (born 1947) submitted a paper to the Journal of the ACM at eighteen defining the complexity of a string as the length of the shortest program that prints it, the same idea Andrey Kolmogorov had published a year earlier in Moscow and Ray Solomonoff two years before that; he had never heard of either. He spent the next fifty years pushing the idea to its limits. Chaitin’s constant Ω (1975), the probability that a random program halts, is a specific real number every one of whose digits is well defined and almost none of which can ever be known. His incompleteness theorem showed that a formal system cannot prove any string to be more complex than the system itself, which turned Gödel’s result from a construction into a fact about information. He also, as a day job at IBM, invented the way compilers allocate registers.

Gregory Chaitin
Gregory Chaitin. Image: LeibnizOmega, CC BY-SA 4.0, via Wikimedia Commons.

The Bronx

Gregory John Chaitin was born in Chicago on June 25, 1947, to Argentine parents, and grew up in New York, where he went to the Bronx High School of Science and, from 1962, the City College of New York. As a teenager he read Gödel, Turing and Shannon and asked a question the three of them had not put together: Shannon had measured information in a source, Turing had defined what a program was, so what was the information in a single string? His answer, the length of the shortest program that outputs it, was written up in 1965 and published in October 1966, when he was nineteen, as “On the Length of Programs for Computing Finite Binary Sequences”. Kolmogorov’s 1965 paper reached the West around the same time, and Solomonoff’s 1964 paper had been ignored; the three had found the measure independently. The literature calls it Kolmogorov complexity, occasionally Kolmogorov–Chaitin complexity; Chaitin’s name for the field, algorithmic information theory, is the one that stuck. The measure itself is explained in Kolmogorov Complexity and its Moscow discoverer in Andrey Kolmogorov.

Buenos Aires and Yorktown

In 1966 the family returned to Argentina, and Chaitin worked for IBM in Buenos Aires until 1975, doing the theory at night. The results of that period are the ones that made the field. In 1971 he proved that a formal axiomatic system whose axioms have complexity n cannot prove that any specific string has complexity much greater than n: there are true statements of the form “this string is random” that the system cannot reach, and they are most of the true statements. Gödel had shown incompleteness with one carefully built sentence; Chaitin’s theorem said incompleteness was the normal condition, and measured it. After a visit in 1974 he moved to IBM’s Thomas J. Watson Research Center in Yorktown Heights in 1975 and stayed for the rest of his career.

The 1975 paper “A Theory of Program Size Formally Identical to Information Theory” fixed a technical flaw in the original definition by requiring programs to be self-delimiting, so that no valid program is a prefix of another, and with that fixed the theory behaved exactly like Shannon’s. It also defined Ω: for a given universal machine, the probability that a program chosen by flipping coins will halt. Ω is a definite real number between zero and one. Its digits are the answers to every halting question, compressed: knowing the first n bits of Ω would settle the halting problem for every program up to n bits long, including the programs that search for counterexamples to Goldbach’s conjecture or the Riemann hypothesis. And Ω is algorithmically random, so no formal system can determine more than finitely many of its bits. Chaitin has called it the clearest possible statement of the limits of reason, and has written about it for general readers in The Limits of Mathematics (1998) and Meta Math! (2005); his textbook Algorithmic Information Theory appeared in 1987.

Register Allocation

At Yorktown he also did the work most programmers use without knowing it. John Cocke’s 801 project was building the first RISC processor, whose compiler had to decide which of a program’s variables lived in the machine’s few registers at any moment and which were spilled to memory (see John Cocke and the IBM 801). In 1981 Chaitin and colleagues showed the problem was graph colouring: draw a node for every variable, an edge between two that are live at the same time, and colour the graph with as many colours as there are registers; where the colouring fails, spill. Chaitin’s algorithm, published in full in 1982, is the basis of register allocation in most optimising compilers since.

Metabiology

He retired from IBM in the 2010s, moved to Rio de Janeiro, where his wife Virginia Chaitin is a philosopher and he became a professor at the Federal University, and turned to biology. Proving Darwin (2012) proposed “metabiology”: treat an organism as a program, a mutation as a change to the program, fitness as what the program computes, and ask whether evolution by random mutation and selection can be proved to work; in the toy model, with Ω-flavoured oracles, it can. Biologists have been polite about it and philosophers of mathematics have argued for years about his larger claims, that mathematics is empirical and that Ω shows it must be done quasi-experimentally; Panu Raatikainen and others reply that the incompleteness results are less novel and less far-reaching than Chaitin’s prose makes them. The theorems are not disputed. He holds honorary doctorates from the University of Maine (1995) and the National University of Córdoba (2009) and an honorary professorship at Buenos Aires, and in 2007 received a Leibniz Medal from Wolfram Research; Leibniz, who wanted a calculus of reason and understood binary numbers, is the thinker he cites most.

See also: The Busy Beaver Problem.

📚 Sources