Theory for programs that are “embedded” in other programs?

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 C of “computable functions” (e.g. Turing-computable), and we have a “parent function”, P:CC, 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?


Source : Link , Question Author : user56834 , Answer Author : Community

Leave a Comment