Page 56

		(a) Every subset of an identifiable collection of languages is identifiable.

		(b) No superset of an unidentifiable collection of languages is identifiable.

		3-4 Given, scientist F, and , F is said to "p percent identify" just in case for each and each text T for L, there is such that:

		(a) Wi = L; and

		(b) for all but finitely many , F(T[j]) = i for p percent of .

		In this case, is "p percent identifiable." Prove that if p > 50, then is identifiable if and only if is p percent identifiable.

		3-5 Call easily distinguishable just in case for all there exists finite such that for all , if then .

		(a) Specify an identifiable collection of languages that is not easily distinguishable.

		(b) Let be given. Prove the following. Some self-monitoring scientist identifies if and only if is easily distinguishable.

		3-6 Suppose that F identifies . Let be such that . Prove that there is a such that is a locking sequence for F on L.

		3-7 Let  s  be a locking sequence for F on . Let be such that . Show that is a locking sequence for F on L.

		3-8 Refute the converse to Corollary 3.25. In other words, exhibit scientist F, , and such that  s  is a locking sequence for F on L, but F does not identify L.

		3-9 Suppose that scientist F identifies . Let T be a text for L. T is called a "locking text for F on L" just in case there exists such that T[n] is a locking sequence for F on L. Provide a counterexample to the following conjecture: If F identifies , then every text for L is a locking text for F on L.

		3-10 Show that some unidentifiable is 49 percent identifiable (see Exercise 3-4).

		3-11 Let be any indexed collection of subsets of N. Suppose that the Xi are used as languages in place of the indexed collection Wi of r.e. sets. How much of the discussion in Section 3.6 carries over to the Xi setting?