|
|
|
|
|
|
We use F to introduce clipped versions of j and the indexing  . For each i and s, define: |
|
|
|
|
|
|
|
|
Note that there are recursive functions f and g such that, for all i and s,  and  . |
|
|
|
|
|
|
|
|
Computation Relative to an Oracle. |
|
|
|
|
|
|
|
|
Informally, we say that a function a is computable relative to a set A if and only if a can be computed by an algorithm that, along with all the usual things algorithms are permitted to do, is allowed to use XA as a "built-in" subroutine. Formally, we say that a is computable relative to A if and only if there is a recursive functional F such that  For example, let K denote the diagonal halting problem set, that is,  K is a recursively enumerable, nonrecursive set.) Then,  computable relative to K. (See Exercise 2-8.) |
|
|
|
|
|
|
|
|
Suppose  an infinite sequence of integers. We write  and only if, for all but finitely many i, ai = b. If, for infinitely many i,  , we write  . We say that a is limiting partial recursive if and only if there is a (total) recursive function g such that, for all x,  . So, a (x) is defined if and only if the limit exists. We say that a is limiting recursive if and only if a is total and limiting partial recursive. The following lemma is essentially due to Post. |
|
|
|
|
|
|
|
|
2.11 Lemma A function a is limiting partial recursive if and only if a is partial recursive in the halting problem. |
|
|
|
|
|
|
|
|
Thus, the limiting partial recursive functions form a strictly larger class than  . A set A is limiting recursive if and only if XA is limiting recursive. A functional F:  is limiting recursive if and only if there is a total recursive functional  such that, for all f and x,  . |
|
|
|
|
