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!

  • 1
    $\begingroup$ Why are you trying to prove this? It reminds me of Banach-Mazur computability, which is not very well behaved. $\endgroup$ Commented Dec 8, 2012 at 14:52
  • $\begingroup$ @AndrejBauer Homework assignment! $\endgroup$
    – Jernej
    Commented Dec 8, 2012 at 14:57

1 Answer 1


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

  • 1
    $\begingroup$ Clearly $d(x',y') \leq \frac{1}{2^K}$ but I still miss how to show that $f^{-1}(L)$ is recursive! $\endgroup$
    – Jernej
    Commented Dec 9, 2012 at 10:17
  • $\begingroup$ @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$? $\endgroup$
    – usul
    Commented Dec 9, 2012 at 17:03
  • $\begingroup$ @Jernej I have posted my solution now. I hope what I posted earlier was helpful! Thanks for posting this problem, it is very cool. $\endgroup$
    – usul
    Commented Dec 11, 2012 at 5:52
  • $\begingroup$ 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! $\endgroup$
    – Jernej
    Commented Dec 11, 2012 at 8:51
  • $\begingroup$ 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? $\endgroup$
    – Jernej
    Commented Dec 11, 2012 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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