Size-limited oracles I am interested in complexity of algorithms which have access to the following peculiar sort of oracle:
Suppose that an invocation of an algorithm f with an input of size n has access to an oracle for f which works only when given input of size n/2 or less. For definiteness, let's say that f(x) for x less than n/2 can be computed in constant time and that calling the oracle with x greater than n/2 halts -- I want to avoid algorithms which call the oracle unless they are certain that the input they provide is sufficiently small.
Has anybody discussed such oracles? Obviously the effect is dramatic; for instance, if writing an algorithm to sum a sequence of numbers, access to such an oracle makes the entire computation constant time, by breaking the list into two sublists. I'm interested in the effect on more complicated problems, though, which may or may not decompose so easily.
 A: Computational problems that can be efficiently (i.e., polynomial-time) computed from solutions of the problem on shorter instances are known as (downward) self-reducible. A classical example is SAT: given a CNF $\phi$ in variables $x_0,\dots,x_n$, let $\phi_0$ and $\phi_1$ be the CNFs in variables $x_0,\dots,x_{n-1}$ obtained by setting $x_n$ to 0 or 1 (respectively), and simplifying the formula accordingly. Then $\phi$ is satisfiable iff $\phi_0$ or $\phi_1$ is satisfiable. For a discussion of the self-reducibility phenomenon and pointers to the literature, see e.g. 
ftp://ftp.cs.rutgers.edu/cs/pub/allender/cie.plenary.pdf or http://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/selke-ma.pdf .
A: Although I also find your concept interesting, the class of functions you get by this notion of computability will not be closed under composition. To see this, suppose that we have a noncomputable oracle $A$ consisting only of even natural numbers. The characteristic function of $A$ will not be $A$-computable using your notion, since if we could generate all information about $A$ from earlier information about $A$, then $A$ would be computable, contrary to assumption. But the function $n\mapsto 2n$ is computable, and the function $2n\mapsto 1$ if $n\in A$, otherwise $0$, is $A$-computable under your concept (if I have understood it correctly), but the composition of these functions would decide $A$. 
