An Introduction to Kolmogorov Complexity and Its Applications
Briefly, we review the basic elements of computability theory and prob ability theory that are required. Finally, in order to place the subject in the appropriate historical and conceptual context we trace the main roots of Kolmogorov complexity. This wa
- PDF / 63,046,878 Bytes
- 655 Pages / 504.57 x 720 pts Page_size
- 51 Downloads / 217 Views
Springer Science+Business Media, LLC
GRADUATE TEXTS IN COMPUTER SCIENCE Fitting, First-Order Logic and Automated Theorem Proving Li and Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications Nerode and Shore, Logic for Applications Smith, A Recursive Introduction to the Theory of Computation Socher-Ambrosius and Johann, Deduction Systems
Ming Li
Paul Vitanyi
AN INTRODUCTION TO KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS Second Edition
With 41 Illustrations
Springer
Ming Li Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1 Canada
Paul Vitanyi Centrum voor Wiskunde en Informatica Kruislaan 413 1098 SJ Amsterdam The Netherlands
Series Editors David Gries Fred B. Schneider Department of Computer Science Cornell University Upson Hall Ithaca, NY 14853-7501, USA
Library of Congress Cataloging-in-Publication Data Li, Ming. An introduction to Kolmogorov complexity and its applications / Ming Li, Paul Vitanyi. - 2nd ed. p. cm. - (Graduate texts in computer science) Includes bibliographical references (p. - ) and index. ISBN 978-1-4757-2608-4 1. Kolmogorov complexity. I. Vitanyi, P.M.B. II. Title. III. Series: Graduate texts in computer science (Springer-Verlag New York Inc.) QA267.7.L5 1997 511.3-dc20 96-42357 Printed on acid-free paper.
© 1997, 1993 Springer Science+Business Media New York Originally published by Springer-Verlag New York, Inc. in 1997 Softcover reprint of the hardcover 2nd edition 1997
All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. Production managed by Lesley Poliner; manufacturing supervised by Jacqui Ashri. Photocomposed copy prepared from the authors' f8.TEJX files.
987654321 ISBN 978-1-4757-2608-4 ISBN 978-1-4757-2606-0 (eBook) DOI 10.1007/978-1-4757-2606-0
v
Preface to the First Edition
We are to admit no more causes of natural things (as we are told by Newton) than such as are both true and sufficient to explain their appearances. This central theme is basic to the pursuit of science, and goes back to the principle known as Occam's razor: "if presented with a choice between indifferent alternatives, then one ought to select the simplest one." Unconsciously or explicitly, informal applications of this principle in science and mathematics abound. The conglomerate of different research threads drawing on an objective and absolute form of this approach appears to be
