|
|
|
|
|
|
4-21 (Advanced) We define a success criterion in the spirit of exact identification but somewhat weaker.5 Given scientist F and  , F exactly identifies  in the weak sense just in case F identifies  and F identifies no language in the complement of  . The class of all  such that some computable M:  identifies  exactly in the weak sense is denoted by TxtExWeakExact. Prove: |
|
|
|
|
|
|
|
|
(a)  if and only if  and  is  indexable. |
|
|
|
|
|
|
|
|
(b) There is  such that  is not  indexable. |
|
|
|
|
|
|
|
|
Conclude that  . |
|
|
|
 |
|
|
|
|
5 For the background to this exercise, see Rogers [158, Chapters 14,16] or Shoenfield [176, Chapters 6,7]. |
|
|
|
|
