# Defining computability for functionals of partial oracles

I believe a recursive (partial) functional $F:\mathbb{N}^\mathbb{N}\to\mathbb{N}$ is ordinarily defined as one for which the "graph" relation $F(\alpha)=n$ is recursively enumerable, which means it can be expressed in the form $$F(\alpha)=n \iff \exists x.Q(\overline{\alpha}(x), n, x)$$ for some (primitive?) recursive total predicate $Q$. Here $\overline{\alpha}(x) = \langle \alpha(0), \ldots, \alpha(x-1)\rangle$, i. e., the $x$-tuple of all the values of $\alpha(t)$ for $t\lt x$ encoded as a single natural number (it's not important how). This definition of recursiveness intuitively coincides with computability if we think of $\alpha$ as being given by an oracle (exercise, or see Shoenfield, Mathematical Logic.)

Unfortunately, I'm actually interested in the generalization where $\alpha$ may be a partial function itself and we don't know for which $t$ $\alpha(t)$ is undefined. If we try to evaluate $\alpha(t)$ and it happens to be undefined, then we simply wait forever for the answer which never comes. We can't cancel the request, either: once we ask the oracle for $\alpha(t)$, we're committed. Also, the oracle can only entertain one query at a time. (This is very important! For example, the functional that returns 0 if the domain of $\alpha$ is not empty and is undefined otherwise is not computable here, but it is computable if the oracle can entertain an arbitrary number of simultaneous queries. Similarly, allowing $n$ simultaneous queries yields a different class of computable functionals for each $n$.) The definition of recursiveness for partial functionals in the first paragraph fails in this generalization, since it could happen that our computation of $F(\alpha)$ queries a finite set of values of $\alpha(t)$ all with $t\lt x$, but $\alpha$ is undefined for some other $t\lt x$, so $\overline\alpha(x)$ is already undefined but our computation is fine.

In summary, I'm asking for a generalization of "recursive partial functional" for this situation.

• I like your concept, but do you have a specific question about it? May 13, 2011 at 0:37
• A thorough answer to this question will be quite long. In the meantime, may suggest section 4 of John R. Longley's survey, Notions of Computability at Higher Types I, [homepages.inf.ed.ac.uk/jrl/Research/notions1.pdf] ? May 13, 2011 at 4:00
• @Ulrik: It is long, but it seems completely relevant to my question. Besides, I've been curious about this subject for a while, so I don't mind a bit of reading. Thanks! May 14, 2011 at 1:59

This sounds like Jaap van Oosten's partial combinatory algebra $\mathcal{B}$, or its effective version, to be precise. You can read about it in John Longley's survey paper, as mentioned by Ulrik in the comments, or specifically in John's "Sequentially realizable functionals".