文档介绍：ALGORITHMIC
INF ORMA TION
THEOR Y
Third Prin ting
G J Chaitin
IBM, P O Bo x704
Y orkto wn Heigh ts, NY 10598
******@ om
Septem b er 30, 1997
This b o ok w as published in 1987 b yCam bridge Uni-
v ersit y Press as the rst v olume in the series Cam-
bridge T racts in puter Science. In
1988 and 1990 it w as reprin ted with revisions. This
is the text of the third prin ting. Ho w ev er the APL
c haracter set is no longer used, since it is not gen-
erally a v ailable.
Ac kno wledgmen ts
The author is pleased to ac kno wledge p ermission to mak e free use of
previous publications:
Chapter 6 is based on his 1975 pap er \A theory of program size
formally iden tical to information theory" published in v olume 22 of the
c
Journal of the A CM, cop yrigh t
1975, Asso ciation puting
Mac hinery , Inc., reprin ted b y p ermission.
Chapters 7, 8, and 9 are based on his 1987 pap er \pleteness
theorems for random reals" published in v olume 8 of A dvanc es in Ap-
c
plie d Mathematics, cop yrigh t
1987 b y Academic Press, Inc.
The author wishes to thank Ralph Gomory , Gordon Lasher, and
the Ph ysics Departmen t of the W atson Researc h Cen ter.
1
2
F orew ord
T uring's deep 1937 pap er made it clear that G odel's astonishing earlier
results on arithmetic undecidabilit y related in a v ery natural w a ytoa
class puting automata, nonexisten t at the time of T uring's pap er,
but destined to app ear only a few y ears later, subsequen tly to proliferate
as the ubiquitous stored-puter of to da y . The app earance
puters, and the in v olv em en t of a large scien ti m unit yin
elucidation of their prop erties and limitations, greatly enric hed the line
of though t op ened b yT uring. T uring's distinction b et w puta-
tional problems w as ra wly binary: some w ere solv able b y algorithms,
others not. Later w ork, of whic h an attractiv e part is elegan tly dev el-
op ed in the presen tv olume, re ned this in t