[Solved]: An interesting metric space related to Turing machines

Problem Detail: 

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!

Asked By : Jernej

Answered By : usul

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7253

 Ask a Question

 Download Related Notes/Documents