文档介绍：ALGORITHMIC
INFORMATION
THEORY
Third Printing
GJChaitin
IBM, P O Box 218
Yorktown Heights, NY 10598
******@us.
April 2, 2003
This book was published in 1987 by Cambridge Uni-
versity Press as the first volume in the series Cam-
bridge Tracts in puter 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 puting
Machinery, Inc., reprinted by permission.
Chapters 7, 8, and 9 are based on his 1987 paper “pleteness
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 G¨odel’s astonishing earlier
results on arithmetic undecidability related in a very natural way to a
class puting 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-puter of today. The appearance
puters, and the involvement of a large munity in
elucidation of their properties and limitations, greatly enriched the line
of thought opened by Turing. Turing’s distinction puta-
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, refined this into a multiplicity of scales
putational difficulty, which is still developing as a fundamental
theory of information putation that plays much the same role