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
