# Are models of computation closed under composition?

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?

• What do you mean by "decidable relative to some model of computation"? Does this mean membership in a particular complexity class, e.g. if our model of computation is P then "decidable" means "polynomial time solvable"? – Tom van der Zanden Sep 21 at 11:33
• I'm saying this in a very informal and vague sense, yeah. Maybe we're limiting ourselves to talking about languages decidable by a Turing machine, maybe languages decidable by a deterministic finite automaton, maybe languages decidable in polynomial time by a Turing machine - whatever. Maybe we're only talking about semidecidable languages (although in that case we'd probably not expect closure under composition, because I think that would imply closure under complement). I really just mean "I'm thinking of this class of languages as the languages decided by some kind of computer". – Billy Smith Sep 21 at 11:36

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.