Page xi

		PREFACE

		The book in your hands offers an introduction to Formal Learning Theory and a review of its principal results. The theory is one of several mathematical approaches to the issues centering on intelligent adaptation to the environment. Other perspectives (not discussed here) include Bayesian probability theory, PAC ("probably, approximately correct") learning, and artificial life. The analysis developed in the present book conceives learners number theoretically and deploys the tools of recursive-function theory to understand how they can stabilize to an accurate view of reality. This line of inquiry was initiated in the 1960s by Hilary Putnam, R. J. Solomonoff, and E. Mark Gold. Since then it has developed prodigiously, to the point that a single work cannot encompass its many theorems.

		The book is self-contained, inasmuch as necessary material from the theory of computation is explained in Chapter 2. In addition, exercises throughout the text provide experience in using computational arguments to prove facts about learning.

		The present edition is built upon the first, but has aimed for wider coverage of the field. We are grateful to Scott Weinstein and Michael Stob for permission to rework and integrate the original text. The magnitude of our intellectual debt to them will be obvious to anyone who compares the two editions.

		We would like to express our gratitude to John Case and Mark Fulk. John introduced three of us to formal learning theory and helped shape our early understanding of the field. Mark was an invaluable friend. In his brief career he produced some beautiful results that have enriched the present work. Other profound intellectual debts are to the works of E. Mark Gold and Noam Chomsky. Gold [80] established the formal framework within which learning theory has developed. Chomsky's writings have revealed the intimate connection between the projection problem and human intelligence. In addition, we have been greatly influenced by the research of Blum and Blum [18], Angluin [6], Case and Smith [35], and Wexler and Cullicover [194].

		It is also our pleasure to thank Andris Ambainis, Robert Daley, Rusins Freivalds, William Gasarch, Klaus Jantke, Bala Kalyanasundaram, Shyam Kapur, Efim Kinber, Stuart Kurtz, Martin Kummer, Steffen Lange, Eric Martin, Franco Montagna, Matthias Ott, Carl Smith, Frank Stephan, Mahe Velauthapillai, Roll Wiehagen, and Thomas Zeugmann for countless discussions about learning. Many of their discoveries have been recounted in the pages to follow. For what is missing or mistold we alone are responsible.