MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I like your concept, but do you have a specific question about it? – Joel David Hamkins May 13 '11 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, [] ? – Ulrik Buchholtz May 13 '11 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! – Darsh Ranjan May 14 '11 at 1:59
up vote 4 down vote accepted

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".

There are many, many variations of computability at higher types. I warmly recommend John's survey paper in this respect. May I ask about the motivation for your question?

share|cite|improve this answer
Thank you! Here's the gist of my motivation: about a year ago, I "proved" that every computable transformation on binary sequences can be represented in a certain form. Later, I realized that my definition of computability was lacking, and I was using/extending the Church-Turing thesis more than I wanted to. I eventually figured out that the inputs & outputs to my computable functions need to be oracles that compute binary sequences, which leads to my question. With a good definition of computability, I can redo the proof properly (for my own amusement; I don't think it's a new result). – Darsh Ranjan May 14 '11 at 2:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.