A metric space on Turing machines

Question

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.

Answer 1

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.