Um espaço métrico interessante relacionado às máquinas de Turing

Nesta questão, consideramos apenas máquinas de Turing que param em todas as entradas. Se , em , denotamos a máquina de Turing cujo código é .T k$k \in \mathbb{N}$$T_k$$k$

Considere a seguinte função

Em outras palavras, $s(x,y)$ é o código da menor máquina de Turing que reconhece precisamente uma das cadeias $x,y.$Agora podemos definir o seguinte mapa

Pode-se verificar rapidamente que $d(x,y)$ induz um espaço métrico (de fato um ultramétrico) em $\Sigma^{*}.$

Agora, eu gostaria de provar que se $f:\Sigma^{*} \mapsto \Sigma^{*}$ é uma função uniformemente contínua , então para toda linguagem recursiva L, $f^{-1}(L)$ é recursiva.

Em outras palavras, seja $f$ um mapa tal que, para todo $\epsilon > 0$ exista um $\delta > 0$ tal que, para as cadeias $x,y \in \Sigma^{*}$

Agora, como já observado neste post, uma maneira de abordar o problema é mostrar que existe uma máquina de Turing que fornece uma string $x \in \Sigma^{*}$ calcula $f(x).$

Estou preso a provar esta afirmação e lentamente me perguntando se existe alguma outra abordagem para resolver isso.

Dicas, sugestões e soluções são bem-vindas!

Editar: dicas removidas, postou minha solução.

Aqui está a minha solução. Nós estamos indo para escolher um ponto de referência , onde e considerar o universo de e 's pontos de vista. Acontece que toda "vizinhança" de um ponto corresponde a uma linguagem recursiva. Então é um bairro em torno de , e haverá algum bairro em torno de que mapeia para ele; esse bairro é uma linguagem recursiva.f ( x ) ∈ L x f ( x ) L f ( x ) $x$$f(x) \in L$$x$$f(x)$$L$$f(x)$$x$

Lema. Nesse espaço, uma linguagem é recursiva se e somente se for uma vizinhança de cada uma de suas seqüências.

Prova . Primeiro, fixar uma linguagem recursiva e deixe . Deixe- ser o índice mínimo de um decisor para . Em seguida, tem que se , , então . Assim implica que .x ∈ G K L y ∉ G s ( x , y ) ≤ K d ( x , y ) ≥ 1 / 2 K d ( x , y ) < 1 / 2 K 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$

Segundo, seja uma string arbitrária e corrija ; deixe . Seja ; então . Então nós podemos escreverε > 0 K = ⌊ log ( 1 / ε ) ⌋ L K = { y : d ( x , y ) < ε } L K = { y : s ( x , y ) > K $x$$\varepsilon > 0$$K = \lfloor \log(1/\varepsilon) \rfloor$$L_K = \{y : d(x,y) < \varepsilon\}$$L_K = \{y : s(x,y) > K\}$

Mas é decidível: Na entrada , pode-se simular os primeiros decisores em e e aceito se e somente se cada um quer aceito tanto ou rejeitado ambos. y K x y $L_K$$y$$K$$x$$y$$~\square$

Agora estamos quase terminando:

Prop. Seja contínuo. Se é recursivo, então é recursivo.L f - 1 ( L $f$$L$$f^{-1}(L)$

Prova. Sob uma função contínua, a pré-imagem de um bairro é um bairro.

Curiosamente, acho que nesse espaço uma função contínua é uniformemente contínua: Seja contínuo, portanto, para cada ponto , para cada existe um correspondente . Corrija um e deixe . Há um número finito de esferas de tamanho : existe ; então há ; então e assim por diante. associa a cada um desses idiomasx ε ô ε K = ⌊ log ( 1 / ε ) ⌋ ε G ( T 1 ) ∪ G ( T 2 ) ⋯ ∪ G ( T K ) ¯ G ( T 1 ) ∪ G ( T 2 ) ⋯ ∪ L ( T K ) G ( T 1 ) ∪ ¯ $f$$x$$\varepsilon$$\delta$$\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)$FGIL ' i δix∈G ' i d(x,y)≤δ$L(T_1) \cup \overline{L(T_2)} \dots \cup L(T_K)$$f$$L_i$uma linguagem de pré-imagem com diâmetro associado . Para cada , . Portanto, podemos assumir o mínimo desses infinitos para obter a constante de continuidade uniforme associada a esse .$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$