Gregory Chaitin | Academic Influence

Gregory Chaitin's AcademicInfluence.com Rankings

Gregory Chaitin

Computer Science

#148

World Rank

#155

Historical Rank

#89

USA Rank

computer-science Degrees

Gregory Chaitin

Mathematics

#256

World Rank

#554

Historical Rank

#124

USA Rank

Complexity Theory

#10

World Rank

#10

Historical Rank

#4

USA Rank

Measure Theory

#250

World Rank

#391

Historical Rank

#112

USA Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Gregory Chaitin's Degrees

Bachelors Mathematics City College of New York

Similar Degrees You Can Earn

Best Online Bachelor's in Math 2025

Why Is Gregory Chaitin Influential?

(Suggest an Edit or Addition)

According to Wikipedia, 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 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 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.

(See a Problem?)

Gregory Chaitin's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

On the Length of Programs for Computing Finite Binary Sequences (1966) (1133)
A Theory of Program Size Formally Identical to Information Theory (1975) (961)
Randomness and Mathematical Proof (1975) (637)
Register Allocation Via Coloring (1981) (619)
Register allocation & spilling via graph coloring (1982) (614)
A methodology for the real world (1981) (591)
Algorithmic Information Theory (1987) (519)
On the Length of Programs for Computing Finite Binary Sequences: statistical considerations (1969) (354)
Register allocation and spilling via graph coloring (2004) (343)
Algorithmic Information Theory: Algorithmic Information Theory (1987) (261)
Information-Theoretic Limitations of Formal Systems (1974) (219)
Register allocation via graph coloring (1981) (180)
Gödel's theorem and information (1982) (180)
Meta Math!: The Quest for Omega (2004) (176)
Information, Randomness and Incompleteness (1987) (173)
Information, Randomness and Incompleteness - Papers on Algorithmic Information Theory; 2nd Edition (1987) (163)
Information-Theoretic Computational Complexity (1974) (162)
The Limits of Mathematics (1995) (154)
Exploring RANDOMNESS (2001) (141)
Information-Theoretic Characterizations of Recursive Infinite Strings (1976) (114)
Information-theoretic computation complexity (1974) (112)
Incompleteness theorems for random reals (1987) (108)
On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers (1969) (104)
The limits of reason. (2006) (99)
Information-Theoretic Incompleteness (1992) (87)
Randomness in Arithmetic (1988) (82)
Proving Darwin: Making Biology Mathematical (2012) (76)
TOWARD A MATHEMATICAL DEFINITION OF “ LIFE ” (1979) (74)
Responses to `Theoretical mathematics: toward a cultural synthesis of mathematics and theoretical physics', by A. Jaffe and F. Quinn (1994) (73)
Randomness in arithmetic and the decline and fall of reductionism in pure mathematics (1993) (59)
On the difficulty of computations (1970) (58)
Information, Randomness & Incompleteness - Papers on Algorithmic Information Theory - Second Edition (1997) (50)
Computing the Busy Beaver Function (1987) (47)
Responses to: A. Jaffe and F. Quinn, “Theoretical mathematics: toward a cultural synthesis of mathematics and theoretical physics” [Bull. Amer. Math. Soc. (N.S.) 29 (1993), no. 1, 1–13; MR1202292 (94h:00007)] (1994) (43)
Thinking about Gödel and Turing - Essays on Complexity, 1970 - 2007 (2007) (41)
Computational complexity and Gödel's incompleteness theorem (1971) (41)
A note on monte carlo primality tests and algorithmic information theory (1978) (40)
Epistemology as Information Theory : From Leibniz to Ω ∗ (2005) (39)
The Unknowable (1999) (38)
The Berry paradox (1994) (35)
ALGORITHMIC ENTROPY OF SETS (1976) (34)
On the intelligibility of the universe and the notions of simplicity, complexity and irreducibility (2002) (33)
Life as Evolving Software (2012) (30)
Epistemology as Information Theory: From Leibniz to Omega (2005) (29)
Computers, paradoxes and the foundations of mathematics: Some great thinkers of the 20th century have shown that even in the austere world of mathematics, incompleteness and randomness are rife (2002) (28)
A century of controversy over the foundations of mathematics (1999) (27)
Kolmogorov complexity (2010) (27)
A Highly Random Number (2001) (26)
Mathematics: Randomness everywhere (1999) (26)
Two Philosophical Applications of Algorithmic Information Theory (2003) (25)
Randomness & complexity in pure mathematics (1994) (24)
Program-size Complexity Computes the Halting Problem (1995) (23)
TO A MATHEMATICAL DEFINITION OF “ LIFE ” (1970) (22)
The Halting Probability Omega: Irreducible Complexity in Pure Mathematics (2006) (20)
Thoughts on the riemann hypothesis (2003) (20)
Goedel's Way: Exploits into an undecidable world (2011) (20)
How Real are Real Numbers? (2004) (19)
Sequences and their Applications (2002) (19)
Evolution of Mutating Software (2009) (17)
The Shrinking Difference Between Artifacts and Natural Objects * (2008) (17)
A note on the number of N -bit strings with maximum complexity (1993) (15)
Metaphysics, Metamathematics and Metabiology (2011) (15)
Conversations with a Mathematician (2002) (15)
The LIMITS of MATHEMATICS: A Course on Information Theory and the Limits of Formal Reasoning (1997) (15)
From Philosophy to Program Size (2003) (14)
Irreducible Complexity in Pure Mathematics (2004) (14)
An Invitation to Algorithmic Information Theory (1996) (13)
Program size, oracles, and the jump operation (1977) (13)
A RANDOM WALK IN ARITHMETIC (1992) (12)
Another Example of Higher Order Randomness (2002) (12)
To a Mathematical Theory of Evolution and Biological Creativity (2011) (11)
A new version of algorithmic information theory (1995) (11)
The Halting Probability via Wang Tiles (2008) (10)
An Improvement on a Theorem of E. F. Moore (1965) (10)
Leibniz, Information, Math and Physics (2003) (10)
An Experiment in Autobiography (2020) (9)
Meta-Mathematics and the Foundations of Mathematics (2002) (9)
LISP program-size complexity III (1992) (9)
Conversations with a mathematician - math, art, science and the limits of reason (2002) (8)
How to run algorithmic information theory on a computer: Studying the limits of mathematical reasoning (1995) (8)
A Philosophical Perspective on a Metatheory of Biological Evolution (2018) (8)
RANDOMNESS AND GÖDEL'S THEOREM (1987) (8)
An algebraic equation for the halting probability (1988) (8)
Paradoxes of randomness and the limitations of mathematical reasoning (2002) (8)
Leibniz, Complexity and Incompleteness (2010) (7)
Register allocation and spilling via graph coloring (with retrospective) (1982) (7)
Leibniz, Randomness and the Halting Probability (2004) (7)
On Limits (2001) (7)
Paradoxes of Randomness (2001) (6)
Elegant Lisp Programs (2003) (6)
How Much Information Can There be in a Real Number? (2007) (5)
The Limits of Mathematics---Extended Abstract (1994) (5)
Algorithmic information theory: Some recollections (2007) (5)
Speculations on Biology, Information and Complexity (2006) (5)
Is the universe random (2011) (4)
INCOMPLETENESS THEOREMS FOR RANDOM REALS Advances in Applied Mathematics (1987) (4)
The Omega Number: Irreducible Complexity in Pure Math (2006) (4)
MATHEMATICS AS A BIOLOGICAL PROCESS (2011) (4)
LISP PROGRAM-SIZE COMPLEXITY IV (1992) (4)
Exhibiting Randomness in Arithmetic using Mathematica and C (1993) (4)
An Algebraic Characterization of the Halting Probability (2007) (3)
Witold Marciszewski Hypercomputational vs . Computational Complexity A Challenge for Methodology of the Social Sciences (2003) (3)
The Limits of Mathematics (in C) (1994) (3)
Some philosophical implications of information-theoretic computational complexity (1973) (3)
The Limits of Mathematics---The Book (1994) (2)
Building the World Out of Information and Computation: Is God a Programmer, Not a Mathematician? (2018) (2)
Computers, Paradoxes and the Foundations of Mathematics (2002) (2)
Number and Randomness: Algorithmic Information Theory — New Results on the Foundations of Mathematics (1997) (2)
RANDOMNESS AND G ¨ ODEL'S THEOREM (1986) (2)
Leibniz, information, math & physics (2007) (2)
Foundations of Mathematics (2002) (2)
The Limits of Mathematics - Course Outline and Software (Abstract) (1993) (2)
Theoretical interlude—What is randomness? My definitions (2001) (2)
Information-Theoretic Computational Complexity Invited Paper (2004) (2)
Description and Modeling (2006) (2)
The Limits of Mathematics---Tutorial Version (1995) (1)
Probability and Program-Size for Functions (2006) (1)
Algorithmic Irreducibility in a Cellular Automata Universe (2005) (1)
Lecture — Algorithmic Information Theory & the Foundations of Mathematics (2002) (1)
A New Version of Algorithmic Information Theory 1 (1995) (1)
ALGORITHMIC ENTROPY OF SETS Computers & Mathematics with Applications 2 ( 1976 ) , pp . 233 – 245 (1976) (1)
What is computation? (how) does nature compute? (2011) (1)
Why mathematics needs new heroes (2007) (1)
Is Incompleteness A Serious Problem (2006) (1)
Interview by Kate Mullen — Math, Science & Fantasy (2002) (0)
The Limits of Mathematics---Third Version (1994) (0)
Proof that Solovay randomness is equivalent to Martin-Löf randomness (2001) (0)
2 Origins of the Concept of Complexity in the Philosophy of Science and in Biology 2 . 1 Complexity in the work of (2014) (0)
Physics Foundations And Frontiers (2022) (0)
The Arithmetization of Register Machines (1987) (0)
Unknowability in Mathematics, Biology, and Physics (2020) (0)
BLANK-ENDMARKER PROGRAMS (1992) (0)
Great Mathematicians and the Geosciences: From Leibniz and Newton to Einstein and Hilbert (2010) (0)
What is LISP? Why do I like it? (2001) (0)
Algorithmic Information Theory: A Version of Pure LISP (1987) (0)
Algorithmic Information Theory: Preface (1987) (0)
HOW REAL ARE REAL NUMBERS? 1,2 (2011) (0)
A LIFE IN MATH (1992) (0)
The Information Economy (2008) (0)
Interview by Hans-Ulrich Obrist — The Creative Life: Science vs. Art (2002) (0)
Interview by Tor Nørretranders — How to be a Mathematician (2002) (0)
Algorithmic Information Theory: Formalisms for Computation: Register Machines, Exponential Diophantine Equations, & Pure LISP (1987) (0)
Interview by Guillermo Martínez — The Reason for My Life (2002) (0)
Interview by Jorge Pontual —Sensual Mathematics (2002) (0)
The halting probability Ω: Concentrated creativity (2007) (0)
Origins of the Concept of Complexity in the Philosophy of Science and in Biology (2015) (0)
The connection between program-size complexity and algorithmic probability: H(x) =-log 2 P(x) + O (1). Occam’s razor: there are few minimum-size programs (2001) (0)
A Visitor from Buenos Aires in the United States (2021) (0)
Leibniz, complexidade e incompletude (2016) (0)
The Limits of Mathematics---Alternative Version (1994) (0)
The Limits of Mathematics---Fourth Version (1994) (0)
The Solovay – Strassen and Miller – Rabin Algorithms (1978) (0)
Ideas on complexity and randomness originally suggested by Gottfried W. Leibniz in 1686, combined with modern information theory, imply that there can never be a "theory of everything" for all of mathematics (2006) (0)
Preface Human beings have a future if they deserve to have a future! (2008) (0)
Parents and their children (2021) (0)
Extending AIT to the size of programs for computing infinite sets and to computations with oracles (2001) (0)
Algorithmic Information Theory: Implementation Notes (1987) (0)
Algorithmic Information Theory: Program Size, Halting Probabilities, Randomness, & Metamathematics (1987) (0)
The Perfect Language (2015) (0)
Interview by Fisher Dilke — Randomness in Arithmetic (2002) (0)
A Century of Controvery Over the Foundations of Mathematics II (2000) (0)
A self-delimiting Turing machine considered as a set of (program, output) pairs (2001) (0)
Postscript—Letter to a daring young reader (2001) (0)
[Front mater] (2021) (0)
Proof that Martin-Löf randomness is equivalent to Chaitin randomness (2001) (0)
Proof that Solovay randomness is equivalent to strong Chaitin randomness (2001) (0)
Algorithmic Information Theory: The LISP Interpreter EVAL (1987) (0)
Plato ’ s Timaeus — The Universe is Intelligible . Origins of the Notion of Simplicity : Simplicity as Symmetry [ Brisson , Meyerstein (2002) (0)
How to construct self-delimiting Turing machines: the Kraft inequality (2001) (0)
Algorithmic Information Theory: Incompleteness (1987) (0)
Conceptual Complexity and Algorithmic Information (2020) (0)
The basic result on relative complexity:H(y∣x)=H(x,y)-H(x)+O(1) (2001) (0)
A Dialogue on Mathematics and Physics (2006) (0)
Single-particle software (1988) (0)
ARENA PROGRAM ON ‘NUMBERS’ (BBC TV) (1992) (0)
Lecture — Undecidability & Randomness in Pure Mathematics (2002) (0)
COMPLEXITY AND RANDOMNESS IN MATHEMATICS (1992) (0)
A Highly Random NumberVer (2001) (0)
Algorithmic Information Theory: Program Size (1987) (0)
The Number of S-expressions of Size N (1987) (0)
How to program my universal Turing machine in LISP (2001) (0)
Algorithmic Information Theory: Randomness (1987) (0)

This paper list is powered by the following services:

Other Resources About Gregory Chaitin

en.wikipedia.org

What Schools Are Affiliated With Gregory Chaitin?

Gregory Chaitin is affiliated with the following schools: