Un espace métrique intéressant lié aux machines de Turing

Dans cette question, nous considérons uniquement les machines Turing qui s'arrêtent sur toutes les entrées. Si $k \in \mathbb{N}$ alors par $T_k$ on désigne la machine de Turing dont le code est $k$ .

Considérez la fonction suivante

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

En d'autres termes, est le code de la plus petite machine de Turing qui reconnaît précisément l'une des chaînes x , y . Nous pouvons maintenant définir la carte suivante$s(x,y)$$x,y.$

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

On peut rapidement vérifier que induit un espace métrique (en fait un ultramétrique) sur Σ ∗$d(x,y)$$\Sigma^{*}.$

Je voudrais maintenant prouver que si est une fonction uniformément continue , alors pour chaque langage récursif L, f - 1 ( L ) est récursif également.$f:\Sigma^{*} \mapsto \Sigma^{*}$$f^{-1}(L)$

En d'autres termes, soit une carte telle que pour chaque ϵ > 0 il y a un δ > 0 tel que si pour les chaînes x , y ∈ Σ $f$$\epsilon > 0$$\delta > 0$$x,y \in \Sigma^{*}$ puis d ( f ( x ) , f ( y ) ) < ϵ . Ensuite, nous devons montrer que f - 1 ( L ) est un langage récursif étant donné que L est récursif.

$$\quad d(x,y) \leq \delta$$ $$d(f(x),f(y)) < \epsilon.$$ $f^{-1}(L)$$L$

Maintenant, comme déjà noté dans ce post, une façon d'aborder le problème est de montrer qu'il existe une machine de Turing qui, étant donné une chaîne calcule f ( x ) $x \in \Sigma^{*}$$f(x).$

Je suis coincé à prouver cette affirmation et je me demande lentement s'il existe une autre approche pour résoudre ce problème?

Les astuces, suggestions et solutions sont les bienvenues!

Edit: suppression des indices, publication de ma solution.

Voici ma solution. Nous allons choisir un point de référence où f ( x ) ∈ L et considérer l'univers des points de vue de x et f ( x ) . Il s'avère que chaque «voisinage» d'un point correspond à un langage récursif. Donc L est un voisinage autour de f ( x ) , et il y aura un voisinage autour de x qui lui correspond; ce quartier est un langage récursif.$x$$f(x) \in L$$x$$f(x)$$L$$f(x)$$x$

Lemme. Dans cet espace, un langage est récursif si et seulement s'il est voisin de chacune de ses chaînes.

Preuve . Tout d' abord, fixer un langage récursif et laisser x ∈ L . Laissez K soit l'indice minimal d'un decider pour L . Ensuite , nous avons que si y ∉ L , s ( x , y ) ≤ K , donc d ( x , y ) ≥ une / deux K . Ainsi , d ( x , y ) < une / deux K implique que y $L$$x \in L$$K$$L$$y \not \in L$$s(x,y) \leq K$$d(x,y) \geq 1/2^K$$d(x,y) < 1/2^K$ .$y \in L$

Deuxièmement, soit une chaîne arbitraire et fixons ε > 0 ; soit K = ⌊ log ( 1 / ε ) ⌋ . Soit L K = { y : d ( x , y ) < ε } ; alors L K$x$$\varepsilon > 0$$K = \lfloor \log(1/\varepsilon) \rfloor$$L_K = \{y : d(x,y) < \varepsilon\}$ . Ensuite, nous pouvons écrire$L_K = \{y : s(x,y) > K\}$

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

Mais est décidable: sur l'entrée y , on peut simuler le premier$L_K$$y$ décideurs sur x et y et accepter si et seulement si chacun a accepté les deux ou rejeté les deux. $K$$x$$y$$~\square$

Maintenant, nous avons presque terminé:

Prop. Soit $f$ continu. Si est récursif, alors f - 1 ( L ) est récursif.$L$$f^{-1}(L)$

Preuve. Sous une fonction continue, la pré-image d'un quartier est un quartier.

---

Fait intéressant, je pense que dans cet espace une fonction continue est uniformément continue: Soit continue, donc pour chaque point x , pour chaque ε il existe un δ correspondant . Fixer un ε et laisser K = ⌊ log ( 1 / ε ) ⌋ . Il y a un nombre fini de boules de taille ε : il y a L ( T 1 ) ∪ L ( $f$$x$$\varepsilon$$\delta$$\varepsilon$$K = \lfloor \log(1/\varepsilon) \rfloor$$\varepsilon$ ; ensuite il y a$L(T_1) \cup L(T_2) \dots \cup L(T_K)$; alorsL(T1)∪ ¯ L ( T 2 ) ⋯∪L(TK), et ainsi de suite. fassocie à chacune de ces languesLiune langue de pré-imageL ' i de diamètre associéδi. Pour chaque$\overline{L(T_1)} \cup L(T_2) \dots \cup L(T_K)$$L(T_1) \cup \overline{L(T_2)} \dots \cup L(T_K)$$f$$L_i$$L_i^{\prime}$$\delta_i$ , d ( x , y ) ≤ δ $x \in L_i^{\prime}$ . Nous pouvons donc prendre le minimum sur ces nombre fini de δ s pour obtenir la constante de continuité uniforme δ associée à ce ε .$d(x,y) \leq \delta_i \implies d(f(x),f(y)) \leq \varepsilon$$\delta$$\delta$$\varepsilon$