G J Chaitin, IBM Research

This collection of papers & autobiographical sketch was published by World Scientific in Singapore in 1992 and was reprinted in 1998.
It may be ordered from the publisher or from Amazon.
Currently available only in softcover.

ISBN: 981-02-3695-6 (softcover), 981-02-1208-9 (hardcover).

240 pages.

World Scientific Series in Computer Science — Vol. 35
by Gregory J Chaitin (IBM)

In this mathematical autobiography, Gregory Chaitin presents a technical survey of his work and a nontechnical discussion of its significance. The volume is an essential companion to the earlier collection of Chaitin's papers INFORMATION, RANDOMNESS & INCOMPLETENESS, also published by World Scientific.

The technical survey contains many new results, including a detailed discussion of LISP program size and new versions of Chaitin's most fundamental information-theoretic incompleteness theorems. The nontechnical part includes the lecture given by Chaitin in Gödel's classroom at the University of Vienna, a transcript of a BBC TV interview, and articles from NEW SCIENTIST, LA RECHERCHE, and the MATHEMATICAL INTELLIGENCER.

Readership: Computer scientists, mathematicians, physicists, philosophers and biologists.

``Chaitin has produced very deep results, with tremendous impact on mathematics, computer technology and philosophy (and, in particular, on Gödel's incompleteness theorem). His new book is another piece of jewelry in his (already) large gallery.'' — Cristian Calude, EATCS Bulletin

``The book under review is an extraordinary mathematical monograph.'' — M. I. Dekhtyar, Mathematical Reviews

``...the reviewer found the book most stimulating and highly recommends it.'' — A. A. Mullin, Zentralblatt MATH

About the author

Gregory J Chaitin is a member of the Computer Science Department at the IBM Thomas J Watson Research Center in Yorktown Heights, New York. He created algorithmic information theory in the mid 1960's when he was a teenager. In the quarter century since he has been the principal architect of the theory. His contributions include: the definition of a random sequence via algorithmic incompressibility, the reformulation of program-size complexity in terms of self-delimiting programs, the definition of the relative complexity of one object given a minimal-size program for another, the discovery of the halting probability Ω and its significance, the information-theoretic approach to Gödel's incompleteness theorem, the discovery that the question of whether an exponential diophantine equation has finitely or infinitely many solutions is in some cases absolutely random, and the theory of program size for Turing machines and for LISP. He is the author of the monograph Algorithmic Information Theory published by Cambridge University Press in 1987.


My book Algorithmic Information Theory is like hiking up a mountain by the fastest route, not stopping until one reaches the top. Here we shall instead take a look at interesting sights along the way and explore some alternate routes, in roughly the order that I discovered them.

In this book I shall survey eight different theories of program size complexity based on eight different programming models. And I'll discuss the incompleteness results that one gets in each of these eight theories.

I decided to tell this story in the form of a mathematical autobiography.



Autobiographical Sketch & Introduction—A Life in Math

Part I—Technical Survey

Turing Machines
Blank-Endmarker Programs
LISP Program-Size Complexity
LISP Incompleteness Theorems
Parenthesis-Free LISP
Character-String LISP
Self-Delimiting Programs

Part II—Non-Technical Discussions

BBC TV Arena Program
Article in New Scientist
Lecture in Vienna
Second Lecture in Vienna
Article in La Recherche
Lecture in Barcelona
Book Review in the Mathematical Intelligencer

Challenge for the Future—Biological Complexity

Book Review in New Scientist

Bibliography—Sources of Quotations, Classics


G. J. Chaitin, Information-Theoretic Incompleteness, World Scientific, 1992. Errata:

  1. On page 67, line 25, ``are there are'' should read ``are there''.

  2. On page 71, line 17, ``that case that'' should read ``the case that''.

  3. On page 75, line 25, ``the the'' should read ``the''.

  4. On page 75, line 31, ``−log2 p −log2 q'' should read ``−p log2 p −q log2 q''.

  5. On page 95, line 22, ``This value of'' should read ``The value of''.

  6. On page 98, line 34, ``they way they'' should read ``the way they''.

  7. On page 99, line 16, ``exactly same'' should read ``exactly the same''.

  8. On page 124, line 10, ``are there are'' should read ``are there''.