|
|
|
|
|
|
that children can acquire in normal fashion. This reflection leads to a new criterion of successful performance called "exact identification." To identify exactly a collection  of languages the learner must identify  and fail to identify any text for any language outside of  . |
|
|
|
|
|
|
|
|
4-1 Suppose that  contain only finitely many languages. Show that  . |
|
|
|
|
|
|
|
|
4-2 Let K be the r.e., nonrecursive set defined on page 25. Define |
|
|
|
|
|
|
|
|
 . |
|
|
|
|
|
|
|
|
Show that  |
|
|
|
|
|
|
|
|
4-3 Given a class  of scientists, denote by  the class of  such that some  identifies  . |
|
|
|
|
|
|
|
|
(a) Show that if  , then  but  is possible. |
|
|
|
|
|
|
|
|
(b) Evaluate the validity of the following claims. |
|
|
|
 |
|
|
|
|
(i)  . |
|
|
|
|
|
|
|
|
(ii)  . |
|
|
|
|
|
|
|
|
(iii)  . |
|
|
|
|
|
|
|
|
(iv)  . |
|
|
|
|
|
|
|
|
4-4 Given  . Let Li = {0,1, . . ., i}. Let  Suppose that  . Show that  if and only if  . |
|
|
|
|
|
|
|
|
4-5 Show that TxtEx is not closed under finite union. |
|
|
|
|
|
|
|
|
4-6 Show that there is  with the following properties. |
|
|
|
|
|
|
|
|
(a)  |
|
|
|
|
|
|
|
|
(b) Some scientist (not necessarily computable) identifies  confidently (see Exercise 3-21). |
|
|
|
|
|
|
|
|
(c) No computable scientist identifies  confidently. |
|
|
|
|
