Un espacio métrico interesante relacionado con las máquinas de Turing.

En esta pregunta solo consideramos las máquinas de Turing que detienen todas las entradas. Si entonces por denotamos la máquina de Turing cuyo código es .$k \in \mathbb{N}$$T_k$$k$

Considere la siguiente función

En otras palabras, es el código de la máquina Turing más pequeña que reconoce con precisión una de las cadenas x, y. Ahora podemos definir el siguiente mapa$s(x,y)$$x,y.$

Se puede verificar rápidamente que $d(x,y)$ induce un espacio métrico (de hecho, una ultrametría) en $\Sigma^{*}.$

Ahora me gustaría probar que si $f:\Sigma^{*} \mapsto \Sigma^{*}$ es una función uniformemente continua , entonces, para cada lenguaje recursivo L, $f^{-1}(L)$ es recursivo.

En otras palabras, dejemos que $f$ sea ​​un mapa tal que para cada $\epsilon > 0$ haya un $\delta > 0$ tal que si para las cadenas $x,y \in \Sigma^{*}$

Ahora, como ya se señaló en esta publicación, una forma de abordar el problema es mostrar que hay una máquina de Turing que da una cadena $x \in \Sigma^{*}$ calcula $f(x).$

Estoy atrapado probando esta afirmación y lentamente preguntándome si hay algún otro enfoque para resolver esto.

¡Sugerencias, sugerencias y soluciones son bienvenidas!

Editar: eliminé sugerencias, publiqué mi solución.

Aquí está mi solución. Vamos a elegir un punto de referencia donde y considerar el universo desde los puntos de vista de y . Resulta que cada "vecindad" de un punto corresponde a un lenguaje recursivo. Entonces es un vecindario alrededor de , y habrá algún vecindario alrededor de que se le asigne; Este barrio es un lenguaje recursivo.x f ( x ) ∈ L x f ( x ) L f ( x ) $x$$f(x) \in L$$x$$f(x)$$L$$f(x)$$x$

Lema En este espacio, un lenguaje es recursivo si y solo si es un vecindario de cada una de sus cadenas.

Prueba . En primer lugar, fijar un lenguaje recursivo y dejar que . Deje que sea ​​el índice mínimo de un decisor paraL x ∈ L K L y ∉ L s ( x , Y ) ≤ K d ( x , y ) ≥ 1 / 2 K d ( x , y ) < 1 / 2 K y ∈ $L$$x \in L$$K$$L$ . Entonces tenemos que si , , por lo que . Por lo tanto implica que .$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$

Segundo, dejax ε > 0 K = ⌊ log ( 1 / ε ) ⌋ L K = { y : d ( x , y ) < ε } L K = { y : s ( x , y ) > K $x$ sea ​​una cadena arbitraria y arregle ; deje . Deje ; entonces . Entonces podemos escribir$\varepsilon > 0$$K = \lfloor \log(1/\varepsilon) \rfloor$$L_K = \{y : d(x,y) < \varepsilon\}$$L_K = \{y : s(x,y) > K\}$

Pero es decidible: en la entradaL K y K x y $L_K$$y$ , uno puede simular los primeros decisores en e y aceptar si y solo si cada uno aceptó ambos o rechazó ambos. $K$$x$$y$$~\square$

Ahora casi hemos terminado:

Prop. Let f L f - 1 ( L $f$ ser continuo. Si es recursivo, entonces es recursivo.$L$$f^{-1}(L)$

Prueba. Bajo una función continua, la preimagen de un barrio es un barrio.

Curiosamente, creo que en este espacio una función continua es uniformemente continua: Sea continuo, por lo que para cada punto , para cada existe una correspondiente f x $f$$x$$\varepsilon$ δ. Arregle uny deje que. Hay un número finito de bolas de tamaño: hay; entonces hay; luego, y así sucesivamente. asocia a cada uno de estos idiomas$\delta$ε K = ⌊ log ( 1 / ε ) ⌋ ε L ( T 1 ) ∪ L ( T 2 ) ⋯ ∪ L ( T K ) ¯ L ( T 1 ) ∪ L ( T 2 ) ⋯ ∪ L ( T K ) L ( T 1 ) ∪ ¯ L ( T 2$\varepsilon$$K = \lfloor \log(1/\varepsilon) \rfloor$$\varepsilon$$L(T_1) \cup L(T_2) \dots \cup L(T_K)$$\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$un lenguaje de preimagen con diámetro asociado . Para cada , . Entonces podemos tomar el mínimo sobre estos finitamente s para obtener la constante de continuidad uniforme asociada con este .$L_i^{\prime}$$\delta_i$$x \in L_i^{\prime}$$d(x,y) \leq \delta_i \implies d(f(x),f(y)) \leq \varepsilon$$\delta$$\delta$$\varepsilon$