Gregory Chaitin | |
---|---|
Born |
Chicago |
November 15, 1947
Residence | United States |
Nationality | American |
Fields |
Biology Mathematics Computer science |
Institutions |
Federal University of Rio de Janeiro IBM Thomas J. Watson Research Center |
Known for |
Chaitin-Kolmogorov complexity Chaitin's constant Chaitin's algorithm |
Influences | Gottfried Wilhelm Leibniz |
Gregory John Chaitin (/ˈtʃaɪtᵻn/ CHY-tən; born 15 November 1947) is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem. He is considered to be one of the founders of what is today known as Kolmogorov (or Kolmogorov-Chaitin) complexity together with Andrei Kolmogorov and Ray Solomonoff. Today, algorithmic information theory is a common subject in any computer science curriculum.
He attended the Bronx High School of Science and City College of New York, where he (still in his teens) developed the theory that led to his independent discovery of Kolmogorov complexity.
Chaitin has defined Chaitin's constant Ω, a real number whose digits are equidistributed and which is sometimes informally described as an expression of the probability that a random program will halt. Ω has the mathematical property that it is definable but not computable.