Algorithmic_Information_Theory-Chaitin.pdf

ALGORITHMIC

INFORMATION

THEORY

Third Printing

GJChaitin

IBM, P O Box 218

Yorktown Heights, NY 10598

chaitin@us.ibm.com

April 2, 2003

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

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.

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

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 scientic 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, rened 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 same role

in computer science that classical thermodynamics plays in physics:

by dening the outer limits of the possible, it prevents designers of

algorithms from trying to create computational structures which prov-

ably do not exist. It is not surprising that such a thermodynamics of

information should be as rich in philosophical consequence as thermo-

dynamics itself.

This quantitative theory of description and computation, or Com-

putational Complexity Theory as it has come to be known, studies the

various kinds of resources required to describe and execute a computa-

tional process. Its most striking conclusion is that there exist computa-

tions and classes of computations having innocent-seeming denitions

but nevertheless requiring inordinate quantities of some computational

resource. Resources for which results of this kind have been established

include:

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: