|
|
|
|
|
the proposition. The following terminology is needed. First, we fix a standard method (uniform in i) for enumerating the set: |
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
Next, given x, and , we say that Mi "predicts (x, y) on s " just in case: |
|
|
|
|
|
|
|
|
(a) and |
|
|
|
|
|
|
|
|
(b) no pair of the form (x, z) occurs in content ( s ) for any . |
|
|
|
|
|
|
|
|
Finally, given text G and x, y, j, , we say that Mi "is seen within m steps to predict (x, y) in G at point j" just in case Mi predicts (x, y) on G[j + 1], and (G[j + 1], x, y) emerges from our standard enumeration of G within m steps of computation. |
|
|
|
|
|
|
|
|
We now give a procedure for enumerating the graph of a (possibly partial) function f as well as (possibly partial) functions g0, g1, . . . . (There may be finitely or infinitely many gi.) Exactly one of these functions will be total and each of the other functions, will be defined on some finite initial segment of N. (Which of these functions will be total depends on the behavior of Mi.) The enumeration of a function's graph proceeds by specifying its canonical text. In particular, Gf will denote the canonical text that enumerates f. Initially, Gf =(0, i). |
|
|
|
|
|
|
|
|
Procedure for enumerating the graphs of f and the gi's |
|
|
|
|
|
|
|
|
Stage n: Suppose that p is the current length of Gf. Let . . . . Search for the least number such that , m and Mi is seen in m steps to predict (x, 0) in G at point j. If such a exists, then set and also set |
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
If no such exists, then let gn be the function whose graph is enumerated by G and extend Gf no further. Proceed to the next stage only if exists; in this case, no more pairs will be enumerated into gn, which is thus finite. (Observe that if exists then no matter how f is extended subsequently, Mi has made a new, incorrect guess about f on Gf[j + 1]. On the other hand, if no such exists, then f is finite, gn is total, Mi fails to identify gn's canonical text, and no other functions are created.) |
|
|
|
|
|
|
|
|
It is easy to verify that if the construction proceeds through only n many stages, then: |
|
|
|
|
|
|
|
|
(a) only n + 2 functions f, g0, g1, . . ., gn are specified; |
|
|
|
|