0
$\begingroup$

Let $L$ be a decidable language. Let $X^L$ be the set of deterministic Turing machines which decide $L$. Define two machines $A,B\in X^L$ to be time-equivalent if $t_A(w) = t_B(w)$ for all $w \in \Sigma^*$. Define a metric on the set of equivalence classes as folows: Let $R>0$ be some big number. $d(A,B) = \sup_{w\in \Sigma^*} | t_A(w) -t_B(w)|$ If this number is bigger than $R$, set $d(A,B) = R$. This defines a complete metric space on the set of equivalence classes of $X^L$. Let $f:X^L \rightarrow X^L$ be the function which to each equivalence class of dTM maps it to its "linear speedup-theorem"-Machine. Suppose that for each machine $M$ we have: $t_{f(M)}(w) = 1/2 t_M(w) + |w| + 2$. Then this map $f$ is a contraction. By the banach fix-point theorem there must exist an equivalence class $M$ such that $f(M) = M$ . But then $t_M(w) = t_{f(M)}(w) = 1/2 t_M(w) + |w| + 2$ and we get $t_M(w) = 2 |w| + 4$. However this seems very absurd. Does it contradict something known? The only assumption which I made is that we have equality instead of $\le$ in the linear speedup theorem.

$\endgroup$
3
$\begingroup$

The map $f$ is not a contraction. To see why, let's take for concreteness $R = 100$. Suppose $w$ is a word and $A,B$ are two machines such that $t_A(w) = 200$ and $t_B(w) = 400$. Then $d(A,B) = 100$. Now $t_{f(A)}(w) = 100 + |w| + 2$ and $t_{f(B)}(w) = 200 + |w| + 2$, so $|t_{f(A)}(w) - t_{f(B)}(w)| = 100$ and $d(f(A),f(B)) = 100$ also. But to have a contraction in the sense of the Banach fixed point theorem (also called a strict contraction) you need to have a constant $c < 1$ such that $d(f(A), f(B)) \le c d(A,B)$, so this can't be achieved.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer! If it was not about this $R$,then it would be a contraction. But without $R$ it is not a metric. $\endgroup$ – user35803 Jul 31 '16 at 16:37
  • $\begingroup$ You were right, that maybe the metric defined is too trivial to give something useful. $\endgroup$ – user35803 Jul 31 '16 at 16:39
  • 1
    $\begingroup$ Exactly. Also, note that your assumption of equality in the linear speedup theorem can't be possible, since by iterating you would have machines running in non-integer time. $\endgroup$ – Nate Eldredge Jul 31 '16 at 16:39
  • 1
    $\begingroup$ You probably can get a metric by taking $d(A,B)=\sup_{w\in\Sigma^*}\frac{|t_A(w)-t_B(w)|}{b(|w|)}$ where $b$ is the busy beaver function which "can be shown to grow faster asymptotically than does any computable function" according to Wikipedia. $\endgroup$ – xavierm02 Jul 31 '16 at 16:45
  • $\begingroup$ You mean that for every machine A,B we have $d(A,B) < \infty$? $\endgroup$ – user35803 Jul 31 '16 at 16:49

Your Answer

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