# An interesting metric space related to Turing machines

In this question we only consider Turing machines that halt on all inputs. If $k \in \mathbb{N}$ then by $T_k$ we denote the Turing machine whose code is $k$.

Consider the following function

$$s(x,y) = \min\{k \mid |L(T_k) \cap \{x,y\}| = 1\}$$

In other words, $s(x,y)$ is the code of the smallest Turing machine that recognizes precisely one of the strings $x,y.$ We can now define the following map

$$d(x,y) = \left\{ \begin{array}{ll} 2^{-s(x,y)} & \mbox{if } x \ne y, \\ 0 & \mbox{otherwise.} \end{array} \right.$$

It can be quickly verified that $d(x,y)$ induces a metric space (in fact an ultrametrics) on $\Sigma^{*}.$

Now I would like to prove that if $f:\Sigma^{*} \mapsto \Sigma^{*}$ is a uniformly continuous function then for every recursive language L, $f^{-1}(L)$ is recursive as well.

In other words let $f$ be a map such that for every $\epsilon > 0$ there is a $\delta > 0$ such that if for strings $x,y \in \Sigma^{*}$ $$\quad d(x,y) \leq \delta$$ then $$d(f(x),f(y)) < \epsilon.$$ Then we need to show that $f^{-1}(L)$ is a recursive language given that $L$ is recursive.

Now as already noted in this post one way to approach the problem is to show that there is a Turing machine that given a string $x \in \Sigma^{*}$ computes $f(x).$

I am stuck proving this claim and slowly wondering if there is some other approach to solve this?

Hints, suggestions and solutions are welcome!

• Why are you trying to prove this? It reminds me of Banach-Mazur computability, which is not very well behaved. – Andrej Bauer Dec 8 '12 at 14:52
• @AndrejBauer Homework assignment! – Jernej Dec 8 '12 at 14:57

Edit: removed hints, posted my solution.

Here is my solution. We're going to pick a reference point $x$ where $f(x) \in L$ and consider the universe from $x$ and $f(x)$'s points of view. It turns out that every "neighborhood" of a point corresponds to a recursive language. So $L$ is a neighborhood around $f(x)$, and there will be some neighborhood around $x$ that maps to it; this neighborhood is a recursive language.

Lemma. In this space, a language is recursive if and only if it is a neighborhood of each of its strings.

Proof. First, fix a recursive language $L$ and let $x \in L$. Let $K$ be the minimal index of a decider for $L$. Then we have that if $y \not \in L$, $s(x,y) \leq K$, so $d(x,y) \geq 1/2^K$. Thus $d(x,y) < 1/2^K$ implies that $y \in L$.

Second, let $x$ be an arbitrary string and fix $\varepsilon > 0$; let $K = \lfloor \log(1/\varepsilon) \rfloor$. Let $L_K = \{y : d(x,y) < \varepsilon\}$; then $L_K = \{y : s(x,y) > K\}$. Then we can write

$$L_K = \{ y : (\forall j=1,\dots,K) |L(T_j) \cap \{x,y\}| \neq 1\}.$$

But $L_K$ is decidable: On input $y$, one may simulate the first $K$ deciders on $x$ and $y$ and accept if and only if each either accepted both or rejected both. $~\square$

Now we're almost done:

Prop. Let $f$ be continuous. If $L$ is recursive, then $f^{-1}(L)$ is recursive.

Proof. Under a continuous function, the preimage of a neighborhood is a neighborhood.

Interestingly, I think that in this space a continuous function is uniformly continuous: Let $f$ be continuous, so for each point $x$, for each $\varepsilon$ there exists a corresponding $\delta$. Fix an $\varepsilon$ and let $K = \lfloor \log(1/\varepsilon) \rfloor$. There are a finite number of balls of size $\varepsilon$: there is $L(T_1) \cup L(T_2) \dots \cup L(T_K)$; then there is $\overline{L(T_1)} \cup L(T_2) \dots \cup L(T_K)$; then $L(T_1) \cup \overline{L(T_2)} \dots \cup L(T_K)$, and so on. $f$ associates to each of these languages $L_i$ a preimage language $L_i^{\prime}$ with associated diameter $\delta_i$. For each $x \in L_i^{\prime}$, $d(x,y) \leq \delta_i \implies d(f(x),f(y)) \leq \varepsilon$. So we can take the minimum over these finitely many $\delta$s to get the uniform continuity constant $\delta$ associated with this $\varepsilon$.

• Clearly $d(x',y') \leq \frac{1}{2^K}$ but I still miss how to show that $f^{-1}(L)$ is recursive! – Jernej Dec 9 '12 at 10:17
• @Jernej OK, so first, we also have the contrapositive -- if $d(x^{\prime},y^{\prime}) > \frac{1}{2^K}$ then either both are in $L$ or neither is. Now let's take $\epsilon = \frac{1}{2^K}$. Then there is some $\delta$ so, if $d(x,y) \leq \delta$, then $\left| L \cap \{f(x),f(y)\} \right| = 1$. In particular, let's pick some $x$ with $x^{\prime} = f(x) \in L$. Now we want to know where all the other elements of $L$ lie relative to $x^{\prime}$, and therefore where must the other members of $f^{-1}(L)$ lie relative to $x$? – usul Dec 9 '12 at 17:03
• @Jernej I have posted my solution now. I hope what I posted earlier was helpful! Thanks for posting this problem, it is very cool. – usul Dec 11 '12 at 5:52
• Thank you very much for your answer. It took me a while to digest the hints hence I haven't upvoted and accepted your answer! – Jernej Dec 11 '12 at 8:51
• Quick question. We have shown that $L_K$ is decidable. I don't see how it follows that it is recursive? Cant it be that one of the simulated $T_j$ never halts? – Jernej Dec 11 '12 at 19:14