Are models of computation closed under composition?

Question

It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or concatenation, or the Kleene star. And those questions seem natural to me, because they're essentially questions about the power of a model of computation that can decide precisely the languages in $C$. However, it seems just as natural to me - perhaps even more natural - to ask whether such a class is also closed under composition.

Here's what I mean by that. If I fix some subset $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$ of "decidable" languages relative to some model of computation, for any (finite) $\Sigma$, then I have also fixed some subset $\mathcal{F} \subseteq B^A$ of computable functions, for any languages $A, B$ - because each function $f : A \rightarrow B$ can be viewed as a function $\bar{f} : A \times B \rightarrow \{0, 1\}$. Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well. Put in terms of the corresponding languages, I'd expect that if $L_f = \{(a, b) \in A \times B : f(a) = b\}$ and $L_g = \{(b, c) \in B \times C : g(b) = c\}$ are decidable, then $L_{g \circ f} = \{(a, c) : \exists b \in B s.t. f(a) = b \wedge g(b) = c\}$ should be decidable as well.

This seems to me like a natural question to ask of any class of languages. Is it in fact a reasonable question? If not, why? If it is, is there a better way to frame it, one that would make it more clear what we're demanding?

Answer 1

Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well.

Let's say our model is quadratic time computation. If $f$ is the function which maps a string of length $n$ to a string of $n^2$ zeroes, then $f$ is computable in our model, but $f\circ f$ is clearly not.

I'd expect that if $L_f = \{(a, b) \in A \times B : f(a) = b\}$ and $L_g = \{(b, c) \in B \times C : g(b) = c\}$ are decidable, then $L_{g \circ f} = \{(a, c) : \exists b \in B s.t. f(a) = b \wedge g(b) = c\}$ should be decidable as well.

This is a bit of a weird definition since $L_f$ can be much easier than $f$ (e.g., let $f(a)$ be the function that outputs a prime factorization of $a$). $F_l$ is poly-time while it is not known that $f$ is. Let's make $f$ also take an additional input $i$, and then let $f(a,i)$ output the number $i$ together with a factorization of $a$. If we then make $g$ output the $i$^th bit of the factorization we end up with $L_f$ and $L_g$ being poly-time computable but $L_{f\circ g}$ being as hard as factorization.