Encyclopedia > Gregory Chaitin

  Article Content

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.


External links

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... elm, wild cherry[?] (Prunus padus), Taxus baccata and several willows are mixed with the conifers; while farther south the maple, mountain ash and oak, as also the ...

This page was created in 35.6 ms