|
|
|
|
|
Case 2: Some stage s starts but does not terminate. Let r and cur be as defined in step 1 of stage s. Since step 3 does not succeed, Mr does not Ex*-identify any extension of j p(3), and thus Mr does not Ex*-identify any extension of j p(cur). We have two subcases. |
|
|
|
|
|
|
|
|
Subcase 2.1: Each substage in stage s terminates. Let f = j p(cur). Clearly, f is computable and a member of C2, since f (1) = p(1) and max(Wp(1)) = p(cur). Also, by the success of step 4.3 and the diagonalization in step 4.5 in each substage, M1-r either diverges on f, or the last program output by M1-r on f commits infinitely many convergent errors. |
|
|
|
|
|
|
|
|
Subcase 2.2: Some substage s' in stage s starts but does not terminate. In this case, let avail be as of the end of step 4.1 in substage s' of stage s. Let f = j p(avail). Clearly, f is recursive and an extension of j p(cur). Also, f is a member of C2, since f(2) = p(2) and max(Wp(2)) = p(avail). However, since step 4.3 does not succeed, M1-r, does not Ex*-identify any extension of j p(cur) and thus does not Ex*-identify f. |
|
|
|
|
|
|
|
|
From the above eases it follows that . |
|
|
|
|
|
|
|
|
We leave it to the reader to show that the above proposition implies the following corollary which says that increasing the size of team results in identifiability of larger collections of functions. |
|
|
|
|
|
|
|
|
9.6 CorollaryLet ![0201-003.gif](0201-003.GIF) |
|
|
|
|
|
|
|
|
The study of the general case, , to which we will return in Section 9.5, is aided by results on identification of functions by probabilistic scientistsour next topic. |
|
|
|
|
|
|
|
|
§9.4 Identification by Probabilistic Scientists |
|
|
|
|
|
|
|
|
Computable scientists have played a central role in the paradigms studied thus far. In this section we consider probabilistic scientists that behave like computable scientists except that every now and then they have the ability to base their actions on the outcome of a random event such as the flip of a fair coin. |
|
|
|
|
|
|
|
|
More formally, a probabilistic scientist P may be construed as an algorithmic machine that is equipped with a fair t-sided coin (or die), where t is an integer greater than 1. P's response to an evidential state s depends, in general, not only on s but also on the outcomes of the coin flips that P performed up to that point. We formalize coin flips and coin flip sequences in the following definition. |
|
|
|
|