ALGORITHMIC
INFORMATION
THEORY
Third Printing
G J Chaitin
IBM, P O Box 704
Yorktown Heights, NY 10598
chaitin@watson.ibm.com
September 30, 1997
This book was published in 1987 by Cambridge Uni-
versity Press as the rst volume in the series Cam-
bridge Tracts in Theoretical Computer Science. In
1988 and 1990 it was reprinted with revisions. This
is the text of the third printing. However the APL
character set is no longer used, since it is not gen-
erally available.
Acknowledgments
The author is pleased to acknowledge permission to make free use of
previous publications:
Chapter 6 is based on his 1975 paper \A theory of program size
formally identical to information theory" published in volume 22 of the
Journal of the ACM, copyright c
1975, Association for Computing
Machinery, Inc., reprinted by permission.
Chapters 7, 8, and 9 are based on his 1987 paper \Incompleteness
theorems for random reals" published in volume 8 of Advances in Ap-
plied Mathematics, copyright c
1987 by Academic Press, Inc.
The author wishes to thank Ralph Gomory, Gordon Lasher, and
the Physics Department of the Watson Research Center.
1
2
Foreword
Turing's deep 1937 paper made it clear that Godel's astonishing earlier
results on arithmetic undecidability related in a very natural way to a
class of computing automata, nonexistent at the time of Turing's paper,
but destined to appear only a few years later, subsequently to proliferate
as the ubiquitous stored-program computer of today. The appearance
of computers, and the involvement of a large scienti c community in
elucidation of their properties and limitations, greatly enriched the line
of thought opened by Turing. Turing's distinction between computa-
tional problems was rawly binary: some were solvable by algorithms,
others not. Later work, of which an attractive part is elegantly devel-
oped in the present volume, re ned this into a multiplicity of scales
of computational diculty, which is still developing as a fundamental
theory of information and computation that plays much the