1
$\begingroup$

We can make the following distinctions: (I will use the term "program" and "machine" as synonyms).

  1. A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes an output, fully by itself.

  2. An oracle machine $T$. This is a Turing machine, but with an additional feature: it can use some black box "oracle" as a subroutine.

  3. A ??? machine $T$. This is a machine that does not have any subroutines like an oracle machine. Rather, it is itself a subroutine of some black-box (parent?) machine $P$.

The third type is supposed to capture the idea of "dependency injection". Suppose we have a fixed parent machine $P$, which takes as input our machine $T$, and uses it (in some way) to compute its output.

  • In the case of oracle machines $T$, we can "plug" an oracle $O$ into $T$, and study what can be achieved by $T$ given this oracle.

  • in the case of ??? machines, we do the opposite: we "plug" $T$ into a $P$, and see what can be achieved by $T$ given the constraint that it will be used as a subroutine by $P$.

The question is: What can we make $P$ compute, by programming $T$, given the constraint that $T$ will be used in some way (exactly how depends on the specific context we're interested in) by $P$? i.e. which functions are "$P$-computable"

Some observations:

  • oracle machines $T$ with oracle $O$ can compute at least as much as Turing machines, since they can just ignore the oracle.

  • ??? machines $T$ with "parent" $P$ can compute less than Turing machines, since they are constrained by being used by $P$ in some way that the programmer of $T$ cannot control. At two extremes: (1), $P$ may simply ignore $T$, in which case there is only a single unique "$P$-computable" function, namely whichever $P$ computes. (2) $P$ may literally copy its input into $T$, and output the output of $T$, in which case every Turing-computable function is also "$P$-computable". In between these extremes, $P$ may use $T$ as a subroutine, and use the output in some restricted way.

Alternatively, here is a more "mathematical" way of stating this:

Suppose we have a space $\mathcal C$ of "computable functions" (e.g. Turing-computable), and we have a "parent function", $P:\mathcal C\to \mathcal C$, which gives a family of function-parameterized functions $P_c$. $P$ takes a computable function $c$ (the function that is computed by the turing machine $T$ in our earlier formulation), and outputs a computable function $P_c$ (the function that is computed by giving $P$ the machines $T$ as its subroutine). The question now is: What is the image of $P$? These are the $P$-computable functions.

Is there a theory about something like this?

$\endgroup$
  • $\begingroup$ Your ??? is called an oracle. I'm not sure what you mean by "The question" - is $P$ given and fixed? what do you mean by that constraint? "will be used in some way" is too vague for me to understand what kind of constraint you have in mind. Can you give an example? Also, your mathematical way doesn't seem to match the above. I suspect you mean to ask what can be computed by algorithms of the form $P(c)^c$, where $c$ varies over all possibilities in $\mathcal{C}$. This is not the image of $P$. $\endgroup$ – D.W. May 2 at 19:27
  • $\begingroup$ "is $P$ given and fixed?" Yes! "what do you mean by that constraint? "will be used in some way" is too vague for me to understand what kind of constraint you have in mind." I simply mean that $P$ is some oracle machine that will use $T$ as a subroutine, in some fixed way. E.g. $P$ could do the following: Take an integer number as input (encoded in some way). Take the absolute value and sign of the input, and store them separately as $abs, sign$. Give $abs$ to $T$ as input, and whatever output comes out of $T$, multiply it by $sign$. This is what I mean by "use in some way". $\endgroup$ – user56834 May 2 at 20:56
  • $\begingroup$ cntd: So it is clear that in my above example, a lot of functions that are Turing computable, are not $P$-computable. E.g. we can't $P$-compute the absolute value function (meaning, we can't choose $T$ such that $P$, using $T$ as its subroutine in the above defined algorithm, will compute the absolute value function), because $T$ doesn't get the information about the sign of the input, and $P$ will simply put the sign back in after whatever output $T$ gives. Other point: "Your ??? is called an oracle." I don't think it should be called that. My $T$ is not a black box. It's a Turing machine. $\endgroup$ – user56834 May 2 at 21:02
  • $\begingroup$ "Also, your mathematical way doesn't seem to match the above." I think it does, though the notation is a bit bad. $P$ is an incompletely specified program, because what it computes depends on what $T$ we put into it. So essentially, $P$ is not a program but a program-parameterized family of programs. $P_T$ is a program for any turing machine $T$, or equivalently, Turing computable function $c$, so $P$ takes a computable function $c$ and gives a computable function $P_c$. The question is, what is the set of functions $P_c$ we get by varying $c$? i.e. what's the image of $P$. $\endgroup$ – user56834 May 2 at 21:07
  • $\begingroup$ Thanks for your replies. I'm still confused. So $P$ is fixed, but the subroutine $T$ is free to vary? I don't know whether "in some fixed way" is intended to restrict $T$ somehow. Do you mean that $T$ can be any algorithm at all? Or are there constraints on $T$? If so, what are the constraints? $\endgroup$ – D.W. May 2 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.