Page 13

		at all. So we might be led to formulate more stringent criteria of scientific success that impose standards of efficiency. Indeed, this is the topic of Chapter 12, below.

		Although liberal with respect to efficiency, our present success criterion is stringent about accuracy. To succeed on a given list, the scientist must produce an English description for exactly the numbers in the list, with no omissions or additions. Such accuracy is required in order to make our games interesting, since the sets in play differ by only a few numbers. But what if the initial collection C were such that every pair of members was infinitely different? In this case, a small error in the scientist's final conjecture might be tolerable. Success in this approximate sense is the topic of Chapters 6 and 7.

		More generally, we shall investigate success criteria that are liberal and stringent in a wide variety of ways. In addition to efficiency and accuracy, we shall be concerned with tolerance for noisy data, with different senses of "last conjecture on a list," with behavior on lists outside of a given scientist's competence, and so forth. Of two, distinct criteria we often ask: What kinds of scientific problems can be solved under one criterion that cannot be solved under the other? In this way we hope to shed light on the limits of empirical inquiry that emerge from different kinds of scientific ambition.7

		Beyond what has been mentioned so far, many additional topics will occupy the chapters of the present book. But enough preliminaries! To get started in a serious way, it is now necessary to review a body of notation and conventions drawn from the theory of computation. This is the topic of the next chapter. Subsequently, in the remaining two chapters of Part I, we formally define and investigate some elementary paradigms.

		Summary

		The Theory of Machine Inductive Inference (or "Computational Learning Theory," etc.) attempts to clarify the process by which a child or adult discovers systematic generalizations about her environment. The clarification is achieved through the analysis of formal models — called paradigms — of scientific inquiry. Each paradigm specifies five concepts central to empirical inquiry, namely:

		(a) a theoretically possible reality

		(b) intelligible hypotheses

		(c) the data available about any given reality, were it actual

		7 As mentioned in the preface, however, the book is far from exhaustive in treating paradigms with claim to illuminating aspects of scientific discovery. In particular, we do not discuss PAC models of learning (see Kearns and Vazirani [105] for an excellent overview).