Gregory Chaitin is
Jewish. He attended the
Bronx High School of Science and the
City College of New York, where he (still in his teens) developed the theory that led to his independent discovery of
algorithmic complexity. In 1975, Chaitin 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, with asymptotic approximations from below (but not from above), but not
computable. Chaitin is also the originator of using
graph coloring to do
register allocation in
compiling, a process known as
Chaitin's algorithm. He was formerly a researcher at IBM's Thomas J. Watson Research Center in New York, where he wrote more than 10 books that have been translated into about 15 languages. Afterwards Chaitin became interested in questions of
metabiology and
information-theoretic formalizations of the theory of
evolution, and he was one of the founding members of the Institute for Advanced Studies at
Mohammed VI Polytechnic University in Morocco. ==Other scholarly contributions==