2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ How does your machine $M_x$ decide if $x \in L$ or not? $\endgroup$ – orgesleka Aug 1 '16 at 15:19
  • $\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$ – orgesleka 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

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