INFORMATION, RANDOMNESS & INCOMPLETENESS
Papers on Algorithmic Information Theory
Second Edition
G J Chaitin, IBM Research
This collection of papers was
published by
World Scientific in Singapore.
The first edition
appeared in 1987, and the second edition appeared in 1990.
It may be ordered from the publisher or from
Barnes & Noble and
Amazon.
Available in hardcover & softcover.
ISBN:
9810201540 (2nd ed., hardcover),
9810201710 (2nd ed., softcover),
9971504790 (1st ed., hardcover),
9971504804 (1st ed., softcover).
324 pages (2nd ed.), 284 pages (1st ed.)
INFORMATION, RANDOMNESS & INCOMPLETENESS
Papers on Algorithmic Information Theory — Second Edition
World Scientific Series in Computer Science — Vol. 8
by Gregory J Chaitin (IBM)
This book
contains in easily accessible form all the main
ideas of the creator and principal architect of algorithmic
information theory. This expanded second edition has added
thirteen abstracts, a
1988 SCIENTIFIC AMERICAN article,
a
transcript of a EUROPALIA 89 lecture, and
an essay on biology.
Its new larger format makes it easier to read.
Chaitin's
ideas are a fundamental extension of those of Gödel and Turing and
have exploded some basic assumptions of mathematics and thrown new
light on the scientific method, epistemology, probability theory, and
of course computer science and information theory.
Readership: Computer scientists, mathematicians,
physicists, philosophers and biologists.
``Many of Chaitin's results are discussed in a delightful collection of his
published articles.''
— Joseph Ford, American Scientist
``Chaitin advances the cause of truths whose time have come; he is
preparing a roadmap to ease our voyage into a truly uncertain future. Those
who embark on this great adventure will most assuredly find sustenance in
the books reviewed here.''
— Joseph Ford, Foundations of Physics
``One will find [in Information, Randomness & Incompleteness] all kinds of
articles which are popularizations or epistemological reflections and
presentations which permit one to rapidly obtain a precise idea of the
subject and of some of its applications (in particular in the biological
domain). Very complete, it is recommended to anyone who is interested in
algorithmic information theory.'' (translated)
— JeanPaul Delahaye, La Recherche
About the author
Gregory J Chaitin is a member of the theoretical physics group
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 two
decades 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
programsize complexity in terms of selfdelimiting programs,
the definition of the relative complexity of one object
given a minimalsize program for another,
the discovery of the halting probability Ω and its
significance, the informationtheoretic 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.
Preface
God not only plays dice in quantum mechanics, but even
with the whole numbers!
The discovery of randomness in arithmetic is presented
in my book
Algorithmic Information Theory
published by Cambridge University Press.
There I show that to decide if an algebraic equation in
integers has finitely or infinitely many solutions is in
some cases absolutely intractable.
I exhibit an infinite series of such arithmetical
assertions that are
random arithmetical facts, and
for which it is essentially
the case that the only way to prove them is to assume them
as axioms.
This extreme form of Gödel incompleteness theorem shows
that some arithmetical truths are totally impervious to
reasoning.
The papers leading to this result
were published over a period of more than
twenty years in widely scattered journals,
but because of their unity of purpose they fall together
naturally into the present book, intended as a companion
volume to my Cambridge University Press monograph.
I hope that it will serve as a stimulus for work on
complexity, randomness and unpredictability, in physics and
biology as well as in metamathematics.
For the second edition, I have added the article ``Randomness in
arithmetic'' (Part I), a collection of abstracts (Part VII),
and, as an Epilogue, two essays which
have not been published elsewhere that assess the impact of
algorithmic information theory on mathematics and biology,
respectively.
I should also like to point out that it is straightforward to apply to
LISP the techniques used in Part VI to study boundedtransfer Turing
machines.
A few footnotes have been added to Part VI, but the subject richly
deserves book length treatment, and I intend to write a book
about LISP in the near future.
[LISP programsize complexity
is discussed at length in my book
InformationTheoretic Incompleteness
published by World Scientific in 1992.]
GREGORY CHAITIN
Contents
Part I—Introductory/Tutorial/Survey Papers
Randomness and mathematical proof, 1975
Randomness in arithmetic, 1988
On the difficulty of computations, 1970
Informationtheoretic computational complexity, 1974
Algorithmic information theory, 1982
Algorithmic information theory, 1977
Part II—Applications to Metamathematics
Gödel's theorem and information, 1982
Randomness and Gödel's theorem, 1986
An algebraic equation for the halting probability, 1988
Computing the busy beaver function, 1987
Part III—Applications to Biology
To a mathematical definition of ``life,'' 1970
Toward a mathematical definition of ``life,'' 1979
Part IV—Technical Papers on SelfDelimiting Programs
A theory of program size formally identical to information theory, 1975
Incompleteness theorems for random reals, 1987
Algorithmic entropy of sets, 1976
Part V—Technical Papers on BlankEndmarker Programs
Informationtheoretic limitations of formal systems, 1974
A note on Monte Carlo primality tests and algorithmic information theory, 1978
Informationtheoretic characterizations of recursive infinite strings, 1976
Program size, oracles and the jump operation, 1977
Part VI—Technical Papers on Turing Machines & LISP
On the length of programs for
computing finite binary sequences, 1966
On the length of programs for
computing finite binary sequences: Statistical considerations, 1969
On the simplicity and speed of programs for
computing infinite sets of natural numbers, 1969
Part VII—Abstracts
On the length of programs for
computing finite binary sequences by boundedtransfer Turing machines, 1966
On the length of programs for
computing finite binary sequences by boundedtransfer Turing machines II, 1966
Computational complexity and Gödel's incompleteness theorem, 1970
Computational complexity and Gödel's incompleteness theorem, 1971
Informationtheoretic aspects of the Turing degrees, 1972
Informationtheoretic aspects of Post's construction of a simple set, 1972
On the difficulty of generating
all binary strings of complexity less than N, 1972
On the greatest natural number of definitional or information
complexity ≤ N, 1973
A necessary and sufficient condition for an infinite binary string
to be recursive, 1973
There are few minimal descriptions, 1973
Informationtheoretic computational complexity, 1973
A theory of program size formally identical to information theory, 1974
Recent work on algorithmic information theory, 1977
Epilogue
Undecidability and randomness in pure mathematics, 1989
Algorithmic information and evolution, 1991
ERRATA
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^{n}''
should read
``#{ k  H(k) ≤ n } ≤ 2^{n}''.

On page 274, bottom line, ``n_{4p+4}''
should read ``n_{4p'+4}''.