Ruang metrik yang menarik terkait dengan mesin Turing

Dalam pertanyaan ini kami hanya mempertimbangkan mesin Turing yang berhenti pada semua input. Jika $k \in \mathbb{N}$ maka oleh kita menunjukkan mesin Turing yang kodenya adalah .$T_k$$k$

Pertimbangkan fungsi berikut

Dengan kata lain, adalah kode dari mesin Turing terkecil yang mengenali dengan tepat salah satu stringKita sekarang dapat mendefinisikan peta berikutx , y $s(x,y)$$x,y.$

Dapat dengan cepat diverifikasi bahwa menginduksi ruang metrik (sebenarnya ultrametrik) pada$d(x,y)$$\Sigma^{*}.$

Sekarang saya ingin membuktikan bahwa jika adalah fungsi kontinu yang seragam maka untuk setiap bahasa rekursif L, bersifat rekursif juga.$f:\Sigma^{*} \mapsto \Sigma^{*}$$f^{-1}(L)$

Dengan kata lain, biarkan menjadi peta sedemikian rupa sehingga untuk setiap ada sehingga jika untuk string lalu Maka kita perlu menunjukkan bahwa adalah bahasa rekursif mengingat adalah rekursif.$f$$\epsilon > 0$$\delta > 0$$x,y \in \Sigma^{*}$

Sekarang seperti yang sudah dicatat dalam posting ini salah satu cara untuk mendekati masalah adalah dengan menunjukkan bahwa ada mesin Turing yang diberi string menghitung f ( x ) $x \in \Sigma^{*}$$f(x).$

Saya terjebak untuk membuktikan klaim ini dan perlahan bertanya-tanya apakah ada pendekatan lain untuk menyelesaikan ini?

Petunjuk, saran dan solusi dipersilahkan!

Edit: menghapus petunjuk, memposting solusi saya.

Ini solusinya. Kita akan memilih titik referensi mana f ( x ) ∈ L dan mempertimbangkan alam semesta dari sudut pandang x dan f ( x ) . Ternyata setiap "lingkungan" suatu titik sesuai dengan bahasa rekursif. Jadi L adalah lingkungan di sekitar f ( x ) , dan akan ada beberapa lingkungan di sekitar x yang memetakannya; lingkungan ini adalah bahasa rekursif.$x$$f(x) \in L$$x$$f(x)$$L$$f(x)$$x$

Kata pengantar singkat. Dalam ruang ini, sebuah bahasa bersifat rekursif jika dan hanya jika merupakan lingkungan dari masing-masing string.

Bukti . Pertama, memperbaiki bahasa rekursif dan membiarkan x ∈ L . Mari K menjadi indeks minimal penentu untuk L . Lalu kami memiliki bahwa jika y ∉ L , s ( x , y ) ≤ K , sehingga d ( x , y ) ≥ 1 / 2 K . Dengan demikian d ( x , y ) < 1 / 2 K menyiratkan bahwa 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$

Kedua, misalkan menjadi string acak dan perbaiki ε > 0 ; misalkan K = ⌊ log ( 1 / ε ) ⌋ . Misalkan L K = { y : d ( x , y ) < ε } ; lalu L K = { y : s ( x , y ) > K } . Lalu kita bisa menulis$x$$\varepsilon > 0$$K = \lfloor \log(1/\varepsilon) \rfloor$$L_K = \{y : d(x,y) < \varepsilon\}$$L_K = \{y : s(x,y) > K\}$

Tapi adalah decidable: Pada masukan y , salah satu dapat mensimulasikan pertama K deciders pada x dan y dan menerima jika dan hanya jika setiap baik diterima baik atau ditolak keduanya. $L_K$$y$$K$$x$$y$$~\square$

Sekarang kita hampir selesai:

Prop. Biarkan menjadi kontinu. Jika L bersifat rekursif, maka f - 1 ( L ) bersifat rekursif.$f$$L$$f^{-1}(L)$

Bukti. Di bawah fungsi yang berkesinambungan, preimage lingkungan adalah lingkungan.

Menariknya, saya berpikir bahwa dalam ruang ini fungsi kontinu adalah kontinu seragam: Let kontinu, sehingga untuk setiap titik x , untuk setiap ε terdapat sesuai δ . Perbaiki ε dan biarkan K = ⌊ log ( 1 / ε ) ⌋ . Ada sejumlah bola ukuran terbatas ε : ada L ( T 1 ) ∪ L ( T 2 ) ⋯ ∪ L ( T K ) ; lalu ada$f$$x$$\varepsilon$$\delta$$\varepsilon$$K = \lfloor \log(1/\varepsilon) \rfloor$$\varepsilon$$L(T_1) \cup L(T_2) \dots \cup L(T_K)$; kemudianL(T1)∪ ¯ L ( T 2 ) ⋯∪L(TK), dan seterusnya. fmengaitkan ke masing-masing bahasa iniLibahasa preimageL ′ i dengan diameter terkaitδi. Untuk setiap$\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}$ . Jadi kita bisa mengambil minimal selama ini finitely banyak δ s untuk mendapatkan seragam kelangsungan konstan δ terkait dengan ini ε .$d(x,y) \leq \delta_i \implies d(f(x),f(y)) \leq \varepsilon$$\delta$$\delta$$\varepsilon$