I am trying to understand the linear speedup theorem:

Let $L$ be a decidable language. Let $X^L$ be the set of all deterministic Turing machines which decide $L$. For a word $x \in \Sigma^*$ define: $t^L(x) := \min_{M \in X^L} t_M(x)$ where $t_M(x)$ is the time of $M$ on input $x$. Now let's choose some machine $M$ which satisfies $t^L(x) = t_M(x)$. Then for all $A \in X^L$ we have:

$$t_M(x) \le t_A(x)\,.\qquad(**)$$

Now let's apply the linear speedup theorem for the machine $M$: We get a new machine $N$ such that:

$$t_N(x) \le t_M(x)/2 + |x| + 2\,.$$

But by (**) we have: $t_M(x) \le t_N(x)$ hence it follows, that $t_M(x) \le t_N(x) \le t_M(x)/2 + |x| + 2$. From this it follows that $t_M(x) \le 2 |x| + 4$.

But how can this be? It means that, for every word $x \in \Sigma^*$ there exists a deterministic Turing machine $M$ which decides $L$ such that the time of $M$ on input $x$ is at most $2|x| + 4$.

This seems very absurd. What am I doing wrong?


I didn't check your working but your conclusion isn't at all absurd. For every Turing machine that decides $L$, and for every $x\in\Sigma^*$, there is another Turing machine $M_x$ that decides $L$ and that runs for exactly $|x|+1$ steps on input $x$. Note that this is more than twice as fast as your conclusion of $2|x|+4$. This also means that, for all languages $L$ and all strings $x\in\Sigma^*$, $t^L(x)=|x|+1$.

$M_x$ operates as follows. First, it reads the first $|x|+1$ characters of the input. If these are the string $x$ followed by a blank, it accepts if $x\in L$ and rejects if $x\notin L$; if they are not $x$ plus a blank, it returns to the left-hand end of the tape and does whatever $M$ would do. Note that $M_x$ does not need to contain any algorithm to decide whether $x\in L$. If $x\in L$, the machine is programmed "If my input is $x$, accept it; otherwise, rewind and do what $M$ would do.", and if $x\notin L$, the machine is programmed "If my input is $x$, reject it; otherwise, rewind and do what $M$ would do."

| cite | improve this answer | |
  • $\begingroup$ How does your machine $M_x$ decide if $x \in L$ or not? $\endgroup$ – user41014 Aug 1 '16 at 15:19
  • 1
    $\begingroup$ @stackExchangeUser It doesn't need to. Either $x\in L$ or $x\notin L$. In the first case, the machine transitions to an accepting state after reading $x$ plus blank; in the second case, it transitions to an accepting state. It does to whatever state I told it to when I designed the machine. Remember that even a DFA can decide whether to reject or accept a single, fixed string. $\endgroup$ – David Richerby Aug 1 '16 at 15:22
  • $\begingroup$ Ok, I understand, so you basically build the machine $M_x$ around the word $x$. If $x\in L$ then your machine also accepts otherwise not. $\endgroup$ – user41014 Aug 1 '16 at 15:25
  • $\begingroup$ @stackExchangeUser Exactly. $\endgroup$ – David Richerby Aug 1 '16 at 15:26
  • $\begingroup$ @stackExchangeUser It only needs to return to the left if the input is not $x$. So, for input $x$ it takes $|x|+1$ steps and, for any input $w\neq x$, it takes $2\tau+2+t_M(x)$, where $\tau = \min \{|x|,|w|\}$. (Because, if $|w|<|x|$, it only needs to read $|w|+1$ characters to know that $w\neq x$.) $\endgroup$ – David Richerby Aug 1 '16 at 15:38

Your Answer

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