4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I like your concept, but do you have a specific question about it? $\endgroup$ May 13, 2011 at 0:37
  • 1
    $\begingroup$ 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] ? $\endgroup$ May 13, 2011 at 4:00
  • $\begingroup$ @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! $\endgroup$ May 14, 2011 at 1:59

1 Answer 1

4
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ May 14, 2011 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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