Gregory Chaitin

related topics
{theory, work, human}
{math, number, function}
{work, book, publish}
{woman, child, man}

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


Mathematics and computer science

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.[1][2]

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.

Other scholarly contributions

Chaitin also writes about philosophy, especially metaphysics and philosophy of mathematics (particularly about epistemological matters in mathematics). 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).

Full article ▸

related documents
Vladimir Arnold
Thomas Bayes
René Thom
Potential infinity
Conceptual schema
Term logic/Danielsavoiu's summary
Larry Wall
James R. Flynn
The Third Culture
George Pólya
The Age of Spiritual Machines
Lincos (language)
Karl Weierstrass
Werner Erhard and Associates
Erhard Seminars Training
Michael Halliday
Software Engineering Body of Knowledge
Jacob Anatoli
Stuart Kauffman
Haskell Curry
William Schutz
World History
Bahya ibn Paquda
The Machinery of Freedom
Extension (metaphysics)