# Disprove unrealistic speed-up of total Turing machines

Let $$T_1$$ be a total Turing machine deciding language $$L_1$$, and let $$I_1$$ and $$I_2$$ be two separate inputs to $$T_1$$. Further, let $$I_{c}$$ be $$I_2$$ concatenated to $$I_1$$ with some separation symbol in between, and let $$S_{T}(I)$$ be the number of steps total TM $$T$$ needs to run until it accepts/rejects input $$I$$. I am wondering about the following two statements:

For every $$T_1$$ there exists another total Turing machine $$T_2$$ such that for all valid inputs $$I_1 \neq I_2$$ for $$T_1$$, $$T_2$$ accepts $$I_c$$ if $$T_1$$ accepts $$I_1$$ or if $$T_1$$ accepts $$I_2$$.

For every $$T_1$$, there exists a $$T_2$$ with the above property such that for all valid inputs $$I_1 \neq I_2$$, it holds that $$S_{T_2}(I_c) < S_{T_1}(I_1) + S_{T_1}(I_2)$$

To me, it seems as if the second statement would imply an impossible speed-up and should have an obvious counterexample, but I haven't been able to come up with one.

• While I don't have an example, I expect that there may be a language for which it's true: namely, we must compute some kind of certificate, which is used for accept/reject, and to compute certificate for $u$ we must compute certificates for all $v<u$. In result, in the process of answering the bigger question, we'll answer the smaller one. – Dmitry Aug 31 at 12:22
• @Dmitry I agree with you that a language where the above statement holds can probably be constructed. However, I am wondering if this statement holds for any decidable language (and if not, what is a counter example) – mtoller Aug 31 at 12:30
• Try some trivial languages. Language consisting of a single word should be a counterexample. – Dmitry Aug 31 at 12:40
• What is the source of the quoted text? From the way the first proposition is phrased it looks like $T_2$ is allowed to depend on $T_1$ as well as $I_1$ and $I_2$. Can you confirm if this is the case? – plop Aug 31 at 13:38
• What about the language $0^*$? The Turing machine complexity is $n+1$, and $|I_c|+1 = |I_1|+1+|I_2|+1$. – Yuval Filmus Sep 1 at 9:38

Suppose that the input alphabet is $$\{0,1\}$$, and consider the language $$L_1 = 0^*$$. We can easily construct a Turing machine $$T_1$$ such that $$S_{T_1}(I) = |I|+1$$. On the other hand, $$S_{T_2}(I_c) \geq |I_c|+1$$. Since $$|I_c|=|I_1|+1+|I_2|$$, we get $$S_{T_2}(I_c) \geq |I_1|+1+|I_2|+1 = S_{T_1}(I_1) + S_{T_1}(I_2).$$