Gregory Chaitin

from Wikipedia, the free encyclopedia

Gregory J. Chaitin (* 1947 in Chicago ) is an American mathematician and philosopher . His main area of ​​work is computability theory . He is thus in the tradition of Kurt Gödel and Alan Turing , whose theorems ( incompleteness theorem , Turing computability ) he generalized into algorithmic information theory , which is similar to Kolmogorov's complexity .


Chaitin was born to Argentine immigrants from Buenos Aires . However, the family moved to New York at an early age , where he was drawn to the theory of computability at an early age by the book Gödel's Proof by Ernest Nagel and James R. Newman about Gödel's incompleteness theorem . (Chaitin approaches this, however, from Shannon's information theory .) He attended the Bronx High School of Science from 1962 and the City University of New York (CUNY) from 1965 . In 1966 he went back to Buenos Aires with the family, where he started as a programmer at IBM and held courses in LISP programming and metamathematics at the University of Buenos Aires. At the beginning of the 1970s his work Information theoretic limits of formal systems (published expanded in the ACM Journal 1974) was created, which earned him an invitation to the Thomas J. Watson Research Center at IBM, where he is still active today. From 1976 to 1985 he worked there as a software and hardware engineer on IBM's RISC project. He is also currently visiting professor in the Computer Science Department at the University of Auckland in New Zealand.


His results concern the structure of mathematical theories. Chaitin is looking for statements on the fundamental predictability and the fundamental decidability of mathematical propositions.

He dealt with examples of principally undecidable sentences. With such sentences it is completely "random" whether they are true or false. However, the English term random can also mean random or random ; What is meant here is that these sentences cannot be "justified", but rather "that it is so".

According to Chaitin, he has proven that, with a finite number of exceptions, it is undecidable whether a number is Kolmogorow-reducible , i.e. H. whether there is a smaller program that produces this number. So there is no general method by which Kolmogorov complexity can be measured.

The interpretation of Chaitin's results is controversial among some mathematicians. Chaitin's constant comes from him .

Chaitin has also written a lot on the philosophy of mathematics, especially in relation to Gödel's incompleteness theorems and questions of complexity.

He received an honorary doctorate from the University of Maine in 1995 and an honorary professorship in Buenos Aires in 2002 .


  • Algorithmic information theory , Cambridge University Press 1987
  • The Limits of Mathematics , Springer-Verlag, 1998.
  • The Unknowable , Springer-Verlag, 1999.
  • Exploring Randomness , Springer-Verlag, 2001.
  • Conversations with a Mathematician , Springer-Verlag, 2002.
  • Meta Math! , Pantheon Books 2005
  • Thinking about Gödel and Turing - Essays on Complexity 1970-2007 , Singapore 2007.
  • Randomness and mathematical proof , Scientific American 1975
  • Randomness in Arithmetic , Scientific American 1988


Web links