From Philosophy To Program Size

FROM PHILOSOPHY TO PROGRAM SIZE Key Ideas and Methods Lecture Notes on Algorithmic Information Theory from the 8th Estonian Winter School in Computer Science, EWSCS’03 Gregory J. Chaitin, IBM Research Institute of Cybernetics Tallinn Gregory J. Chaitin IBM Research P. O. Box 218, Yorktown Heights, NY 10598, USA http://www.cs.umaine.edu/~chaitin/ http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ The 8th Estonian Winter School in Computer Science, EWSCS’03, was held at Palmse, Estonia, 2-7 March 2003, organized by the Institute of Cybernetics, Tallinn. The organizers acknowledge the financial support from the Estonian Information Technology Foundation through the Tiigri¨ ulikool programme, the European Commission through the FP5 IST project eVikings II and the Ministry of Education and Research of Estonia through its Centers of Excellence in Research programme. Photos by Vahur Kotkas, Marko K¨a¨aramees Cover design by Kristiina Krabi Typesetting by the author Institute of Cybernetics at Tallinn Technical University Akadeemia tee 21, EE-12618 Tallinn, Estonia http://www.ioc.ee/ ISBN 9985-894-55-3 c Gregory J. Chaitin 2003 Printed and bound at Tallinna Raamatutr¨ ukikoda, Tallinn, Estonia. Preface This little book contains the course that I had the pleasure of giving at the 8th Estonian Winter School in Computer Science (EWSCS ’03) held at the beautiful Palmse manor in Lahemaa National Park, Estonia, from March 2nd through 7th, 2003. There I gave four 90-minute lectures on algorithmic information theory (AIT), which is the theory of programsize complexity. Each of these lectures is one chapter of this book. In these lectures I discuss philosophical applications of AIT, not practical applications. Indeed, I believe AIT has no practical applications. The most interesting thing about AIT is that you can almost never determine the