Gregory Chaitin

Gregory Chaitin, American contemporary mathematician and computer scientist who, beginning in the late 1960s, has made important contributions to algorithmic information theory, in particular a new incompleteness theorem similar in spirit to Gödel's incompleteness theorem.

Chaitin's work has profound consequences for our ideas of randomness.

Chaitin has defined Chaitin's constant Ω, a real number whose digits are randomly distributed and which expresses the probability that a random program will halt. Ω has numerous remarkable mathematical properties, including the fact that it is definable but not computable.

Chaitin's work on algorithmic information theory paralleled the work of Kolmogorov in many respects.

Books

• Algorithmic Information Theory, (Cambridge University Press (http://www.cup.org), 1987),
• Information, Randomness & Incompleteness, (World Scientific (http://www.worldscientific.com), 1987),
• Information-Theoretic Incompleteness, (World Scientific (http://www.worldscientific.com), 1992),
• The Limits of Mathematics, (Springer-Verlag (http://www.springer.de) 1998),
• The Unknowable, (Springer-Verlag (http://www.springer.de) 1999),
• Exploring Randomness, (Springer-Verlag (http://www.springer.de) 2001),
• Conversations with a Mathematician: math, art, science and the limits of reason, (Springer-Verlag (http://www.springer.de) 2002),
• From Philosophy to Program Size, (Tallinn Cybernetics Institute (http://www.cs.ioc.ee/ioc) 2003).

External links

• For other work see:
  • http://www.cs.umaine.edu/~chaitin/#PL
• See also his website:
  • http://www.cs.auckland.ac.nz/CDMTCS/chaitin/