0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Tom van der Zanden Sep 21 at 11:33
  • $\begingroup$ 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". $\endgroup$ – Billy Smith Sep 21 at 11:36
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As regards the first part - yeah, there are definitely models of computation that wouldn't be closed under composition in this manner. That's perfectly fine - I'm interested in talking about it as a property, I never thought that every single model of computation would have it. I might say informally that every reasonable model of computation would have it, and dismiss quadratic-time computation as "unreasonable" - in favor of perhaps polynomial-time computation. $\endgroup$ – Billy Smith Sep 21 at 11:58
  • $\begingroup$ For your second paragraph... yeah, I guess the conflation between deciding languages and computing the equivalent function only makes any sense if we're talking about computability and not complexity. We need to be talking about the class of languages decided by some kind of computer (maybe a DFA or Turing machine or something) and not a resource-bounded class for this conflation to be reasonable. So I guess my question should be viewed as a question about computability. $\endgroup$ – Billy Smith Sep 21 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.