HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Disprove unrealistic speed-up of total Turing machines

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
totalunrealisticmachinesdisproveturingspeed

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#129710, answer score: 3

Revisions (0)

No revisions yet.