|
|
|
|
|
|
Analogous results hold for each of the paradigms treated in this chapter (see Exercise 6-1). As a consequence, to show the unlearnability of a certain collection of functions we shall often reason only about the behavior of total scientists, leaving this step of the argument implicit. |
|
|
|
|
|
|
|
|
It is clear from Definition 6.2 that, for each  ,  . To show that the containment is proper, we introduce a variant of the "self-describing" functions  introduced in Definition 4.24. |
|
|
|
|
|
|
|
|
6.4 Definition Let  .  is the set of all  such that f(0) is an index for an a-variant of f, that is, j f(0) = a f. |
|
|
|
|
|
|
|
|
The symbol  is read as "almost self-describing." It is clear that  , and that  just in case f(0) is a *-error index for f. By Lemma 2.4, for all  ,  . The following result shows that  is an example of an Exm+1-identifiable collection of functions that no scientist can Exm-identify. |
|
|
|
|
|
|
|
|
6.5 Proposition (Case and Smith [35]) For each  ,  . |
|
|
|
|
|
|
|
|
Proof: Fix m. Clearly,  . To show the proposition, it thus suffices to prove that  . |
|
|
|
|
|
|
|
|
Suppose by way of contradiction that scientist M Exm-identifies  . Without loss of generality we may assume that M is total (since an analog of Proposition 4.15 holds for Exm-identification). We now show the existence of a total computable function  such that M fails to Exm-identify f. The proof of this employs a technique that is frequently used in sequel, hence we discuss the idea behind the proof in some detail. |
|
|
|
|
|
|
|
|
We use Kleene's recursion theorem (Theorem 2.3) to construct a program with index e such that the (partial) function j e is defined in stages. At the start of the construction, we initialize j e (0) = e. The construction is arranged so that if it ever reaches stage s, then at the beginning of that stage the domain of j e will be {0, . . ., xs - 1}, a finite initial segment of N. In stage s, the construction dovetails between the following two processes until, if ever, the search in b succeeds. |
|
|
|
|
|
|
|
|
a. Hold back defining j e on the m + 1 many arguments xs, . . ., xs + m and, for x = xs + m + 1, xs + m + 2, . . . in turn, extend j e to take the value 0.
b. Search for a suitable extension of j e as defined thus far that forces the scientist M to change its mind. |
|
|
|
|
