|
|
|
|
|
|
(b)  . |
|
|
|
|
|
|
|
|
We leave it to the reader to work out counterparts of Proposition 8.10 and Corollary 8.11 for noisy and incomplete texts. |
|
|
|
|
|
|
|
|
It is worth examining in more detail the impact on function identification of just a single noisy input. The next proposition shows that there are collections of functions for which programs can be identified from accurate texts, but for which programs for arbitrary finite variants cannot be identified from texts with at most one spurious datum. |
|
|
|
|
|
|
|
|
8.12 Proposition  . |
|
|
|
|
|
|
|
|
Proof: For each  , define f' and f" as follows, for each j and  : |
|
|
|
|
|
|
|
|
Consider the following collections of functions: |
|
|
|
|
|
|
|
|
It is easy to verify that  and  (and hence  ). However, according to Theorem 4.25,  . It is easy to see that for any  , f(<0,0>) can be used to determine whether  or  . Thus, a scientist which Ex-identifies  can be constructed. |
|
|
|
|
|
|
|
|
Suppose by way of contradiction that scientist M N1Ex-identifies  . Then, using M, we show how to construct M' which Ex*-identifies  , contradicting Theorem 4.25. |
|
|
|
|
|
|
|
|
We first define two recursive functions twit and untwit. Let twit:  be a recursive function such that, for all s and  : |
|
|
|
|
