|
|
|
|
|
|
the bound on the number of errors in the final inferred grammar. (We note that Corollary 10.21 may be directly argued from Corollary 10.6.) |
|
|
|
|
|
|
|
|
One might attempt to use Corollary 10.10 in a similar fashion in order to obtain an analogous hierarchy result about TxtBex-identification. However, this strategy yields only the partial hierarchy: |
|
|
|
|
|
|
|
|
Corollary 10.10 provides no information about whether TxtBexc,c = TxtBexc+1,c or  . This is because only diagonalization results can be translated from functions to languages. To obtain the full hierarchy we establish the following proposition which says that there is a collection of languages such that, for each member language L, an (a + 1)-error grammar can be identified, but an a-error grammar cannot always be TxtBex-identified even if the scientist is given the best possible additional information—an upper bound on MinGram0(L). |
|
|
|
|
|
|
|
|
10.22 Proposition Suppose  . Then,  . |
|
|
|
|
|
|
|
|
Proof: Let  , which is clearly in TxtExa+1. Suppose by way of contradiction that some scientist  . Then, by Kleene's recursion theorem (Theorem 2.3), there exists a grammar e informally described in stages below. |
|
|
|
|
|
|
|
|
Let iN be a grammar for N. Let  denote the finite subset of We enumerated before stage s. Let  and w = max ({ e, iN }). Go to stage 0. |
|
|
|
|
|
|
|
|
Begin ( Stage s )
Step 1.
 Search for a s extending s s until at least one of
Condition 1A.  .
Condition 1B. A set  of cardinality a + 1 is found.
holds.
If Condition 1A held, go to Step 2, otherwise go to Step 3.
Step 2. (The mind change case.)
Set m = max(content( s )) + 1.
Enumerate all of { 0, . . . , m} into We.
Let s s + 1 be an extension of s with content( s s + 1) = { 0, . . . , m }..
Go to stage s + 1.
Step 3. (A suitable D was found in Condition 1B.) |
|
|
|
|
, 
.