|
|
|
|
|
simulation'' arguments. Second, at moment n, Mf(i) does not use Mi's response to the entire sequence T[n] of incoming text T. Rather, Mf(i) uses Mi's response to some possibly proper initial segment T[j] of T[n]. Although the gap between the available and used segments of T may increase with time, Mf(i) eventually produces Mi's response to larger and larger initial segments of T on which Mi is defined. This feature of the proof may be called "falling back on the text." |
|
|
|
|
|
|
|
|
Proposition 4.15 gives us something more. |
|
|
|
|
|
|
|
|
4.16 Corollary There exists a recursively enumerable sequence of total computable scientists M0, M1,. . ., such that . |
|
|
|
|
|
|
|
|
We can take Mf(0),Mf(1),. . . to be one such enumeration. A counterpart of the above corollary holds for many of the paradigms considered in this book (with identical proofs). This fact can often be exploited to make diagonalization arguments simpler. |
|
|
|
|
|
|
|
|
§4.3 Function Identification by Computable Scientist |
|
|
|
|
|
|
|
|
We now introduce the paradigm Ex. As in the language case, the letters "Ex" are short for "explains" and signify that the success criterion is convergence to a single index for the target function. Scientists in the Ex model are computable functions either partial or total from SEG to N. All other aspects of the Ex paradigm are the same as for Func. We define: |
|
|
|
|
|
|
|
|
4.17 Definition (Gold [80]) (a) Let M be a computable scientist and let . M Ex-identifies f (written: just in case M identifies f. |
|
|
|
|
|
|
|
|
(b) . |
|
|
|
|
|
|
|
|
Analysis of Ex is facilitated by limiting attention to texts of a special kind. |
|
|
|
|
|
|
|
|
4.18 Definition Let G be a text for total function f. G is canonical just in case for all , G(n) =(n, f(n)) (that is, the pair (n, f(n)) occurs in the (n + 1)st position of G). Similarly, is in canonical order just in case s = (0, x0), (1, x1),. . . , (n, xn) for and x0, . . ., Let INIT be the collection of all that are in canonical order. |
|
|
|
|