|
|
|
|
|
Let conv be as defined in Equation 9.1. Let , , . . . , be a permutation of 1, 2, . . . , 3j, such that, for each r = 1, . . . , 3j- 1, |
|
|
|
|
|
|
|
|
Define scientists , , and so that for each s : |
|
|
|
|
|
|
|
|
Now suppose T is a text for . Consider the following two cases. |
|
|
|
|
|
|
|
|
Case 1: At least 2j + 1 of the scientists in the team consisting of scientists M1, M2, . . . ,M3j converge on T. In this case, it is easy to verify that . Moreover, (respectively, ) TxtEx-identifies T if (respectively, does not TxtEx-identify T). |
|
|
|
|
|
|
|
|
Case 2: Not case 1. In this case, and . |
|
|
|
|
|
|
|
|
We leave it to the reader to modify the above proof to show the following result, which says that probabilistic identification of languages with probability of success at least is the same as team identification of languages with success ratio . |
|
|
|
|
|
|
|
|
9.39 Proposition . |
|
|
|
|
|
|
|
|
Proposition 9.40 below establishes that is indeed the cut-off point at which team identification of languages becomes more powerful than identification by a single scientist. |
|
|
|
|
|
|
|
|
9.40 Proposition . |
|
|
|
|
|
|
|
|
Proof: Let be as in the proof of Proposition 8.22. By Lemma 8.23, . So we need only show that . Consider a team consisting of three scientists M0, M1, and M2. For each , scientist Mi behaves as follows: On T[n], Mi outputs the maximum y, if any, such that . It is easy to verify that if T is a text for some language in , then at least two of the scientists will converge in the limit to a grammar for content(T). Thus, . |
|
|
|
|