文档介绍：INF ORMA TION-
THEORETIC
PLETENESS
G. J. Chaitin
IBM, P O Bo x704
Y orkto wn Heigh ts, NY 10598
******@ om
Published 1992 b y
W orld Scien ti c, Singap ore
Ac kno wledgmen ts | The author and the publisher are grateful to the follo w-
ing for p ermission to reprin t the pap ers included in this v olume:
L aR e cher che ;
IPC Magazines Ltd. ( New Scientist );
Elsevier Science Publishing Co., Inc.
( Applie d Mathematics putation );
Klu w er Academic Publishers . and Marc E. Carv allo
( Natur e, Co gnition, and System, V ol. 3 );
Springer-V erlag New Y ork Inc. ( The Mathematic al Intel ligenc er ).
Thanks are due to Abraham P eled, Mic hael Blasgen and Martin Hopkins (Com-
puter Science Departmen t, W atson Researc hCen ter) for supp orting this researc h.
Also to Axel Leijonh ufvud and V ela V elupillai, whose in vitation to the author to
giv e a series of lectures at the UCLA Cen ter putable Economics w as an
imp ortan t stim ulus.
T omyp ar ents Sar a and Norman,
and to Maur e en and Carmen for b eing so swe et!
F orew ord
My book A lgorithmic Information The ory is lik e hiking up a moun tain
b y the fastest route, not stopping un til one reac hes the top. Here w e
shall instead tak e a lo ok at in teresting sigh ts along the w a y and explore
some alternate routes, in roughly the order that I disco v ered them.
In this b o ok I shall surv ey eigh t di eren t theories of program size
complexit y based on eigh t di eren t programming mo dels. And I'll dis-
cuss the pleteness results that one gets in eac h of these eigh t
theories.
I decided to tell this story in the form of a mathematical autobi-
ograph y .
Gregor y Chaitin
v
vi
Con ten ts
A life in math 1
I T ec hnical Surv ey 13
T uring mac hines 17
Blank-endmark er programs 25
LISP program-plexit y 37
LISP program-plexit yII 55
LISP program-plexit yIII 83
LISP program-plexit yIV 97
Information-theoretic pletenes