# 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 $$TT$$. This is a Turing machine, but with an additional feature: it can use some black box “oracle” as a subroutine.

3. A ??? machine $$TT$$. 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 $$PP$$.

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

• In the case of oracle machines $$TT$$, we can “plug” an oracle $$OO$$ into $$TT$$, and study what can be achieved by $$TT$$ given this oracle.

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

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

Some observations:

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

• ??? machines $$TT$$ with “parent” $$PP$$ can compute less than Turing machines, since they are constrained by being used by $$PP$$ in some way that the programmer of $$TT$$ cannot control. At two extremes: (1), $$PP$$ may simply ignore $$TT$$, in which case there is only a single unique “$$PP$$-computable” function, namely whichever $$PP$$ computes. (2) $$PP$$ may literally copy its input into $$TT$$, and output the output of $$TT$$, in which case every Turing-computable function is also “$$PP$$-computable”. In between these extremes, $$PP$$ may use $$TT$$ 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\mathcal C$$ of “computable functions” (e.g. Turing-computable), and we have a “parent function”, $$P:C→CP:\mathcal C\to \mathcal C$$, which gives a family of function-parameterized functions $$PcP_c$$. $$PP$$ takes a computable function $$cc$$ (the function that is computed by the turing machine $$TT$$ in our earlier formulation), and outputs a computable function $$PcP_c$$ (the function that is computed by giving $$PP$$ the machines $$TT$$ as its subroutine). The question now is: What is the image of $$PP$$? These are the $$PP$$-computable functions.

Is there a theory about something like this?

## Answer

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