We can make the following distinctions: (I will use the term “program” and “machine” as synonyms).
A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes an output, fully by itself.
An oracle machine T. This is a Turing machine, but with an additional feature: it can use some black box “oracle” as a subroutine.
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 C of “computable functions” (e.g. Turing-computable), and we have a “parent function”, P:C→C, which gives a family of function-parameterized functions Pc. 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 Pc (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?
Answer
Attribution
Source : Link , Question Author : user56834 , Answer Author : Community