Chaitin, beginning in the late 1960s, made important contributions to algorithmic information theory, in particular a new incompleteness theorem similar in spirit to Gödel's incompleteness theorem. In 1995 he was given the degree of doctor of science honoris causa by the University of Maine. In 2002 he was given the title of honorary professor by the University of Buenos Aires in Argentina, where his parents were born and where Chaitin spent part of his youth. He is also a visiting professor at the Computer Science Department of the University of Auckland.
Chaitin has defined Chaitin's constantΩ, a real number whose digits are normally 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 earlier work of Kolmogorov in many respects.
Books
Algorithmic Information Theory, (Cambridge University Press (http://www.cup.org), 1987),
In metaphysics, Chaitin claims that algorithmic information theory is the key to solving problems in the field of biology (obtaining a formal definition of ‘life’, its origin and evolution) and neuroscience (the problem of consciousness and the study of the mind).
Chaitin is also the originator of using graph coloring to do register allocation in compiling.
In the computer science subfield of algorithmic information theory a Chaitin constant or halting probability is a construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or programming language will halt.
Chaitin's constant is uncompressible (others may say irreducible, or algorithmically random).
Omega and why math has no TOEs article based on one written by Gregory Chaitin which appeared in the August 2004 edition of Mathematics Today, on the occasion of the 50th anniversary of Alan Turing's death.
Feeds |
Contact