# A question on decidable formal languages and turing machines

Let $L' \subseteq L \subseteq \Sigma^*$ be decidable languages with deterministic Turing machines $M'$ and $M$ which decide the languages. Typically we have $t_M(w) \le t_{M'}(w)$ for all $w \in \Sigma^*$, where $t_M(w)$ is the time of $M$ on input $w$.

Suppose furthermore that $M$ and $M'$ have minimum length when interpreted on some chosen universal Turing machine $U$. So if $M''$ decides $L'$ then $l(M'')\ge l(M')$ where $l(M)$ is the length of $M$ when interpreted on $U$.

Is this just a coincidence of the chosen Turing machines, or does this property hold for all deciders of $L$ and $L'$ with minimum length?

"Typically" here means the following situation:

For instance if $L'$ is a decision problem on graphs and $L$ is the language of graphs (meaning that words correspond to adjacency matrix of a directed graph), then first for a word $w\in \Sigma^*$ one must decide if this word corresponds to an adjacency matrix of a graph, then decide if that graph has the property one is looking for. If you know a counterexample to that, that would also answer the question.

• Why do we have that "typically"? If you don't provide more information about the TMs the runtime can be chosen almost arbitrarily. – adrianN Aug 5 '16 at 12:35
• So you choose M' and M to be (one of) the fastest deciders for their language? – adrianN Aug 5 '16 at 13:22
• No, the shortest. – orgesleka Aug 5 '16 at 13:24
• Then how do you know that M doesn't do extra work? Maybe the shortest machine for L is terribly slow compared to the shortest machine for L'. – adrianN Aug 5 '16 at 13:28
• It is still not true that smaller languages need more time, see my answer. – adrianN Aug 5 '16 at 13:32

## 2 Answers

We can make the relationship between $t_M$ and $t_{M^\prime}$ quite arbitrary. For example, consider $L$ the language of strings that encode a prime number, and $L^\prime$ the language of strings that encode either a prime number, or a satisfiable formula. Then $t_M<t_{M^\prime}$ if P$\not=$NP. On the other hand, if we choose $L^\prime=\Sigma^{\star}$, then $t_{M^\prime}<t_{M}$.

A counterexample is choosing L' as the empty language. That can be decided faster than most other languages.