Gregory John Chaitin (born 1947) is an Argentine-American mathematician and computer scientist. Year 1947 (MCMXLVII) was a common year starting on Wednesday (link will display full 1947 calendar) of the Gregorian calendar. ... Leonhard Euler, considered one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is the field of mathematics. ... Computer science (informally: CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ...

Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a new incompleteness theorem similar in spirit to Gödel's incompleteness theorem. He attended the Bronx High School of Science and City College of New York, where he first developed his theorem while still in his teens. The 1960s decade refers to the years from January 1, 1960 to December 31, 1969, inclusive. ... This article or section is in need of attention from an expert on the subject. ... In general, metamathematics or meta-mathematics is reflection about mathematics seen as an entity/object in human consciousness and culture. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ... The Bronx High School of Science, commonly called Bronx Science, Bronx Sci, or just Science, is a specialized New York City public high school located in the Bedford Park section of the Bronx, with no tuition charges and admission by exam (reportedly taken by more than 20,000 students). ... The City College of The City University of New York (known more commonly as City College of New York or simply City College, CCNY, or colloquially as City) is a senior college of the City University of New York, in New York City. ...

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. In the computer science subfield of algorithmic information theory the Chaitin constant or halting probability is a construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or programming language will halt. ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... In mathematics, a normal number is, roughly speaking, a real number whose digits show a random distribution with all digits being equally likely. ... A real number a is first-order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ(a) holds (in the von Neumann universe V). ... In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ...

Chaitin's early work on algorithmic information theory paralleled the earlier work of Kolmogorov. Andrey Kolmogorov Andrey Nikolaevich Kolmogorov (Андре́й Никола́евич Колмого́ров) (kahl-mah-GAW-raff) (April 25, 1903 in Tambov - October 20, 1987 in Moscow) was a...

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). Indeed, in recent writings, he defends a position known as digital philosophy. In the epistemology of mathematics, he claims that his findings in mathematical logic and algorithmic information theory show there are “mathematical facts that are true for no reason, they're true by accident. They are random mathematical facts”. Chaitin proposes that mathematicians must abandon any hope of proving those mathematical facts and adopt a quasi-empirical methodology. The philosopher Socrates about to take poison hemlock as ordered by the court. ... Plato (Left) and Aristotle (right), by Raphael (Stanza della Segnatura, Rome) Metaphysics is the branch of philosophy concerned with explaining the ultimate nature of reality, being, and the world. ... // Philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. ... This article or section is in need of attention from an expert on the subject. ... Biology studies the variety of life (clockwise from top-left) E. coli, tree fern, gazelle, Goliath beetle Biology (from Greek: βίος, bio, life; and λόγος, logos, knowledge), also referred to as the biological sciences, is the study of living organisms utilizing the scientific method. ... This article is about evolution in biology. ... Drawing of the cells in the chicken cerebellum by S. Ramón y Cajal Neuroscience is a field that is devoted to the scientific study of the nervous system. ... Consciousness is a quality of the mind generally regarded to comprise qualities such as subjectivity, self-awareness, sentience, sapience, and the ability to perceive the relationship between oneself and ones environment. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... It has been suggested that Meta-epistemology be merged into this article or section. ... Mathematical logic is a major area of mathematics, which grew out of symbolic logic. ... Quasi-empiricism in mathematics is the movement in the philosophy of mathematics to reject as pointless the foundations problem in mathematics, and re-focus philosophers on mathematical practice itself, in particular relations with physics and social sciences. ...

Some philosophers and logicians strongly disagree with the philosophical conclusions that Chaitin has drawn from his theorems ^{[attribution needed]}. The logician Torkel Franzén ^{[citation needed]}criticizes Chaitin’s interpretation of Gödel's Incompleteness Theorem and the alleged explanation for it that Chaitin’s work represents. One criticism is that although Chaitin has frequently talked of the "unknowable" and the "limits of reason", he has not given one instance of a mathematical fact or question which is unknowable or beyond the limits of reason/mathematics. In fact, there is no limit, in principle, to the number and location of bits of omega one could work out. Torkel Franzén (born 1950, died April 19, 2006) was a Swedish academic working in the fields of mathematical logic and computer science. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ...

Chaitin is also the originator of using graph coloring to do register allocation in compiling, a process known as Chaitin's algorithm. Image:3-colouringEx. ... In compiler optimization, register allocation is the process of multiplexing a large number of target program variables onto a small number of CPU registers. ... Chaitins algorithm is a graph coloring algorithm designed specifically for register allocation. ...

In 1995 he was given the degree of doctor of science honoris causa by the University of Maine. In 2002 he was given the title of honorary professor by the University of Buenos Aires in Argentina, where his parents were born and where Chaitin spent part of his youth. He is a research staff member at IBM's Thomas J. Watson Research Center and also a visiting professor at the Computer Science Department of the University of Auckland, and on the international committee of the Valparaíso Complex Systems Institute. The University of Maine, established in 1865, is the flagship university of the University of Maine System. ... The Universidad de Buenos Aires (UBA) is the largest university in Argentina, founded on August 12, 1821 in the city of Buenos Aires. ... IBM redirects here. ... The Thomas J. Watson Research Center is the headquarters for the IBM Research Division. ... The University of Auckland (Māori: Te Whare Wānanga o Tāmaki Makaurau) is New Zealands largest research-based university. ...

[edit] Bibliography

• Algorithmic Information Theory, (Cambridge University Press, 1987),
• Information, Randomness & Incompleteness, (World Scientific, 1987),
• Information-Theoretic Incompleteness, (World Scientific, 1992),
• The Limits of Mathematics, (Springer-Verlag 1998),
• The Unknowable, (Springer-Verlag 1999),
• Exploring Randomness, (Springer-Verlag 2001),
• Conversations with a Mathematician, (Springer-Verlag 2002),
• From Philosophy to Program Size, (Tallinn Cybernetics Institute 2003),
• Meta Math!: The Quest for Omega, (Pantheon 2005).

Year 1987 (MCMLXXXVII) was a common year starting on Thursday (link displays 1987 Gregorian calendar). ... Year 1992 (MCMXCII) was a leap year starting on Wednesday (link will display full 1992 Gregorian calendar). ... Year 1998 (MCMXCVIII) was a common year starting on Thursday (link will display full 1998 Gregorian calendar). ... This article is about the year. ... Year 2001 (MMI) was a common year starting on Monday (link displays the 2001 Gregorian calendar). ... Also see: 2002 (number). ... Year 2003 (MMIII) was a common year starting on Wednesday of the Gregorian calendar. ... Year 2005 (MMV) was a common year starting on Saturday (link displays full calendar) of the Gregorian calendar. ...

[edit] External links

• G J Chaitin Home Page
• List of publications of G J Chaitin
• New Scientist article (March, 2001) on Chaitin, Omegas and Super-Omegas
• A short version of Chaitin's proof
• A review in Notices of the American Mathematical Society, criticizing two of Chaitin's books, The Unknowable and Exploring Randomness
• A paper (dead link)(1) criticizing Chaitin's interpretation of his results