Page 213

		The next result completely characterizes in terms of probabilistic identification.

		9.33 Proposition (Pitt and Smith [151]) Suppose .

		Then,

		Proof: We first show that . The definition of IN implies that for all , IN(IN(p)) = IN(p). Now, by Corollary 9.31, we have .

		We now show that . Since , Proposition 9.32 implies that . Observe that . Thus, by Corollary 9.29, we have . Hence, . We need now only show that . Observe that for any , . Thus, . Since , we have . Therefore, .

		§9.6 Team and Probabilistic Identification of Languages

		Team identification of languages was introduced in Definition 9.4. We now adapt the machinery of probabilistic scientists introduced in Section 9.4 to language identification.

		Let P be a probabilistic scientist equipped with a t-sided coin and let T be a text for some language . Then, the probability of P TxtEx-identifying T is taken to be . It follows from Lemma 9.11 that {O | PO TxtEx-identifies T} is measurable.

		The following definition, motivated by the above discussion, introduces the probability of identification of a text.

		9.34 Definition (Pitt [149])Let T be a text and P be a probabilistic scientist equipped with a t-sided coin (). Then, denotes .

		The next definition describes language identification by probabilistic scientists. As in the case of function identification, there is no loss of generality in assuming a two-sided coin, since the analog of Lemma 9.14 can easily be shown to hold in this new context.