Page 261

		12 Complexity Issues in Identification

		§12.1 Introduction

		Our study has thus far concentrated on the question of what is learnable in principle when there are no constraints on either

		(a) the computational resources required by the scientist, or

		(b) the complexity of final hypotheses.

		The present chapter discusses the prospects for learnability when resources are bounded,

		or when final hypotheses are required to be simple.

		The complexity of the Identification Process.

		Unlike the case for complexity of computable functions, there are no standard notions of "feasible" identification or even agreement about how to measure the computation costs of identification. Worse yet, the study of the computational complexity of functionals and operators is still in its infancy, with knotty questions surrounding even the most basic definitions — see Cook [44], Kapron and Cook [102], Seth [169, 170], and Royer [160].

		In the light of the above difficulties, only partial attempts have been made to model the complexity of the identification process. Some of these are:

		1. bounding the number of mind changes made by a scientist before convergence (discussed in Section 12.2);

		2. bounding the number of examples required before the onset of convergence (discussed in Section 12.3);

		3. measuring the amount of computation done by the scientist before the onset of convergence (discussed in Exercise 12-6).

		Additionally, in Section 12.4 we discuss an axiomatic treatment of the complexity of convergence.

		The complexity of the Final Hypothesis.

		It is easy to motivate the desire for succinct final hypotheses. Numerous formulations of succinctness have been advanced for both functions and languages. Sections 12.5 and 12.6 examine a number of such proposals for languages. The analogous cases for functions can be found in the exercises.