Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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!

share|improve this question
1  
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
add comment

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
1  
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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