List of Publications of G J Chaitin

An improvement on a theorem of E. F. Moore
IEEE Transactions on Electronic Computers EC-14 (1965), pp. 466-467.
On the length of programs for computing finite binary sequences by bounded-transfer Turing machines
AMS Notices 13 (1966), p. 133.
On the length of programs for computing finite binary sequences by bounded-transfer Turing machines II
AMS Notices 13 (1966), pp. 228-229.
On the length of programs for computing finite binary sequences
Journal of the ACM 13 (1966), pp. 547-569.
On the length of programs for computing finite binary sequences: statistical considerations
Journal of the ACM 16 (1969), pp. 145-159.
On the simplicity and speed of programs for computing infinite sets of natural numbers
Journal of the ACM 16 (1969), pp. 407-422.
On the difficulty of computations
IEEE Transactions on Information Theory IT-16 (1970), pp. 5-9.
Reprinted in Thinking about Gödel & Turing, 2007.
To a mathematical definition of "life"
ACM SICACT News, No. 4 (Jan. 1970), pp. 12-18.
Computational complexity and Gödel's incompleteness theorem
AMS Notices 17 (1970), p. 672.
Computational complexity and Gödel's incompleteness theorem
ACM SIGACT News, No. 9 (April 1971), pp. 11-12.
Information-theoretic aspects of the Turing degrees
AMS Notices 19 (1972), pp. A-601, A-602.
Information-theoretic aspects of Post's construction of a simple set
AMS Notices 19 (1972), p. A-712.
On the difficulty of generating all binary strings of complexity less than n
AMS Notices 19 (1972), p. A-764.
On the greatest natural number of definitional or information complexity less than or equal to n
Recursive Function Theory: Newsletter, No. 4 (Jan. 1973), pp. 11-13.
A necessary and sufficient condition for an infinite binary string to be recursive
Recursive Function Theory: Newsletter, No. 4 (Jan. 1973), p. 13.
There are few minimal descriptions
Recursive Function Theory: Newsletter, No. 4 (Jan. 1973), p. 14.
Information-theoretic computational complexity
Abstracts of Papers, 1973 IEEE International Symposium on Information Theory, p. F1-1.
Information-theoretic computational complexity
IEEE Transactions on Information Theory IT-20 (1974), pp. 10-15.
Reprinted in T. Tymoczko, New Directions in the Philosophy of Mathematics, Birkhäuser, 1986, Expanded Edition, Princeton University Press, 1998.
Reprinted in Thinking about Gödel & Turing, 2007.
Information-theoretic limitations of formal systems
Journal of the ACM 21 (1974), pp. 403-424.
A theory of program size formally identical to information theory
Abstracts of Papers, 1974 IEEE International Symposium on Information Theory, p. 2.
Randomness and mathematical proof
Scientific American 232, No. 5 (May 1975), pp. 47-52.
Reprinted in N.H. Gregersen, From Complexity to Life, Oxford University Press, 2003.
Reprinted in Thinking about Gödel & Turing, 2007.
A theory of program size formally identical to information theory
Journal of the ACM 22 (1975), pp. 329-340.
Information-theoretic characterizations of recursive infinite strings
Theoretical Computer Science 2 (1976), pp. 45-48.
Algorithmic entropy of sets
Computers & Mathematics with Applications 2 (1976), pp. 233-245.
Program size, oracles, and the jump operation
Osaka Journal of Mathematics 14 (1977), pp. 139-149.
Algorithmic information theory
IBM Journal of Research and Development 21 (1977), pp. 350-359, 496.
Recent work on algorithmic information theory
Abstracts of Papers, 1977 IEEE International Symposium on Information Theory, p. 129.
G. Chaitin, J.T. Schwartz:
A note on Monte Carlo primality tests and algorithmic information theory
Communications on Pure and Applied Mathematics 31 (1978), pp. 521-527.
Toward a mathematical definition of "life"
R.D. Levine, M. Tribus, The Maximum Entropy Formalism, MIT Press, 1979, pp. 477-498.
Algorithmic information theory
Encyclopedia of Statistical Sciences, Volume 1, Wiley, 1982, pp. 38-41.
Gödel's theorem and information
International Journal of Theoretical Physics 21 (1982), pp. 941-954.
Reprinted in T. Tymoczko, New Directions in the Philosophy of Mathematics, Birkhäuser, 1986, Expanded Edition, Princeton University Press, 1998.
Reprinted in Polish in R. Murawski, Współczesna filozofia matematyki, PWN, 2002.
Reprinted in Thinking about Gödel & Turing, 2007.
Randomness and Gödel's theorem
Mondes en Développement, No. 54-55 (1986), pp. 125-128.
Incompleteness theorems for random reals
Advances in Applied Mathematics 8 (1987), pp. 119-146.
Algorithmic Information Theory
Cambridge University Press, 1987.
Information, Randomness & Incompleteness
World Scientific, 1987.
Computing the busy beaver function
T.M. Cover, B. Gopinath, Open Problems in Communication and Computation, Springer-Verlag, 1987, pp. 108-112.
An algebraic equation for the halting probability
R. Herken, The Universal Turing Machine, Oxford University Press, 1988, pp. 279-283.
Randomness in arithmetic
Scientific American 259, No. 1 (July 1988), pp. 80-85.
Reprinted in Thinking about Gödel & Turing, 2007.
Algorithmic Information Theory
2nd printing (with revisions)
Cambridge University Press, 1988.
Algorithmic Information Theory
3rd printing (with revisions)
Cambridge University Press, 1990.
Algorithmic information & evolution
O.T. Solbrig, G. Nicolis, Perspectives on Biological Complexity, IUBS Press, 1991, pp. 51-60.
Information, Randomness & Incompleteness
2nd edition
World Scientific, 1990.
Contains all the preceding papers in this list except for my 1965 paper An improvement on a theorem of E. F. Moore.
A random walk in arithmetic
New Scientist 125, No. 1709 (24 March 1990), pp. 44-46.
Reprinted in N. Hall, The New Scientist Guide to Chaos, Penguin, 1992, (UK edition), Exploring Chaos, Norton, 1993, (US edition).
Le hasard des nombres
La Recherche 22, N^o 232 (mai 1991), pp. 610-615.
Reprinted in La Recherche, Hors-Série N^o 2 (août 1999), pp. 60-65.
Reprinted in La Recherche, Histoire des nombres, Tallandier, 2007.
Complexity and biology
New Scientist 132, No. 1789 (5 October 1991), p. 52.
Information-theoretic incompleteness
Applied Mathematics and Computation 52 (1992), pp. 83-101.
LISP program-size complexity
Applied Mathematics and Computation 49 (1992), pp. 79-93.
LISP program-size complexity II
Applied Mathematics and Computation 52 (1992), pp. 103-126.
LISP program-size complexity III
Applied Mathematics and Computation 52 (1992), pp. 127-139.
LISP program-size complexity IV
Applied Mathematics and Computation 52 (1992), pp. 141-147.
A Diary on Information Theory
The Mathematical Intelligencer 14, No. 4 (Fall 1992), pp. 69-71.
Information-Theoretic Incompleteness
World Scientific, 1992.
Includes the preceding nine papers.
Algorithmic Information Theory
4th printing
Cambridge University Press, 1992.
Identical to 3rd printing.
Randomness in arithmetic and the decline and fall of reductionism in pure mathematics
Bulletin of the European Association for Theoretical Computer Science 50 (June 1993), pp. 314-328.
Reprinted in J. Cornwell, Nature's Imagination, Oxford University Press, 1995, pp. 27-44.
Reprinted in The Limits of Mathematics, 1998.
Reprinted in Thinking about Gödel & Turing, 2007.
Il y a aussi une traduction française.
On the number of n-bit strings with maximum complexity
Applied Mathematics and Computation 59 (1993), pp. 97-100.
Responses to "Theoretical mathematics..."
Bulletin of the American Mathematical Society 30 (1994), pp. 181-182.
Program-size complexity computes the halting problem
Bulletin of the European Association for Theoretical Computer Science 57 (October 1995), p. 198.
The Berry paradox
Complexity 1, No. 1 (1995), pp. 26-30.
A new version of algorithmic information theory
Complexity 1, No. 4 (1995/1996), pp. 55-59.
How to run algorithmic information theory on a computer
Complexity 2, No. 1 (September 1996), pp. 15-21.
The limits of mathematics
Journal of Universal Computer Science 2 (1996), pp. 270-305.
Reprinted in The Limits of Mathematics, 1998.
An invitation to algorithmic information theory
DMTCS'96 Proceedings, Springer-Verlag, 1997, pp. 1-23.
Reprinted in The Limits of Mathematics, 1998.
The Limits of Mathematics
Springer-Verlag, 1998.
Published in Japanese by SIB-Access, 2001.
Elegant LISP programs
C. Calude, People and Ideas in Theoretical Computer Science, Springer-Verlag, 1999, pp. 32-52.
Reprinted in The Limits of Mathematics, 1998.
The Unknowable
Springer-Verlag, 1999.
Published in Japanese by SIB-Access, 2001.
C. Calude, G. Chaitin:
Randomness everywhere
Nature 400 (1999), pp. 319-320.
A century of controversy over the foundations of mathematics
C. Calude, G. Paun, Finite vs. Infinite, Springer-Verlag, 2000, pp. 75-100.
Reprinted in Italian in V. Manca, Logica matematica, Bollati Boringhieri, 2001.
Reprinted in Conversations with a Mathematician, 2002.
Reprinted in Turkish in B.S. Gür, Matematik Felsefesi, Orient, 2004.
Reprinted in Thinking about Gödel & Turing, 2007.
A century of controversy over the foundations of mathematics
Complexity 5, No. 5 (May/June 2000), pp. 12-21.
Reprinted in Exploring Randomness, 2001.
Reprinted in Thinking about Gödel & Turing, 2007.
Exploring Randomness
Springer-Verlag, 2001.
Conversations with a Mathematician
Springer-Verlag, 2002.
Published in Japanese by Iwanami Shoten, 2003; published in Portuguese by Gradiva, 2003.
Computers, paradoxes and the foundations of mathematics
American Scientist 90 (2002), pp. 164-171.
Reprinted in Meta Math!, 2005.
Metamathematics and the foundations of mathematics
Bulletin of the European Association for Theoretical Computer Science 77 (June 2002), pp. 167-179.
Reprinted in Italian in Enciclopedia del Novecento: Supplemento III, vol. H-W, 2004, pp. 111-116.
Reprinted in Thinking about Gödel & Turing, 2007.
Paradoxes of randomness
Complexity 7, No. 5 (May/June 2002), pp. 14-21.
Reprinted in Thinking about Gödel & Turing, 2007.
Complexité, logique et hasard
R. Benkirane, La Complexité, Éditions Le Pommier, 2002, pp. 283-310.
Published in Italian as R. Benkirane, La teoria della complessità, Bollati Boringhieri, 2007.
The unknowable
A. Miyake, H.U. Obrist, Bridge the Gap?, Walther König, 2002, pp. 39-47.
Two philosophical applications of algorithmic information theory
C.S. Calude, M.J. Dinneen, V. Vajnovszki, Discrete Mathematics and Theoretical Computer Science, Springer-Verlag, 2003, pp. 1-10.
Reprinted in Thinking about Gödel & Turing, 2007.
From Philosophy to Program Size
Tallinn Institute of Cybernetics, 2003.
Interview with performance artist Marina Abramovic
H.U. Obrist, Interviews, Charta, 2003, pp. 29-44.
L'univers est-il intelligible?
La Recherche, N^o 370 (décembre 2003), pp. 34-41.
Reprinted in Teoria algoritmica della complessità, 2006.
Thoughts on the Riemann hypothesis
The Mathematical Intelligencer 26, No. 1 (Winter 2004), pp. 4-7.
On the intelligibility of the universe and the notions of simplicity, complexity and irreducibility
Grenzen und Grenzüberschreitungen, XIX. Deutscher Kongress für Philosophie, Bonn, 23.-27. September 2002, Vorträge und Kolloquien, Herausgegeben von Wolfram Hogrebe in Verbindung mit Joachim Bromand, Akademie Verlag, Berlin, 2004, pp. 517-534.
Reprinted in Meta Math!, 2005.
Reprinted in Thinking about Gödel & Turing, 2007.
Leibniz, information, math and physics
Wissen und Glauben / Knowledge and Belief. Akten des 26. Internationalen Wittgenstein-Symposiums 2003, Herausgegeben von L�ffler, Winfried / Weingartner, Paul, �BV & HPT, Wien, 2004, pp. 277-286.
Reprinted in Teoria algoritmica della complessità, 2006.
Reprinted in Thinking about Gödel & Turing, 2007.
Leibniz, randomness and the halting probability
Mathematics Today 40 (2004), pp. 138-139.
Reprinted in Teoria algoritmica della complessità, 2006.
Reprinted in Thinking about Gödel & Turing, 2007.
Algorithmic Information Theory
first paperback edition
Cambridge University Press, 2004.
Identical to 4th printing.
Meta Math!
Pantheon, 2005.
Published in Greek by Travlos Publications, 2007; published in Japanese by Hakuyosha, 2007; published in Italian by Adelphi, 2007.
Algorithmic irreducibility in a cellular automata universe
Journal of Universal Computer Science 11 (2005), pp. 1901-1903.
The limits of reason
Scientific American 294, No. 3 (March 2006), pp. 74-81.
Reprinted in Thinking about Gödel & Turing, 2007.
Probability and program-size for functions
Fundamenta Informaticae 71 (2006), pp. 367-370.
How real are real numbers?
International Journal of Bifurcation and Chaos 16 (2006), pp. 1841-1848.
Reprinted in Thinking about Gödel & Turing, 2007.
Epistemology as information theory: from Leibniz to Ω
Collapse 1 (2006), pp. 27-51.
Reprinted in Teoria algoritmica della complessità, 2006.
Reprinted in Thinking about Gödel & Turing, 2007.
Teoria algoritmica della complessità
Giappichelli, 2006.
Meta Maths
Atlantic Books, 2006.
Meta Math!
first paperback edition
Vintage, 2006.
Meta Maths
first UK paperback edition
Atlantic Books, 2007.
Speculations on biology, information and complexity
Bulletin of the European Association for Theoretical Computer Science 91 (February 2007), pp. 231-237.
Reprinted in Thinking about Gödel & Turing, 2007.
An algebraic characterization of the halting probability
Fundamenta Informaticae 79 (2007), pp. 17-23.
How much information can there be in a real number?
International Journal of Bifurcation and Chaos 17 (2007), pp. 1933-1935.
Reprinted in Thinking about Gödel & Turing, 2007.
Review of How Mathematicians Think
New Scientist 195, No. 2614 (28 July 2007), p. 49.
Thinking about Gödel and Turing: Essays on Complexity, 1970-2007
World Scientific, 2007.
Algorithmic information theory: some recollections
C.S. Calude, Randomness and Complexity, from Leibniz to Chaitin, World Scientific, 2007, pp. 423-441.
Review of Incompleteness: The Proof & Paradox of Kurt Gödel
Journal of Scientific Exploration 21 (2007), pp. 769-771.
The halting probability Ω: irreducible complexity in pure mathematics
Milan Journal of Mathematics 75 (2007) pp. 291-304.
Reprinted in Thinking about Gödel & Turing, 2007.
Epistemology as information theory: from Leibniz to Ω
Filosofia, scienza e bioetica nel dibattito contemporaneo --- Studi internazionali in onore di Evandro Agazzi,
A cura di Fabio Minazzi, Presidenza del consiglio dei ministri, Dipartimento per l'informazione e l'editoria,
Istituto poligrafico e zecca dello stato --- Roma 2007, pp. 453-464.
Reprinted in Thinking about Gödel & Turing, 2007.
Is incompleteness a serious problem?
G. Lolli, U. Pagallo, La complessità di Gödel, Giappichelli, 2008, pp. 65-69.
Reprinted in Thinking about Gödel & Turing, 2007.
Interview with Gregory Chaitin
L. Floridi, Philosophy of Computing & Information: 5 Questions, Automatic Press / VIP, 2008, pp. 49-55.
The halting probability via Wang tiles
Fundamenta Informaticae 86 (2008), pp. 429-433.
Irreducible complexity in pure mathematics
A. Pichler, H. Hrachovec, Wittgenstein and the Philosophy of Information (Proceedings of the 30th International Ludwig Wittgenstein-Symposium in Kirchberg, 2007), Ontos Verlag, 2008, pp. 261-272.
Foreword
I. Licata, A. Sakaji, Physics of Emergence and Organization, World Scientific, 2008, pp. v-vi.