Dapat mesin Turing memutuskan bahasa

Biarkan Apakah ada mesin Turing R yang memutuskan (maksud saya tidak mengenali) bahasa L ∅ ?

Tampaknya teknik yang sama digunakan untuk menunjukkan bahwa juga berfungsi di sini.$\{A \mid A \text{ is a DFA and } L(A)=\emptyset\}$

Dengan menandai, Anda mungkin berarti analisis keterjangkauan - mencari jalur dari kondisi awal ke kondisi penerimaan. Memang, bahasa DFA kosong jika tidak ada jalan seperti itu.

Mari kita mulai dengan contoh mengapa ini gagal dalam TM. Pertimbangkan TM itu, di , mengabaikan masukan itu, tetapi menulis sebuah rekaman itu, bergerak kepala kanan dan pergi ke negara q 1 , maka dalam q 1 lagi mengabaikan input, menulis sebuah , bergerak kepala kiri dan pergi ke q 2 . Di q 2 , jika berbunyi a , maka ia menulis a , menggerakkan kepala ke kanan dan kembali ke q 1 .$q_0$$a$$q_1$$q_1$$a$$q_2$$q_2$$a$$a$$q_1$

Artinya, mesin hanya menulis dan berganti-ganti antara dua status ( q 1 dan q 2 ) dan selalu memiliki dua huruf ' a ' yang berdekatan pada kaset.$a$$q_1$$q_2$$a$

Kami sekarang menambahkan transisi dari yang ketika membaca b pergi ke keadaan menerima dan berhenti.$q_2$$b$

Bahasa mesin ini kosong. Memang, proses selalu macet di loop , dan tidak akan pernah sampai ke status penerima. Namun, ada jalan negara menuju negara penerima. Jadi apa yang salah?$q_1-q_2$

Secara intuitif, "status" sebuah TM tidak cukup informatif untuk menggambarkan kelanjutan dari proses tersebut. Untuk mendapatkan semua informasi, Anda memerlukan konfigurasi TM, yang mencakup keadaan, posisi kepala, dan isi rekaman itu. Jika Anda menemukan jalur konfigurasi (yang disebut run ) ke konfigurasi penerima, maka memang bahasanya tidak kosong, dan itu adalah kondisi iff.

Masalah dengan menggunakan analisis reachability pada grafik konfigurasi, adalah mungkin tak terhingga. Inilah mengapa memutuskan kekosongan bahasa tidak dapat diputuskan.

Ini juga mengapa bahasa non-kekosongan dapat dikenali - Anda dapat melakukan BFS pada grafik konfigurasi tak terbatas. Jika ada jalan ke negara penerima, Anda akan menemukannya pada akhirnya. Namun, jika tidak ada, maka Anda mungkin terjebak dalam pencarian yang tidak terbatas.

tidak dapat dipastikan karenaTeorema Padi, yang menyatakan bahwa sifat non-sepele dari fungsi parsial tidak dapat ditentukan.$A$

1. Ada TM yang tidak menerima string apa pun. (Yang langsung menuju ke negara tolak).
2. Ada TM yang menerima setiap string. (Yang langsung menuju ke negara penerima).

Ini berarti bahwa fungsi-fungsi yang dikomputasi oleh elemen-elemen memiliki sifat non trivial. Oleh karena itu A tidak dapat diputuskan.$A$$A$

dapat ditentukan hanya dengan asumsi bahwa DFA dikodekan dengan cara khusus seperti tabel transisi negara atau lainnya. (Kami tidak dapat memutuskan apakah TM hanya menerima bahasa biasa, karena Teorema Rice!). Dalam hal ini Rice Teorema tidak berlaku karena pengkodean tertentu dari suatu unsur diperlukan untuk memutuskan E . Jadi kami tidak hanya memutuskan fungsi parsial.$E$$E$

(Artinya jika masalahnya adalah, memutuskan apakah TM tertentu adalah DFA - atau DFA yang dapat dihitung - dan bahasa yang diterima olehnya kosong, akan diputuskan melalui Teorema Rice. Perhatikan bahwa dalam hal ini A = E .)$E$$A = E$

Petunjuk lain: Coba kurangi masalah penghentian ke .$L_\emptyset$

(Petunjuk aslinya adalah menggunakan teorema Rice, tetapi dalam kasus ini bukti langsung juga cukup sederhana.)

Lemma 1 : Jika L tidak dapat ditentukan maka komplemen L.

Kita tahu bahwa masalah penghentian, $H_{TM}$ tidak dapat diputuskan. Oleh karena itu, menurut Lemma 1 komplemen dari masalah penghentian, $H_{TM}^c$ juga tidak dapat ditentukan.

$H_{TM}$ =$\{\langle M, x \rangle { }\mid \text{ M is a TM and M halts on input x } \}$

$H_{TM}^c$ =$\{\langle M, x \rangle { }\mid \text{ M is a TM and M loops on input x } \}$

$E_{TM}$ =$\{\langle M \rangle { }\mid \text{ M is a TM and L(M) = } \emptyset \}$

Asumsikan bahwa $E_{TM}$ dapat dipilih. Kami akan mengurangi $H_{TM}^c$ untuk $E_{TM}$ - dengan kata lain kita akan menunjukkan bagaimana untuk membangun Turing Machine $M_{H_{TM}^c}$ yang memutuskan $H_{TM}^c$ menggunakan TM, $M_{E_{TM}}$ yang memutuskan $E_{TM}$ . Ini memberi kita kontradiksi, karena kita tahu bahwa $H_{TM}^c$ tidak dapat diputuskan, dan karenanya $M_{H_{TM}^c}$tidak bisa ada Kata "mengurangi" berarti memecahkan masalah yang diberikan dengan mengubahnya menjadi masalah lain yang sudah kita ketahui untuk dipecahkan. Jadi, Mesin Turing untuk $H_{TM}^c$ dapat dibangun sebagai berikut:

$M_{H_{TM}^c}$ = “masukan$\langle M,x \rangle$

$\qquad$1. Buat kode untuk TM, $M_1$ yang melakukan hal berikut:

$\qquad$ $\quad$ $M_1$ = "pada input$w$

$\qquad$ $\quad$1. Simulasikan $M$ pada $x$ .

$\qquad$ $\quad$2. Terima jika $M$ berhenti. "

$\qquad$2. Jalankan $M_{E_{TM}}$ di $\langle M_1 \rangle$

$\qquad$3. Terima jika $M_{E_{TM}}$ menerima, tolak sebaliknya. "

Sangat penting untuk memahami bahwa TM $M_1$ tidak pernah benar-benar disimulasikan - simulasi semacam itu bisa menjadi loop tak terbatas. Yang kami lakukan hanyalah membuat kode untuk $M_1$ .

$M_1$ dibangun sehingga pada setiap masukan$w$ diberikan untuk itu, itu akan mensimulasikan$M$ dengan masukan$x$ . $M$ dapat menghentikan atau mengulang pada$x$ dan karenanya ada dua kasus:

$\quad$1. $M_1$ menerima semua input $w$ jika $M$ berhenti di $x$ . $M_{E_{TM}}$ akan menolak $M_1$ sebagai $L(M_1) \neq \emptyset$ .

$\quad$2. Jika $M$ loop pada $x$ , $M_1$ akan juga loop untuk setiap masukan $w$ diberikan untuk itu. Lagi pula, karena $M_{E_{TM}}$ adalah a$\quad$Penentu akan menolak dan berhenti pada input $M_1$ sebagai $L(M_1) = \emptyset$ .

$Correctness$ : Sejak$M_{E_{TM}}$ selalu perhentian (oleh asumsi kami),$M_{H_{TM}^c}$ juga selalu perhentian. $M_{H_{TM}^c}$ menerima jika$M_{E_{TM}}$ menerima, yaitu jika$L(M_1) = \emptyset$ yang terjadi jika$M$ loop pada$x$ .
$M_{H_{TM}^c}$ menolak jika$M_{E_{TM}}$ menolak yaitu$L(M_1) \neq \emptyset$ yang terjadi jika$M$ berhenti pada$x$ . Dengan demikian,$M_{H_{TM}^c}$ memutuskan$H_{TM}^c$ yang merupakan kontradiksi karena$H_{TM}^c$ tidak dapat ditentukan.

$Nb:$

Biarkan R menjadi reduksi dari $H_{TM}^c$ untuk $E_{TM}$ .

Pengurangan itu memberi:

i) $\langle M, x \rangle \in H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \in E_{TM}$

$\qquad$ M loop pada input x IFF bahasa diakui oleh $R(\langle M,x \rangle)$ menerima apa-apa

ii) $\langle M, x \rangle \notin H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \notin E_{TM}$

$\qquad$ M perhentian pada input x IFF bahasa diakui oleh $R(\langle M,x \rangle)$ menerima sesuatu

Bukti oleh bertentangan , (yang kita tahu adalah diputuskan).$A_{TM}= \{\langle M,w\rangle \mid M \text{ is a Turing Machine which accepts w}\}$

Asumsikan keberadaan , TM yang memutuskan L $R_{TM}$$L_\emptyset$

Gunakan kemudian dapat menggunakan dalam konstruksi TM S T M , yang merupakan penentu untuk A T $R_{TM}$$S_{TM}$$A_{TM}$

"Pada masukan ⟨ M , w ⟩ , di mana M adalah pengkodean TM dan w adalah string:$S_{TM}=^{definition}$$\langle M,w\rangle$$M$$w$

1. Ubah , dengan mempertimbangkan input w , sehingga M baru (sebut saja M 1 ) menolak semua input yang tidak sama dengan w , di mana w dibangun ke dalam deskripsi. Jika input sama dengan w , maka M 1 menjalankan M pada w dan menghasilkan keluaran M apa pun .$M$$w$$M$$M_1$$w$$w$$w$$M_{1}$$M$$w$$M$

2. Run dengan masukan ⟨ M 1 , w $R_{TM}$$\langle M_1,w\rangle$

3. Output kebalikan dari keluaran s."$R_{TM}$

$L_\emptyset$$A_{TM}$

E = {| M adalah TM dan L (M) = Φ}. Apakah E Turing dapat dikenali?

E adalah bahasa, untuk menerima bahasa E kami membangun Mesin Turing. Misalkan kita membuat Turing EM untuk bahasa E.

EM akan diberikan sebagai input pengkodean dari mesin Turing lain, Jika mesin yang dimasukkan M menerima bahasa kosong maka itu akan menjadi anggota bahasa E, kalau tidak itu bukan anggota bahasa.

Misalkan kita memiliki Mesin Turing M, kita perlu memeriksa apakah ia menerima bahasa kosong. Mesin Turing EM memiliki M dan string eps, a, b, aa, bb, ..... EM akan memeriksa apakah M dapat mencapai keadaan akhir untuk setidaknya pada satu input, dan jika ia menerima setidaknya satu input saja akan dibuang dan tidak termasuk dalam bahasa E. Sekarang, lihat kemungkinan TM M masuk ke loop sehingga M akan terus berjalan dan kami tidak bisa memutuskan apakah itu dapat menerima atau tidak dapat menerima apa pun. Karenanya, bahasa yang diberikan E ini BUKAN RE.

PS: Saya pikir pelengkap Bahasa E yang diberikan ini akan menjadi RE.