Ciekawa przestrzeń metryczna związana z maszynami Turinga

W tym pytaniu rozważamy tylko maszyny Turinga, które zatrzymują się na wszystkich wejściach. Jeśli to przez oznaczamy maszynę Turinga, której kod to$k \in \mathbb{N}$$T_k$$k$ .

Rozważ następującą funkcję

Innymi słowy, jest kodem najmniejszej maszyny Turinga, która rozpoznaje dokładnie jeden z ciągówMożemy teraz zdefiniować następującą mapę$s(x,y)$$x,y.$

Można szybko sprawdzić, czy $d(x,y)$ indukuje przestrzeń metryczną (w rzeczywistości ultrametryczną) na $\Sigma^{*}.$

Chciałbym teraz udowodnić, że jeśli $f:\Sigma^{*} \mapsto \Sigma^{*}$ jest funkcją jednorodnie ciągłą, to dla każdego rekurencyjnego języka L, $f^{-1}(L)$ jest rekurencyjny.

Innymi słowy, niech $f$ będzie mapą taką, że dla każdego $\epsilon > 0$ jest $\delta > 0$ taka, że ​​jeśli dla ciągów $x,y \in \Sigma^{*}$

Jak już wspomniano w tym poście, jednym ze sposobów rozwiązania problemu jest pokazanie, że istnieje maszyna Turinga, która podała ciąg $x \in \Sigma^{*}$ oblicza $f(x).$

Utknąłem w dowodzeniu tego twierdzenia i powoli zastanawiam się, czy istnieje jakieś inne podejście do rozwiązania tego problemu?

Wskazówki, sugestie i rozwiązania są mile widziane!

Edytuj: usunąłem podpowiedzi, opublikowałem moje rozwiązanie.

Oto moje rozwiązanie. Wybierzmy punkt odniesienia gdzie i rozważmy wszechświat z punktu widzenia i . Okazuje się, że każde „sąsiedztwo” punktu odpowiada językowi rekurencyjnemu. Więc to sąsiedztwo wokół , i będzie jakieś sąsiedztwo wokół które to odwzorowuje; ta okolica jest językiem rekurencyjnym.$x$$f(x) \in L$$x$$f(x)$$L$$f(x)$$x$

Lemat. W tej przestrzeni język jest rekurencyjny wtedy i tylko wtedy, gdy jest sąsiedztwem każdego z jego łańcuchów.

Dowód . Po pierwsze, ustalić rekurencyjne języka i niech . Niech będzie minimalny wskaźnik o decydującym dla . Następnie ma że jeśli , , aby . Zatem oznacza, że .$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$

Po drugie, niech będzie dowolnym ciągiem znaków i naprawi ; niech . Niech ; następnie . Potem możemy pisać$x$$\varepsilon > 0$$K = \lfloor \log(1/\varepsilon) \rfloor$$L_K = \{y : d(x,y) < \varepsilon\}$$L_K = \{y : s(x,y) > K\}$

Ale jest rozstrzygalne: na wejściu , można symulować pierwsze decydentów na i i przyjąć tylko wtedy, gdy każdy albo przyjęte lub odrzucone zarówno oba. $L_K$$y$$K$$x$$y$$~\square$

Teraz prawie skończyliśmy:

Prop. Niech będzie ciągły. Jeśli jest rekurencyjny, to jest rekurencyjny.$f$$L$$f^{-1}(L)$

Dowód. W ramach ciągłej funkcji preimage sąsiedztwa to sąsiedztwo.

Co ciekawe, myślę, że w tej przestrzeni funkcja ciągła jest jednolicie ciągła: Niech będzie ciągła, więc dla każdego punktu , dla każdego istnieje odpowiednia . Napraw plik i pozwól . Istnieje skończona liczba piłek wielkości : istnieje ; wtedy jest ; następnie i tak dalej. kojarzy się z każdym z tych języków$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)$$L(T_1) \cup \overline{L(T_2)} \dots \cup L(T_K)$$f$$L_i$język preimage z powiązaną średnicą . Dla każdego , . Możemy więc wziąć minimum tych skończonych wielu aby uzyskać jednolitą stałą ciągłości związaną z tym .$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$