An Introduction to Kolmogorov Complexity and Its Applications
This must-read textbook presents an essential introduction to Kolmogorov complexity (KC), a central theory and powerful tool in information science that deals with the quantity of information in individual objects. The text covers both the fundamental con
- PDF / 8,601,217 Bytes
- 852 Pages / 518.741 x 737.009 pts Page_size
- 25 Downloads / 170 Views
Ming Li Paul Vitányi
An Introduction to Kolmogorov Complexity and Its Applications Fourth Edition
Texts in Computer Science Series Editors David Gries, Department of Computer Science, Cornell University, Ithaca, NY, USA Orit Hazzan, Faculty of Education in Technology and Science, Technion— Israel Institute of Technology, Haifa, Israel
More information about this series at http://www.springer.com/series/3191
Ming Li Paul Vitányi •
An Introduction to Kolmogorov Complexity and Its Applications Fourth Edition
123
Ming Li University of Waterloo Waterloo, ON, Canada
e-mail: [email protected]
Paul Vitányi Centrum voor Wiskunde en Informatica (CWI) Amsterdam, The Netherlands
e-mail: [email protected]
ISSN 1868-0941 ISSN 1868-095X (electronic) Texts in Computer Science ISBN 978-3-030-11297-4 ISBN 978-3-030-11298-1 (eBook) https://doi.org/10.1007/978-3-030-11298-1 Library of Congress Control Number: 2018967734 1st and 2nd editions: © Springer Science+Business Media New York 1993, 1997 3rd and 4th editions: © Ming Li and Paul Vitányi 2008, 2019 This work is subject to copyright. All rights are solely and exclusively licensed by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer Nature Switzerland AG The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
To our wives, Wenhui and Pauline
Preface to the First Edition
Preface to the First Edition
vii
“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
Data Loading...
