3
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – user114966
    Aug 31, 2020 at 12:22
  • $\begingroup$ @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) $\endgroup$
    – mto_19
    Aug 31, 2020 at 12:30
  • $\begingroup$ Try some trivial languages. Language consisting of a single word should be a counterexample. $\endgroup$
    – user114966
    Aug 31, 2020 at 12:40
  • 1
    $\begingroup$ 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? $\endgroup$
    – plop
    Aug 31, 2020 at 13:38
  • 1
    $\begingroup$ What about the language $0^*$? The Turing machine complexity is $n+1$, and $|I_c|+1 = |I_1|+1+|I_2|+1$. $\endgroup$
    – Yuval Filmus
    Sep 1, 2020 at 9:38

1 Answer 1

Reset to default
3
$\begingroup$

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). $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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