|
|
|
|
|
|
(b)  . |
|
|
|
|
|
|
|
|
The following proposition shows that identification from recursive texts fails to yield any advantage over identification from arbitrary texts. |
|
|
|
|
|
|
|
|
8.34 Proposition For all  , TxtExa = RecTxtExa. |
|
|
|
|
|
|
|
|
Proof: Follows from the stabilizing sequence construction given in Chapter 5. |
|
|
|
|
|
|
|
|
However, the story is completely different if the scientists are not required to be computable. The following definition introduces the notion of identification from recursive texts by scientists that may not be computable. Convention: F in the following ranges over possibly noncomputable scientists. |
|
|
|
|
|
|
|
|
(a) F RecLang-identifies L (written:  ) just in case for all recursive texts T for L,  and WF(T) = L. |
|
|
|
|
|
|
|
|
(b)  |
|
|
|
|
|
|
|
|
The next proposition says that there is a single noncomputable scientist that identifies each recursively enumerable language from recursive texts. |
|
|
|
|
|
|
|
|
8.36 Proposition  . |
|
|
|
|
|
|
|
|
Proof: Consider the following F: |
|
|
|
|
|
|
|
|
Begin ( F on s )
 Let i be the least number such that for all  , j i(n) = s (n).
Output the least grammar for range ( j i) - { # }. |
|
|
|
|
|
|
|
|
It is easy to see that  |
|
|
|
|
|
|
|
|
It should be noted that if caretakers and natural phenomena are assumed to be computer simulable, then there is no reason to consider, as in the above case, noncomputable scientists and children. But, since the computable nature of children and their environments is only a hypothesis, it is worth considering identification on nonrecursive texts by both computable and noncomputable scientists. We have yet to isolate the nonrecursive texts for separate study. The following definition fills this gap. |
|
|
|
|
