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 $\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?

Answer

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