Gregory Chaitin
Encyclopedia
Gregory John Chaitin 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 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
.
, 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.
. 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. In 2007 he was given a Leibniz Medal by Wolfram Research. In 2009 he was given the degree of doctor of philosophy honoris causa by the National University of Córdoba
. He was formerly a researcher at IBM
's Thomas J. Watson Research Center
and is now a professor at the Federal University of Rio de Janeiro.
The logician Torkel Franzén
criticizes Chaitin’s interpretation of Gödel's incompleteness theorem and the alleged explanation for it that Chaitin’s work represents.
Argentina
Argentina , officially the Argentine Republic , is the second largest country in South America by land area, after Brazil. It is constituted as a federation of 23 provinces and an autonomous city, Buenos Aires...
-American
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
.
Mathematics and computer science
Beginning in 2009 Chaitin has worked on metabiology, a field parallel to biology dealing with the random evolution of artificial software (computer programs) instead of natural software (DNA).Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory
Algorithmic information theory
Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information...
and metamathematics
Metamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
, in particular a new incompleteness theorem in reaction to Gödel's incompleteness theorem. He attended the Bronx High School of Science
Bronx High School of Science
The Bronx High School of Science is a specialized New York City public high school often considered the premier science magnet school in the United States. Founded in 1938, it is now located in the Bedford Park section of the Bronx...
and City College of New York
City College of New York
The City College of the City University of New York is a senior college of the City University of New York , in New York City. It is also the oldest of the City University's twenty-three institutions of higher learning...
, where he (still in his teens) developed the theories that led to his independent discovery of Kolmogorov complexity
Kolmogorov complexity
In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
.
Chaitin has defined Chaitin's constant
Chaitin's constant
In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that informally represents the probability that a randomly constructed program will halt...
Ω, a real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
whose digits are equidistributed
Normal number
In mathematics, a normal number is a real number whose infinite sequence of digits in every base b is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b2 pairs of digits are equally likely with density b−2,...
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
Definable number
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 φ holds in the standard model of set theory .For the purposes of this article,...
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
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
to do register allocation
Register allocation
In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers...
in compiling, a process known as Chaitin's algorithm
Chaitin's algorithm
Chaitin's algorithm is a bottom-up, graph coloring register allocation algorithm that uses cost/degree as its spill metric. It is named after its designer, Gregory Chaitin...
.
Other scholarly contributions
Chaitin also writes about philosophyPhilosophy
Philosophy is the study of general and fundamental problems, such as those connected with existence, knowledge, values, reason, mind, and language. Philosophy is distinguished from other ways of addressing such problems by its critical, generally systematic approach and its reliance on rational...
, especially metaphysics
Metaphysics
Metaphysics is a branch of philosophy concerned with explaining the fundamental nature of being and the world, although the term is not easily defined. Traditionally, metaphysics attempts to answer two basic questions in the broadest possible terms:...
and philosophy of mathematics
Philosophy of mathematics
The philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. The aim of the philosophy of mathematics is to provide an account of the nature and methodology of mathematics and to understand the place of...
(particularly about epistemological matters in mathematics). In metaphysics, Chaitin claims that algorithmic information theory
Algorithmic information theory
Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information...
is the key to solving problems in the field of biology
Biology
Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...
(obtaining a formal definition of ‘life’, its origin and evolution
Evolution
Evolution is any change across successive generations in the heritable characteristics of biological populations. Evolutionary processes give rise to diversity at every level of biological organisation, including species, individual organisms and molecules such as DNA and proteins.Life on Earth...
) and neuroscience
Neuroscience
Neuroscience is the scientific study of the nervous system. Traditionally, neuroscience has been seen as a branch of biology. However, it is currently an interdisciplinary science that collaborates with other fields such as chemistry, computer science, engineering, linguistics, mathematics,...
(the problem of consciousness
Consciousness
Consciousness is a term that refers to the relationship between the mind and the world with which it interacts. It has been defined as: subjectivity, awareness, the ability to experience or to feel, wakefulness, having a sense of selfhood, and the executive control system of the mind...
and the study of the mind).
Indeed, in recent writings, he defends a position known as digital philosophy
Digital philosophy
Digital philosophy is a direction in philosophy and cosmology advocated by certain mathematicians and theoretical physicists, e.g., Gregory Chaitin, Edward Fredkin, Stephen Wolfram, and Konrad Zuse ....
. In the epistemology of mathematics, he claims that his findings in mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
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.
Honors
In 1995 he was given the degree of doctor of science honoris causa by the University of MaineUniversity of Maine
The University of Maine is a public research university located in Orono, Maine, United States. The university was established in 1865 as a land grant college and is referred to as the flagship university of the University of Maine System...
. In 2002 he was given the title of honorary professor by the University of Buenos Aires
University of Buenos Aires
The University of Buenos Aires is the largest university in Argentina and the largest university by enrollment in Latin America. Founded on August 12, 1821 in the city of Buenos Aires, it consists of 13 faculties, 6 hospitals, 10 museums and is linked to 4 high schools: Colegio Nacional de Buenos...
in Argentina, where his parents were born and where Chaitin spent part of his youth. In 2007 he was given a Leibniz Medal by Wolfram Research. In 2009 he was given the degree of doctor of philosophy honoris causa by the National University of Córdoba
National University of Córdoba
The National University of Córdoba, , is the oldest university in Argentina, and one of the oldest in the Americas. It is located in Córdoba, the capital of Córdoba Province. Since the early 20th century it has been the second largest university in the country in terms of the number of students,...
. He was formerly a researcher at IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
's Thomas J. Watson Research Center
Thomas J. Watson Research Center
The Thomas J. Watson Research Center is the headquarters for the IBM Research Division.The center is on three sites, with the main laboratory in Yorktown Heights, New York, 38 miles north of New York City, a building in Hawthorne, New York, and offices in Cambridge, Massachusetts.- Overview :The...
and is now a professor at the Federal University of Rio de Janeiro.
Criticism
Some philosophers and logicians strongly disagree with the philosophical conclusions that Chaitin has drawn from his theorems.The logician Torkel Franzén
Torkel Franzén
Torkel Franzén was a Swedish academic. He worked at the Department of Computer Science and Electrical Engineering at Luleå University of Technology, Sweden, in the fields of mathematical logic and computer science. He was known for his work on Gödel's incompleteness theorems and for his...
criticizes Chaitin’s interpretation of Gödel's incompleteness theorem and the alleged explanation for it that Chaitin’s work represents.