Bibliography

Popularizations

A.M. Turing, ``Solvable and unsolvable problems,'' Science News 31, Penguin, 1954, pp. 7-23. [Reprinted in (two volumes of) A.M. Turing, Collected Works, 1992.]
E. Nagel, J.R. Newman, Gödel's Proof, New York University Press, 1958.
M. Davis, ``What is a computation?'' chapter in L.A. Steen, Mathematics Today—Twelve Informal Essays, Springer-Verlag, 1978.
D.R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979.
R. Rucker, Infinity and the Mind—The Science and Philosophy of the Infinite, Princeton University Press, 1995.
R. Rucker, Mind Tools—The Five Levels of Mathematical Reality, Houghton Mifflin, 1987.
J.L. Casti, Searching for Certainty—What Scientists Can Know About the Future, Morrow, 1990.
J. Barrow, Pi in the Sky—Counting, Thinking, and Being, Oxford University Press, 1992.
P. Davies, The Mind of God—The Scientific Basis for a Rational World, Simon & Schuster, 1992.
J.L. Casti, Complexification—Explaining a Paradoxical World Through the Science of Surprise, HarperCollins, 1994.
I. Peterson, The Jungles of Randomness—A Mathematical Safari, Wiley, 1998.
J.A. Paulos, Once Upon a Number—The Hidden Mathematical Logic of Stories, Basic Books, 1998.
G.J. Chaitin, The Unknowable, this URL, 1999.

Original Works

K. Gödel, ``On formally undecidable propositions of Principia Mathematica and related systems I,'' Monatshefte für Mathematik und Physik, Volume 38, 1931, pp. 173-198. [Reprinted in van Heijenoort, 1967 & Davis, 1965. Also published as a book by Basic Books, 1962 and Dover, 1992. Part II was never written.]
A.M. Turing, ``On computable numbers, with an application to the entscheidungsproblem,'' Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936-7, pp. 230-265. ``A correction,'' ibid., Volume 43, 1937, pp. 544-546. [Reprinted in Davis, 1965. Not included in Turing's Collected Works.]
G.J. Chaitin, Algorithmic Information Theory, Cambridge University Press, 1987.
G.J. Chaitin, The Limits of Mathematics—A Course on Information Theory and the Limits of Formal Reasoning, Springer-Verlag, 1998.

Collections of Papers

W.R. Ewald, From Kant to Hilbert—A Source Book in the Foundations of Mathematics, 2 volumes, Oxford University Press, 1996.
P. Mancosu, From Brouwer to Hilbert—The Debate on the Foundations of Mathematics in the 1920s, Oxford University Press, 1998.
J. van Heijenoort, From Frege to Gödel—A Source Book in Mathematical Logic 1879-1931, Harvard University Press, 1967.
M. Davis, The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven Press, 1965.
K. Gödel, Collected Works, 3 volumes to date, Oxford University Press, 1986-.
A.M. Turing, Collected Works, 3 volumes, North-Holland, 1992. [The volume with Turing's papers on mathematical logic was not published.]
M. Davis, Solvability, Provability, Definability: The Collected Works of Emil L. Post, Birkhäuser, 1994.
G.J. Chaitin, Information, Randomness & Incompleteness—Papers on Algorithmic Information Theory, 2nd Edition, World Scientific, 1990.
T. Tymoczko, New Directions in the Philosophy of Mathematics, 2nd Edition, Princeton University Press, 1998.

Biographies

E.T. Bell, ``Paradise lost? Cantor (1845-1918),'' last chapter in Men of Mathematics, Simon & Schuster, 1937.
J.W. Dauben, Georg Cantor—His Mathematics and Philosophy of the Infinite, Harvard University Press, 1979.
B. Russell, The Autobiography of Bertrand Russell 1872-1914, George Allen & Unwin, 1967.
A.R. Garciadiego, Bertrand Russell and the Origins of the Set-Theoretic ``Paradoxes,'' Birkhäuser Verlag, 1992.
W.P. van Stigt, Brouwer's Intuitionism, North-Holland, 1990.
C. Reid, Hilbert, Springer-Verlag, 1970.
J.W. Dawson, Jr., Logical Dilemmas—The Life and Work of Kurt Gödel, A.K. Peters, 1997.
H. Wang, A Logical Journey—From Gödel to Philosophy, MIT Press, 1996. [A biography of Gödel.]
W. DePauli-Schimanovich, P. Weibel, Kurt Gödel—Ein mathematischer Mythos, Verlag Hölder-Pichler-Tempsky, 1997.
S. Turing, Alan M. Turing, Heffers, 1959. [Written by Turing's mother.]
A. Hodges, Alan Turing: The Enigma, Simon & Schuster, 1983.
N. Macrae, John von Neumann, Random House, 1992.
S.M. Ulam, Adventures of a Mathematician, University of California Press, 1991. [Ulam's autobiography contains much information on von Neumann and on von Neumann's admiration for Gödel.]
C. Reid, Julia—A Life in Mathematics, Mathematical Association of America, 1996. [A biography of J. Robinson by her sister.]
C. Calude, People & Ideas in Theoretical Computer Science, Springer-Verlag, 1999. [Contains autobiographical essays by M. Davis and Y. Matijasevic.]
M. Kac, Enigmas of Chance—An Autobiography, Harper & Row, 1985.
G.J. Chaitin, Information-Theoretic Incompleteness, World Scientific, 1992. [A mathematical autobiography.]

Mathematical Fictions

[Works of fiction that in my opinion capture some of the feeling of doing mathematics.]

A. Huxley, Young Archimedes, in J.R. Newman, The World of Mathematics, volume 4, Simon & Schuster, 1956.
A. Huxley, The Genius and the Goddess, Harper & Brothers, 1955.
S. Zweig, The Royal Game and Other Stories, Harmony Books, 1981.
W. Tevis, The Queen's Gambit, Random House, 1983.
R. Goldstein, The Mind-Body Problem—A Novel, Random House, 1983.
G. Martínez, Regarding Roderer—A Novel About Genius, St. Martin's Press, 1994.
V. Tasic, Herbarium of Souls, Broken Jaw Press, 1998.
F. Dürrenmatt, The Physicists, Grove Press, 1991.
D. Aronofsky, π, 85 minute black and white film, independent, released 1998.
N.C. Chaitin, The Small Hours, 95 minute black and white film, NYC Museum of Modern Art Film Library, released 1962.
J.L. Casti, The Cambridge Quintet—A Work of Scientific Speculation, Little, Brown & Company, 1998.

Works on AIT

C. Calude, Information and Randomness—An Algorithmic Perspective, Springer-Verlag, 1994.
L. Brisson, F.W. Meyerstein, Inventer L'Univers—Le Problème de la Connaissance et les Modèles Cosmologiques, Les Belles Lettres, 1991.
L. Brisson, F.W. Meyerstein, Inventing the Universe—Plato's Timaeus, the Big Bang, and the Problem of Scientific Knowledge, State University of New York Press, 1995.
L. Brisson, F.W. Meyerstein, Puissance et Limites de la Raison—Le Problème des Valeurs, Les Belles Lettres, 1995.
G. Markowsky, ``An introduction to algorithmic information theory—its history and some examples,'' Complexity, Vol. 2, No. 4, March/April 1997, pp. 14-22.
G. Rozenberg, A. Salomaa, ``The secret number,'' last chapter in Cornerstones of Undecidability, Prentice-Hall, 1994.
G.R. Mulhauser, Mind Out of Matter—Topics in the Physical Foundations of Consciousness and Cognition, Kluwer Academic, 1998.

Publications on AIT by G.J. Chaitin

``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.
``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. Also reprinted in T. Tymoczko, New Directions in the Philosophy of Mathematics (Expanded Edition), Princeton University Press, 1998.
``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.
``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.
``A note on Monte Carlo primality tests and algorithmic information theory,'' with J.T. Schwartz, Communications on Pure and Applied Mathematics 31 (1978), pp. 521-527.
``Toward a mathematical definition of `life','' in R.D. Levine and M. Tribus, The Maximum Entropy Formalism, MIT Press, 1979, pp. 477-498.
``Algorithmic information theory,'' in Encyclopedia of Statistical Sciences, Volume 1, Wiley, 1982, pp. 38-41.
``Gödel's theorem and information,'' International Journal of Theoretical Physics 22 (1982), pp. 941-954. Reprinted in T. Tymoczko, New Directions in the Philosophy of Mathematics, Birkhäuser, 1986. Also reprinted in T. Tymoczko, New Directions in the Philosophy of Mathematics (Expanded Edition), Princeton University Press, 1998.
``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,'' in T.M. Cover and B. Gopinath, Open Problems in Communication and Computation, Springer-Verlag, 1987.
``An algebraic equation for the halting probability,'' in R. Herken, The Universal Turing Machine, Oxford University Press, 1988.
``Randomness in arithmetic,'' Scientific American 259, No. 1 (July 1988), pp. 80-85.
Algorithmic Information Theory, 2nd printing (with revisions), Cambridge University Press, 1988.
Information, Randomness & Incompleteness, 2nd edition, World Scientific, 1990. Errata: on page 26, line 25, ``quickly that'' should read ``quickly than''; on page 31, line 19, ``Here one'' should read ``Here once''; on page 55, line 17, ``RI, p. 35'' should read ``RI, 1962, p. 35''; on page 85, line 14, ``1. The problem'' should read ``1. The Problem''; on page 88, line 13, ``4. What is life?'' should read ``4. What is Life?''; on page 108, line 13, ``the table in'' should read ``in the table in''; on page 117, Theorem 2.3(q), ``H_C (s, t)'' should read ``H_C (s | t)''; on page 134, line 7, ``#{ n | H(n) ≤ n } ≤ 2ⁿ'' should read ``#{ k | H(k) ≤ n } ≤ 2ⁿ''; on page 274, bottom line, ``n_4p+4'' should read ``n_4p'+4''.
Algorithmic Information Theory, 3rd printing (with revisions), Cambridge University Press, 1990.
``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, and in N. Hall, Exploring Chaos, Norton, 1993.
``Algorithmic information & evolution,'' in O.T. Solbrig and G. Nicolis, Perspectives on Biological Complexity, IUBS Press, 1991, pp. 51-60.
``Le hasard des nombres,'' La Recherche 22, N^o 232 (mai 1991), pp. 610-615.
``Complexity and biology,'' New Scientist 132, No. 1789 (5 October 1991), p. 52.
``LISP program-size complexity,'' Applied Mathematics and Computation 49 (1992), pp. 79-93.
``Information-theoretic incompleteness,'' Applied Mathematics and Computation 52 (1992), pp. 83-101.
``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. Errata: on page 67, line 25, ``are there are'' should read ``are there''; on page 71, line 17, ``that case that'' should read ``the case that''; on page 75, line 25, ``the the'' should read ``the''; on page 75, line 31, ``− log₂ p − log₂ q'' should read ``− p log₂ p − q log₂ q''; on page 95, line 22, ``This value of'' should read ``The value of''; on page 98, line 34, ``they way they'' should read ``the way they''; on page 99, line 16, ``exactly same'' should read ``exactly the same''; on page 124, line 10, ``are there are'' should read ``are there''.
Algorithmic Information Theory, 4th printing, Cambridge University Press, 1992. (Identical to 3rd printing.) Erratum: on page 111, Theorem I0(q), ``H_C (s, t)'' should read ``H_C (s | t)''.
``Randomness in arithmetic and the decline and fall of reductionism in pure mathematics,'' Bulletin of the European Association for Theoretical Computer Science, No. 50 (June 1993), pp. 314-328. Reprinted in J.L. Casti and A. Karlqvist, Cooperation and Conflict in General Evolutionary Processes, Wiley, 1995. Also reprinted in Chaos, Solitons & Fractals, Vol. 5, No. 2, pp. 143-159, 1995.
``On the number of n-bit strings with maximum complexity,'' Applied Mathematics and Computation 59 (1993), pp. 97-100.
``Randomness and complexity in pure mathematics,'' International Journal of Bifurcation and Chaos 4 (1994), pp. 3-15. Reprinted in Lecture Notes in Physics, Vol. 461, Springer-Verlag, 1995.
``Responses to `Theoretical mathematics...','' Bulletin of the American Mathematical Society 30 (1994), pp. 181-182.
Foreword in C. Calude, Information and Randomness, Springer-Verlag, 1994, pp. ix-x.
``Randomness in arithmetic and the decline and fall of reductionism in pure mathematics,'' in J. Cornwell, Nature's Imagination, Oxford University Press, 1995, pp. 27-44. Slightly edited version of 1993 EATCS Bulletin paper.
``Program-size complexity computes the halting problem,'' Bulletin of the European Association for Theoretical Computer Science, No. 57 (October 1995), p. 198.
``The Berry paradox,'' Complexity 1, No. 1 (1995), pp. 26-30. Reprinted in Lecture Notes in Physics, Vol. 461, Springer-Verlag, 1995. Also reprinted in P. Århem, H. Liljenström, U. Svedin, Matter Matters?, Springer-Verlag, 1997.
``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, No. 5 (1996), pp. 270-305.
``An invitation to algorithmic information theory,'' DMTCS'96 Proceedings, Springer-Verlag, 1997, pp. 1-23.
The Limits of Mathematics, Springer-Verlag, 1998.
``Elegant LISP programs,'' in C. Calude, People and Ideas in Theoretical Computer Science, Springer-Verlag, 1999, pp. 32-52.