Apakah ada bahasa yang dapat mengekspresikan kompiler Turing-nya sendiri?

Sebuah komentar di tex.SE membuatku bertanya-tanya. Pernyataan itu pada dasarnya:

Jika saya dapat menulis kompiler untuk bahasa X dalam bahasa X, maka X adalah Turing-complete.

Dalam istilah komputasi dan bahasa formal, ini adalah:

Jika memutuskan dan , maka . $M$ $L \subseteq L_{\mathrm{TM}}$ $\langle M \rangle \in L$ $F_L = \mathrm{RE}$

Berikut menunjukkan bahasa semua pengkodean mesin Turing dan menunjukkan set fungsi dihitung dengan mesin di . $L_{\mathrm{TM}}$ $F_L$ $L$

Apakah ini benar?

computability turing-completeness Raphael
sumber

tutup, pikirkan / setujui harus ada yang benar-benar dekat dengan ini seperti, bahasa "nontrivial" atau "cukup kompleks" yang dapat mengekspresikan simulator sendiri lengkap dengan TM. kompiler pada umumnya bukan bagian dari simulator. itu memang "pola desain" yang ditemukan di banyak bukti kelengkapan TM tapi mungkin belum digeneralisasikan / diformalkan. mungkin topik untuk analisis / diskusi lebih lanjut dalam Obrolan Ilmu Komputer . curiga / dugaan ada beberapa hal lain yang menarik seperti "setiap nontrivial / bahasa rekursif yang cukup kompleks dan rekursif dapat dipetakan / dikurangi menjadi satu sama lain".

vzn

Saya menciptakan bahasa esoterik yang disebut InterpretMe, yang tidak bisa melakukan apa - apa selain mengekspresikan itu sendiri juru bahasa, jadi tentu saja Turing tidak lengkap.

Ejaan Nonkontekstual

Bisakah Anda menjelaskan pernyataan kedua? Apa itu ? Bagaimana pernyataan ini terkait dengan yang pertama?

⟨ M ⟩

$\langle M \rangle$

reinierpost

@reinierpost biasanya menunjukkan jumlah , diberikan beberapa pengkodean (dapat diterima). Karenanya, . Oleh saya menunjukkan sekumpulan fungsi yang dihitung oleh bahasa dari mesin Turing.

⟨ M ⟩

$\langle M \rangle$

M

$M$

L_{T M} = {⟨ M ⟩ ∣ M is a Turing machine}

$L_{\mathrm{TM}} = \{ \langle M \rangle \mid M \text{ is a Turing machine}\}$

F_{L}

$F_L$

L

$L$

Raphael

Cara yang lebih baik untuk menyatakan klaim adalah: "Jika ada TM dengan dan , maka .

M

$M$

⟨ M ⟩ \in L

$\langle M \rangle \in L$

L_{M} = L

$L_M = L$

F_{L} = R E

$F_L = \mathrm{RE}$

Raphael

Jawaban:

Pernyataan informal tidak benar, seperti yang ditunjukkan oleh bahasa pemrograman berikut. Setiap string, katakanlah, karakter ASCII adalah program yang valid dan makna setiap program adalah, "Keluarkan program yang hanya mengeluarkan salinan inputnya." Dengan demikian, setiap program dalam bahasa ini adalah kompiler untuk bahasa tersebut tetapi bahasanya tidak lengkap Turing.

Saya tidak yakin apakah "versi teori komputabilitas" Anda setara tetapi juga tidak benar. Dengan teorema rekursi kedua Kleene , untuk setiap pengkodean mesin Turing, ada TM yang menerima pengkodeannya sendiri dan menolak yang lainnya. ¹ Mesin ini merupakan contoh berlawanan dengan proposisi. Lebih konkretnya, kita dapat mencapai hasilnya dengan memilih pengkodean. Misalnya, biarkan setiap kode angka ganjil yang didefinisikan oleh mesin "Jika input saya ganjil, terimalah; jika tidak, tolak" dan biarkan angka kode mesin yang dikodekan oleh dalam skema pengkodean favorit Anda sendiri untuk mesin Turing. dalam bahasa diterima oleh tetapi $M$ $2x$ $x$ $\langle M\rangle$ $L$ $M$ $F_L$ belum menyelesaikan Turing.

¹ Teorema rekursi kedua Kleene mengatakan bahwa, untuk enumerasi apa pun dari fungsi rekursif parsial (yaitu, untuk setiap pengkodean program sebagai bilangan bulat), dan fungsi rekursif parsial , ada integer sehingga adalah fungsi yang memetakan ke . Jadi, khususnya, misalkan adalah fungsi yang menerima jika dan menolak sebaliknya. Dengan teorema, ada bilangan bulat yang mengkode program . Artinya, menerima coding sendiri $(\phi_i)_{i\geq 0}$ $Q(x,y)$ $p$ $\phi_p$ $y$ $Q(p,y)$ $Q$ $x=y$ $p$ $\phi_p(y) = Q(p,y)$ $\phi_p$ $p$ dan menolak semua input lainnya.

David Richerby
sumber

Dalam hal apa setiap program dalam bahasa itu merupakan kompiler untuk bahasa itu? Setiap program adalah program yang memasukkan program dalam bahasa itu dan mengeluarkan program yang berbeda dalam bahasa itu, ya, tetapi quines umumnya tidak dianggap sebagai kompiler.

user253751

Saya pikir @immibis ada benarnya: kompiler Anda adalah sedangkan semua program dalam bahasa adalah , jadi jelas tidak dalam bahasa Apakah saya melewatkan sesuatu?

c

$c$

c (P) = {x \Rightarrow r e t u r n P}

$c(P) = \{ x \Rightarrow \mathtt{return}\ P \}$

P (x) = P

$P(x) = P$

c

$c$

Raphael

@immibis I (terlambat) berpikir Anda benar. Tampaknya apa yang saya maksudkan adalah semantik dari setiap program hanya "output input Anda". Itu sepertinya cukup dekat dengan apa yang saya tulis sehingga mungkin itu yang saya maksudkan. Atau mungkin saya sangat beruntung bahwa jarak edit dari jawaban yang salah ke jawaban yang benar sangat kecil. :-)

David Richerby

Jawabannya sekarang mengatakan "abaikan inputnya dan outputkan salinan inputnya" - Anda tidak bisa melakukan keduanya.

user253751

@immibis saya akan masuk lagi .

David Richerby