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.
INFORMATION-THEORETIC INCOMPLETENESS
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.
FOREWORD
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.
GREGORY CHAITIN
Autobiographical Sketch & Introduction—A Life in Math
Afterword
Bibliography—Sources of Quotations, Classics
ERRATA
G. J. Chaitin,
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, ``−log2 p −log2 q''
should read ``−p log2 p −q log2 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''.