文档介绍：INF ORMA TION,
RANDOMNESS &
PLETENESS
P ap ers on Algorithmic
Information Theory
Second Edition
G J Chaitin
IBM, P O Bo x704
Y orkto wn Heigh ts, NY 10598
******@ om
Septem b er 30, 1997
This collection of reprin ts w as published b yW orld
Scien ti c in Singap ore. The rst edition app eared
in 1987, and the second edition app eared in 1990.
This is the second edition with an up dated bibliog-
raph y .
Ac kno wledgmen ts
The author and the publisher are grateful to the follo wing for p ermis-
sion to reprin t the pap ers included in this v olume.
Academic Press, Inc. ( A dv. Appl. Math. );
American Mathematical So ciet y( AMS Notic es );
Asso ciation puting Mac hinery ( J. A CM, SICA CT News,
SIGA CT News );
Cam bridge Univ ersit y Press ( A lgorithmic Information The ory );
Elsevier Science Publishers ( The or. Comput. Sci. );
IBM ( IBM J. R es. Dev. );
IEEE ( IEEE T r ans. Info. The ory, IEEE Symp osia A bstr acts );
N. Ik eda, Osak aUniv ersit y( Osaka J. Math. );
John Wiley & Sons, Inc. ( Encyclop e dia of Statistic al Sci., Com-
mun. Pur e Appl. Math. );
I. Kalan tari, W estern Illinois Univ ersit y( R e cursive F unction The-
ory: Newsletter );
MIT Press ( The Maximum Entr opy F ormalism );
P ergamon Journals Ltd. ( Comp. Math. Applic. );
Plen um Publishing Corp. ( Int. J. The or. Phys. );
1
2
I. Prigogine, Univ ersit e Libre de Bruxelles ( Mondes en D evelopp e-
ment );
Springer-V erlag ( Op en Pr oblems munic ation pu-
tation );
V erlag Kammerer & Un v erzagt ( The Universal T uring Machine|
A Half-Century Survey );
W. H. F reeman pan y( Sci. A mer. ).
Preface
Go d not only pla ys dice in quan tum mec hanics, but ev en with the whole
n um b ers! The disco v ery of randomness in arithmetic is presen ted in m y
book A lgorithmic Information The ory published b y Cam bridge Univ er-
sit y Press. There I sho w that to decide if an algebrai