Gregory Chaitin

Gregory Chaitin (born 1947) is an Argentine-American mathematician and computer scientist whose work was foundational to algorithmic information theory and influential on metamathematics. While still in his teens at the City College of New York he independently discovered algorithmic complexity, also called Kolmogorov or Solomonoff-Kolmogorov-Chaitin complexity, at the same time as Andrei Kolmogorov and Ray Solomonoff. In 1975 he defined Chaitin's constant, a real number that is definable but not computable and is informally described as the probability that a random program will halt. He also originated the use of graph coloring for register allocation in compilers. Formerly a researcher at IBM's Thomas J. Watson Research Center, he later turned to metabiology, and he writes on philosophy, defending digital philosophy and a quasi-empirical view of mathematical knowledge.