Bahasa total yang hanya dapat diterjemahkan oleh bahasa Turing yang lengkap

Bahasa apa pun yang tidak lengkap Turing tidak dapat menulis penerjemah untuk itu sendiri. Saya tidak tahu di mana saya membaca itu tetapi saya telah melihatnya digunakan beberapa kali. Sepertinya ini memunculkan semacam bahasa "Turing" non-Turing lengkap; satu-satunya yang hanya bisaditafsirkan oleh mesin Turing. Bahasa-bahasa ini tidak harus mampu menghitung semua fungsi total dari naturals ke naturals juga tidak harus isomorfik (yang mungkin merupakan bahasa pamungkas A dan B ada sedemikian rupa sehingga ada fungsi F yang A dapat dihitung tetapi B tidak dapat). Agda dapat menafsirkan sistem Godel T dan Agda bersifat total sehingga bahasa utama semacam itu harus benar-benar lebih kuat sehingga sistem Godel T akan terlihat. Tampaknya bagi saya bahwa bahasa seperti itu setidaknya akan sekuat agda juga (meskipun saya tidak punya bukti, hanya firasat).

Apakah ada penelitian yang dilakukan dalam bidang ini? Apa hasil yang diketahui (yaitu bahasa "akhir" yang dikenal)?

Bonus: Saya khawatir ada kasus patologis yang tidak dapat menghitung fungsi yang Godel's System T masih bisa hanya dapat ditafsirkan oleh mesin Turing karena memungkinkan beberapa fungsi yang sangat aneh untuk dihitung. Apakah ini masalahnya atau dapatkah kita tahu bahwa bahasa seperti itu akan dapat menghitung apa pun yang dapat dihitung oleh Sistem T Godel?

Ini adalah pertanyaan yang diutarakan dengan buruk, jadi mari kita pertama-tama memahaminya. Saya akan melakukannya dengan gaya teori komputabilitas. Jadi saya akan menggunakan angka alih-alih string: sepotong kode sumber adalah angka, bukan serangkaian simbol. Tidak masalah, Anda dapat mengganti dengan s t r i n $\mathbb{N}$$\mathtt{string}$ seluruh bawah.

Mari $\langle m, n\rangle$ menjadi fungsi pasangan .

Katakanlah bahasa pemrograman $L = (P, ev)$ diberikan oleh data berikut:

1. satu set yang dapat ditentukan $P \subseteq \mathbb{N}$ dari "program yang sah", dan
2. sebuah komputasi dan parsial fungsi $ev : P \times \mathbb{N} \to \mathbb{N}$ .

Fakta bahwa adalah decidable berarti ada total peta yang dapat dihitung v a l i d : N → { 0 , 1 } sedemikian rupa sehingga v a l i d ( n $P$$valid : \mathbb{N} \to \{0,1\}$ . Secara informal, kami mengatakan bahwa adalah mungkin untuk mengetahui apakah string yang diberikan adalah bagian kode yang valid. Fungsi e v sangat penting sebagai juru bahasa kita: e v ( m , n ) menjalankan kode m pada input$valid(n) = 1 \iff n \in P$$ev$$ev(m,n)$$m$$n$ - hasilnya mungkin tidak ditentukan.

Kami sekarang dapat memperkenalkan beberapa terminologi:

1. Bahasa adalah total jika adalah fungsi total untuk semua m ∈ $n \mapsto ev(m,n)$$m \in P$ .
2. Sebuah bahasa menafsirkan bahasa L 2 = ( P 2 , e v 2 ) jika ada u ∈ P 1 sehingga e v 1 ( u , ⟨ n , m ⟩ ) ≃ e v 2 ( n , m ) untuk semua n ∈ $L_1 = (P_1, ev_1)$ $L_2 = (P_2, ev_2)$$u \in P_1$$ev_1(u, \langle n, m \rangle) \simeq ev_2(n, m)$$n \in P$dan . Di sini u adalah simulator untuk L 2 diimplementasikan di L 1 . Ia juga dikenal sebagai program universal untuk L 2 .$m \in \mathbb{N}$$u$$L_2$$L_1$$L_2$

Definisi lain dari " interprets L 2 " dimungkinkan, tetapi saya tidak akan membahasnya sekarang.$L_1$$L_2$

Kami mengatakan bahwa dan L 2 adalah setara jika mereka menginterpretasikan satu sama lain.$L_1$$L_2$

Ada "bahasa yang paling kuat" dari mesin Turing (yang Anda sebut sebagai "mesin Turing") di mana n ∈ N adalah penyandian mesin Turing dan φ ( n , m ) adalah fungsi komputasi sebagian yang "menjalankan mesin Turing yang dikodekan oleh n pada input m ". Bahasa ini dapat memadukan semua bahasa lain, jelas karena kami membutuhkan e $T = (\mathbb{N}, \varphi)$$n \in \mathbb{N}$$\varphi(n,m)$$n$$m$$ev$ menjadi dihitung.

Definisi bahasa pemrograman kami sangat santai. Agar hal-hal berikut dapat dilalui, mari kita membutuhkan tiga kondisi lagi:

• mengimplementasikan fungsi penerus: ada s u c c ∈ P sedemikian sehingga e v ( s u c c , m ) = m + 1 untuk semua m ∈ $L$$succ \in P$$ev(succ,m) = m+1$$m \in \mathbb{N}$ ,
• mengimplementasikan fungsi diagonal: ada d i a g ∈ P sehingga e v ( d i a g , m ) = ⟨ m , m ⟩ untuk semua m ∈ $L$$diag \in P$$ev(diag,m) = \langle m, m \rangle$$m \in \mathbb{N}$ ,
• ditutup di bawah komposisi fungsi: jika L mengimplementasikan f dan g maka ia juga mengimplementasikan f ∘ g ,$L$$L$$f$$g$$f \circ g$

Hasil klasiknya adalah ini:

Teorema: Jika suatu bahasa dapat menafsirkan dirinya sendiri maka itu tidak total.

Bukti. Misalkan adalah program universal untuk total langauge L diimplementasikan dalam L , yaitu, untuk semua m ∈ P dan n ∈ N , e v ( u , ⟨ m , n ⟩ ) ≃ e v ( m , n ) . Sebagai penerus, diagonal, dan e v ( u , - ) diimplementasikan dalam L , demikian juga komposisi mereka e $u$$L$$L$$m \in P$$n \in \mathbb{N}$

$$ev(u, \langle m, n \rangle) \simeq ev(m, n).$$ $ev(u, {-})$$L$ . Ada ada n 0 ∈ P sehingga e v ( n 0 , k ) ≃ e v ( u , ⟨ k , k ⟩ ) + 1 , tapi kemudian e v ( u , ⟨ n 0 , n 0 ⟩ ) ≃ e v $k \mapsto ev(u, \langle k, k \rangle) + 1$$n_0 \in P$$ev(n_0, k) \simeq ev(u, \langle k, k \rangle) + 1$ Karena tidak ada nomor sama penggantinya sendiri, berikut bahwa L tidak total atau bahwa L tidak menafsirkan sendiri. QED. $$ev(u, \langle n_0, n_0\rangle) \simeq ev(n_0, n_0) \simeq ev(u, \langle n_0, n_0 \rangle) + 1$$ $L$$L$

Perhatikan bahwa kami dapat mengganti peta pengganti dengan peta bebas-fixpoint lainnya.

Berikut adalah teorema kecil yang saya pikir akan membersihkan kesalahpahaman.

Teorema: Setiap bahasa total dapat ditafsirkan oleh bahasa total lainnya.

Bukti. Biarkan menjadi bahasa total. Kami mendapatkan total L ' yang menafsirkan L oleh sebelahnya untuk L nya evaluator e v . Lebih tepatnya, mari P ' = { ⟨ 0 , n ⟩ | n ∈ P } ∪ { ⟨ 1 , 0 ⟩ } dan mendefinisikan e v ' sebagai e v ' ( ⟨ b , n ⟩ , $L$$L'$$L$$L$$ev$$P' = \{\langle 0, n\rangle \mid n \in P\} \cup \{\langle 1, 0\rangle\}$$ev'$ Jelas, L ' total karenaLtotal. Untuk melihat bahwa L ' dapat mensimulasikanLhanya mengambilu=⟨1,

$$ev'(\langle b, n \rangle, m) = \begin{cases} ev(n,m) & \text{if $b = 0$},\\ ev(m_0, m_1) & \text{if $b = 1$ and $m = \langle m_0, m_1 \rangle$} \end{cases}$$ $L'$$L$$L'$$L$ , sejak itu $u = \langle 1, 0\rangle$$ev'(u, \langle m, n\rangle) \simeq ev(m, n)$ , seperti yang diperlukan. QED.

$L'$$L'$$L$ melakukannya.

$L$$L'$$L'$$L$$L$$L$ tidak menafsirkan sendiri.

Bahasa apa pun yang tidak lengkap Turing tidak dapat menulis penerjemah untuk itu sendiri.

Pernyataan ini salah. Pertimbangkan bahasa pemrograman di mana semantik setiap string adalah "Abaikan masukan Anda dan segera hentikan". Bahasa pemrograman ini tidak lengkap, tetapi setiap program adalah juru bahasa.