Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Gregory Chaitin
Summary
Gregory John Chaitin (ˈtʃaɪtɪn ; born 25 June 1947) is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem. He is considered to be one of the founders of what is today known as algorithmic (Solomonoff–Kolmogorov–Chaitin, Kolmogorov or program-size) complexity together with Andrei Kolmogorov and Ray Solomonoff. Along with the works of e.g. Solomonoff, Kolmogorov, Martin-Löf, and Leonid Levin, algorithmic information theory became a foundational part of theoretical computer science, information theory, and mathematical logic. It is a common subject in several computer science curricula. Besides computer scientists, Chaitin's work draws attention of many philosophers and mathematicians to fundamental problems in mathematical creativity and digital philosophy.
Gregory Chaitin is Jewish and he attended the Bronx High School of Science and City College of New York, where he (still in his teens) developed the theory that led to his independent discovery of algorithmic 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, 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. He has written more than 10 books that have been translated to about 15 languages. He is today interested in questions of metabiology and information-theoretic formalizations of the theory of evolution, and is a member of the Institute for Advanced Studies at Mohammed VI Polytechnic University.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.