This book is an essential companion to Chaitin's monograph ALGORITHMIC INFORMATION THEORY and includes in easily accessible form all the main ideas of the creator and principal archi-tect of algorithmic information theory. This expanded second edition has added thirteen abstracts, a 1988 SCIENTIFIC AMERICAN article, a transcript of a EUROPALIA 89 lecture, an essay on bi-ology, and an extensive bibliography. Its larger format makes it easier to read. Chaitin's ideas are a fundamental extension of those of Godel and Turing and have exploded some basic assumptions of mathematics and thrown new light on the scientific method, epistemology, probability theory, and of course computer science and information theory."One will find in [Information, Randomness & Incompleteness] all kinds of "articles which are popularizations or epistemological reflections, and presentations which permit one to rapidly obtain a precise idea of the subject and of some of its applications (in particular in the biological domain).

Very complete, it is recommended to anyone who is interested in algorithmic information theory." Jean-Paul Delahaye in LA RECHERCHE "No one, but no one, is exploring to greater depths the amazing insights and theorems that flow from Godel's work on undecidability than Gregory Chaitin. His exciting discoveries and speculations in-vade such areas as logic, induction, simplicity, the philosophy of mathematics and science, random-ness, proof theory, chaos, information theory, computer complexity, diophantine nalysis, and even the origin and evolution of life." Martin Gardner "Gregory Chaitin...has proved the ultimate in undecidability theorems that the logical structure of arithmetic can be random... The assumption that the formal structure of arithmeticis precise and regular turns out to have been a time-bomb, and Chaitin has just pushed the detonator." Ian Stewart in NATURE

Gregory John Chaitin： (born 1947) is an Argentine-American mathematician and computer scientist.

Beginning in 2009 Chaitin has worked on metabiology, a field parallel to biology dealing with the evolution of artificial software (computer programs) instead of natural software (DNA).

Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a new incompleteness theorem in reaction to Gödel's incompleteness theorem. He attended the Bronx High School of Science and City College of New York, where he (still in his teens) developed the theories 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.

Chaitin's early work on algorithmic information theory paralleled the earlier work of Kolmogorov.

Chaitin is also the originator of using graph coloring to do register allocation in compiling, a process known as Chaitin's algorithm.