Gregory John Chaitin ( ; born 25 June 1947) is an

Argentine Argentines (mistakenly translated Argentineans in the past; in Spanish (masculine) or (feminine)) are people identified with the country of Argentina. This connection may be residential, legal, historical or cultural. For most Argentines, s ...

American American(s) may refer to: * American, something of, from, or related to the United States of America, commonly known as the "United States" or "America" ** Americans, citizens and nationals of the United States of America ** American ancestry, pe ...

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

. Beginning in the late 1960s, Chaitin made contributions to

algorithmic information theory Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as st ...

and

metamathematics Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories. Emphasis on metamathematics (and perhaps the creation of the ter ...

, 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 Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generall ...

together with

Andrei Kolmogorov Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...

and

Ray Solomonoff Ray Solomonoff (July 25, 1926 – December 7, 2009) was the inventor of algorithmic probability, his General Theory of Inductive Inference (also known as Universal Inductive Inference),Samuel Rathmanner and Marcus Hutter. A philosophical treatise o ...

. Along with the works of e.g.

Solomonoff Ray Solomonoff (July 25, 1926 – December 7, 2009) was the inventor of algorithmic probability, his General Theory of Inductive Inference (also known as Universal Inductive Inference),Samuel Rathmanner and Marcus Hutter. A philosophical treatise ...

Kolmogorov Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...

, Martin-Löf, and

Leonid Levin Leonid Anatolievich Levin ( ; russian: Леони́д Анато́льевич Ле́вин; uk, Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American mathematician and computer scientist. He is kn ...

became a foundational part of

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

information theory Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...

, and

mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...

. 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.

Mathematics and computer science

He attended the

Bronx High School of Science The Bronx High School of Science, commonly called Bronx Science, is a public specialized high school in The Bronx in New York City. It is operated by the New York City Department of Education. Admission to Bronx Science involves passing the Spec ...

and

City College of New York The City College of the City University of New York (also known as the City College of New York, or simply City College or CCNY) is a public university within the City University of New York (CUNY) system in New York City. Founded in 1847, Cit ...

, where he (still in his teens) developed the theory that led to his independent discovery of

algorithmic complexity Algorithmic may refer to: *Algorithm, step-by-step instructions for a calculation **Algorithmic art, art made by an algorithm **Algorithmic composition, music made by an algorithm ** Algorithmic trading, trading decisions made by an algorithm **Alg ...

. Chaitin has defined

Chaitin's constant In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will ...

Ω, a

real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...

whose digits are

equidistributed In mathematics, a sequence (''s''1, ''s''2, ''s''3, ...) of real numbers is said to be equidistributed, or uniformly distributed, if the proportion of terms falling in a subinterval is proportional to the length of that subinterval. Such sequences ...

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 Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...

. Chaitin is also the originator of using

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 o ...

to do

register allocation In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers. Register allocation can happen over a basic block (''local register allocation' ...

compiling In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...

, a process known as

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. Chaitin's algorithm was the first register allocation algorithm that made u ...

. He was formerly a researcher at IBM's Thomas J. Watson Research Center in New York and remains an emeritus researcher. 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 Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. T ...

formalizations of the theory of

evolution Evolution is change in the heritable characteristics of biological populations over successive generations. These characteristics are the expressions of genes, which are passed on from parent to offspring during reproduction. Variation ...

Other scholarly contributions

Chaitin also writes about

philosophy Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such questions are often posed as problems to be studied or resolved. Some ...

, especially

metaphysics Metaphysics is the branch of philosophy that studies the fundamental nature of reality, the first principles of being, identity and change, space and time, causality, necessity, and possibility. It includes questions about the nature of conscio ...

and

philosophy of mathematics The philosophy of mathematics is the branch of philosophy that studies the assumptions, foundations, and implications of mathematics. It aims to understand the nature and methods of mathematics, and find out the place of mathematics in people's ...

(particularly about epistemological matters in mathematics). In metaphysics, Chaitin claims that

is the key to solving problems in the field of

biology Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary i ...

(obtaining a formal definition of 'life', its origin and

) and

neuroscience Neuroscience is the scientific study of the nervous system (the brain, spinal cord, and peripheral nervous system), its functions and disorders. It is a multidisciplinary science that combines physiology, anatomy, molecular biology, development ...

(the problem of

consciousness Consciousness, at its simplest, is sentience and awareness of internal and external existence. However, the lack of definitions has led to millennia of analyses, explanations and debates by philosophers, theologians, linguisticians, and scien ...

and the study of the mind). In recent writings, he defends a position known as

digital philosophy Computational philosophy or digital philosophy is the use of computational techniques in philosophy. It includes concepts such as computational models, algorithms, simulations, games, etc. that help in the research and teaching of philosophical ...

. In the

epistemology Epistemology (; ), or the theory of knowledge, is the branch of philosophy concerned with knowledge. Epistemology is considered a major subfield of philosophy, along with other major subfields such as ethics, logic, and metaphysics. Episte ...

of mathematics, he claims that his findings in

and algorithmic information theory show there are "mathematical facts that are true for no reason, that are true by accident". 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 An honorary degree is an academic degree for which a university (or other degree-awarding institution) has waived all of the usual requirements. It is also known by the Latin phrases ''honoris causa'' ("for the sake of the honour") or ''ad hono ...

'' by the

University of Maine The University of Maine (UMaine or UMO) is a Public university, public Land-grant university, land-grant research university in Orono, Maine. It was established in 1865 as the land-grant college of Maine and is the Flagship universities, flagshi ...

. In 2002 he was given the title of honorary professor by the

University of Buenos Aires The University of Buenos Aires ( es, Universidad de Buenos Aires, UBA) is a public university, public research university in Buenos Aires, Argentina. Established in 1821, it is the premier institution of higher learning in the country and one o ...

in Argentina, where his parents were born and where Chaitin spent part of his youth. In 2007 he was given a

Leibniz Medal The Berlin-Brandenburg Academy of Sciences and Humanities (german: Berlin-Brandenburgische Akademie der Wissenschaften), abbreviated BBAW, is the official academic society for the natural sciences and humanities for the German states of Berlin ...

Wolfram Research Wolfram Research, Inc. ( ) is an American multinational company that creates computational technology. Wolfram's flagship product is the technical computing program Wolfram Mathematica, first released on June 23, 1988. Other products include Wo ...

. In 2009 he was given the degree of doctor of philosophy ''honoris causa'' by the

National University of Córdoba The National University of Córdoba ( es, Universidad Nacional de Córdoba,) is an institution of higher education in the city of Córdoba, Argentina. Founded in 1613, the university is the oldest in Argentina, the third oldest university of t ...

. He was formerly a researcher at IBM's

Thomas J. Watson Research Center The Thomas J. Watson Research Center is the headquarters for IBM Research. The center comprises three sites, with its main laboratory in Yorktown Heights, New York, U.S., 38 miles (61 km) north of New York City, Albany, New York and with ...

and is now a professor at the

Federal University of Rio de Janeiro The Federal University of Rio de Janeiro or University of Brazil (UFRJ; pt, Universidade Federal do Rio de Janeiro or ') is a public research university located in the state of Rio de Janeiro, Brazil. It is the largest federal university in the ...

Criticism

Some philosophers and logicians disagree with the philosophical conclusions that Chaitin has drawn from his theorems related to what Chaitin thinks is a kind of fundamental arithmetic randomness. The logician

Torkel Franzén Torkel Franzén (1 April 1950, Norrbotten County – 19 April 2006, Stockholm) was a Swedish academic. Biography Franzén worked at the Department of Computer Science and Electrical Engineering at Luleå University of Technology, Sweden, in the fi ...

criticized Chaitin's interpretation of Gödel's incompleteness theorem and the alleged explanation for it that Chaitin's work represents.

Bibliography

*''Information, Randomness & Incompleteness'' (

World Scientific World Scientific Publishing is an academic publisher of scientific, technical, and medical books and journals headquartered in Singapore. The company was founded in 1981. It publishes about 600 books annually, along with 135 journals in various f ...

1987)
online
*''Algorithmic Information Theory'' (

Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press A university press is an academic publishing hou ...

1987
online
*''Information-theoretic Incompleteness'' (

1992)
online
*''The Limits of Mathematics'' (

Springer-Verlag Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 in ...

1998) *''The Unknowable'' (

1999) *''Exploring Randomness'' (

2001) *''Conversations with a Mathematician'' (

2002) *''From Philosophy to Program Size''
Tallinn Cybernetics Institute
2003) *''Meta Math!: The Quest for Omega'' (

Pantheon Books Pantheon Books is an American book publishing imprint with editorial independence. It is part of the Knopf Doubleday Publishing Group.Random House, Inc. Datamonitor Company Profiles Authority: Retrieved 6/20/2007, from EBSCO Host Business Source ...

2005) (reprinted in UK as ''Meta Maths: The Quest for Omega'',

Atlantic Books Atlantic Books is an independent British publishing house, with its headquarters in Ormond House in Bloomsbury, in the London Borough of Camden. It is perhaps best known for publishing Aravind Adiga's debut novel ''The White Tiger'', which rece ...

2006) () *''Teoria algoritmica della complessità''
G. Giappichelli Editore
2006) *''Thinking about Gödel & Turing'' (

2007) *''Mathematics, Complexity and Philosophy''
Editorial Midas
2011) *''Gödel's Way'' (

CRC Press The CRC Press, LLC is an American publishing group that specializes in producing technical books. Many of their books relate to engineering, science and mathematics. Their scope also includes books on business, forensics and information tec ...

2012) *''Proving Darwin: Making Biology Mathematical'' (

2012)

References

External links

G J Chaitin Home Page from academia.eduG J Chaitin Home Page from UMaine.edu in the Internet Archive

List of publications of G J Chaitin
*
Video of lecture on "Leibniz, complexity and incompleteness"
*

* ttp://www.flownet.com/gat/chaitin.html A short version of Chaitin's proofbr>Gregory Chaitin extended film interview and transcripts for the 'Why Are We Here?' documentary seriesChaitin Lisp on github
{{DEFAULTSORT:Chaitin, Gregory 1947 births Living people The Bronx High School of Science alumni City College of New York alumni Argentine mathematicians Argentine computer scientists 20th-century American mathematicians 21st-century American mathematicians American information theorists IBM employees Philosophers of mathematics Epistemologists Metaphysics writers American logicians 21st-century American philosophers Argentine information theorists Mathematicians from New York (state)