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$
4
$\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.

$\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$ – orgesleka Jul 31 '16 at 16:37
  • $\begingroup$ You were right, that maybe the metric defined is too trivial to give something useful. $\endgroup$ – orgesleka 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$ – orgesleka 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

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