Page 145

		''errors of omission" and "errors of commission" is due to Daley. Behaviorally correct function identification appears in the work of Barzdins * [14] (see also Feldman [58]). Case and Smith [35] investigated behaviorally correct identification in its full generality, including errors in the hypotheses. The result is due to Harrington (cited in Case and Smith [35]). The result that vacillatory function identification is the same as identification of functions is due to Barzdins* and Podnieks [16]. Later, Case and Smith [35] showed that this result holds even if errors are allowed in the final program.

		In the context of languages, errors in the final hypotheses were considered by Osherson and Weinstein [143] and by Case and Lynes [33]. These two papers also considered behaviorally correct language identification and its variants. Vacillatory language identification was first considered by Osherson and Weinstein [143] and later investigated extensively by Case [26].

		§6.4 Exercises

		6-1 Suppose . Show that there exists a recursively enumerable sequence of total computable scientists M0, M1, . . . such that, for each there is an i such that .

		6-2 Consider the following criteria of function identification.

		6.29 Definition Let .

		(a) M Ex=m-identifies f (written: ) just in case and .

		(b) M Ex=m-identifies S just in case .

		(c) .

		Show that for all , Exm = Ex.

		6-3 Prove each of the following.

		(a) COFIN is TxtEx*-identifiable, where COFIN is the collection of cofinite languages.

		(b) For each , .

		(c) Let . If scientist M TxtExa-identifies L, then there exists a such that the following hold: