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ę

s (x, y) = min {k ∣ | L (T_{k}) \cap {x, y} | = 1}

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

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.$

d (x, y) = {\begin{cases} 2^{- s (x, y)} & if x \neq y, \\ 0 & otherwise. \end{cases}

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

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^{*}$

d (x, y) \leq δ

$\quad d(x,y) \leq \delta$ a następnie

d (f (x), f (y)) < ϵ .

$d(f(x),f(y)) < \epsilon.$ Następnie musimy pokazać, że

f^{- 1} (L)

$f^{-1}(L)$ jest językiem rekurencyjnym, biorąc pod uwagę, że

L

$L$ jest rekurencyjny.

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!

computability turing-machines

— Jernej
źródło

Dlaczego próbujesz to udowodnić? Przypomina mi obliczalność Banacha-Mazura, która nie jest zbyt dobrze wychowana.

— Andrej Bauer,

@AndrejBauer Zadanie domowe!

— Jernej

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\}$

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

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

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$

— usul
źródło

Oczywiście ale wciąż brakuje mi sposobu pokazania, że jest rekurencyjny!

d (x^{'}, y^{'}) \leq \frac{1}{2^{K}}

$d(x',y') \leq \frac{1}{2^K}$

f^{- 1} (L)

$f^{-1}(L)$

— Jernej

@Jernej OK, więc po pierwsze mamy również przeciwieństwo - jeśli wówczas oba są w lub nie jest. Teraz weźmy . Potem jest trochę więc jeśli , to . W szczególności, niech wybrać kilka z . Teraz chcemy wiedzieć, gdzie wszystkie pozostałe elementy leżą względem , a zatem gdzie muszą pozostać inni członkowie względem ?

d (x^{'}, y^{'}) > \frac{1}{2^{K}}

$d(x^{\prime},y^{\prime}) > \frac{1}{2^K}$

L

$L$

ϵ = \frac{1}{2^{K}}

$\epsilon = \frac{1}{2^K}$

δ

$\delta$

d (x, y) \leq δ

$d(x,y) \leq \delta$

| L \cap {f (x), f (y)} | = 1

$\left| L \cap \{f(x),f(y)\} \right| = 1$

x

$x$

x^{'} = f (x) \in L

$x^{\prime} = f(x) \in L$

L

$L$

x^{'}

$x^{\prime}$

f^{- 1} (L)

$f^{-1}(L)$

x

$x$

— usul

@Jernej Zamieściłem teraz swoje rozwiązanie. Mam nadzieję, że to, co opublikowałem wcześniej, było pomocne! Dziękujemy za opublikowanie tego problemu, jest bardzo fajny.

— usul

Bardzo dziękuję za odpowiedź. Zajęło mi trochę czasu, aby przyswoić wskazówki, dlatego nie głosowałem i nie zaakceptowałem twojej odpowiedzi!

— Jernej

Szybkie pytanie. Wykazaliśmy, że jest rozstrzygalny. Nie rozumiem, jak to się dzieje, że jest rekurencyjne? Czy to możliwe, że jeden z symulowanych nigdy się nie zatrzymuje?

L_{K}

$L_K$

T_{j}

$T_j$

— Jernej