Pertanyaan yang berkaitan dengan Mesin Turing dengan status tidak berguna

OK, jadi inilah pertanyaan dari tes sebelumnya di kelas Teori Komputasi saya:

Keadaan tidak berguna di TM adalah yang tidak pernah dimasukkan pada string input apa pun. Biarkan Buktikan bahwa tidak dapat ditentukan.

$$\mathrm{USELESS}_{\mathrm{TM}} = \{\langle M, q \rangle \mid q \text{ is a useless state in }M\}.$$ $\mathrm{USELESS}_{\mathrm{TM}}$

Saya pikir saya punya jawaban, tetapi saya tidak yakin apakah itu benar. Akan memasukkannya di bagian jawaban.

Ini jelas dapat direduksi dari Masalah Pemutusan Hubungan. Jika sebuah mesin tidak berhenti pada input maka setiap status final adalah "tidak berguna". Diberikan input untuk masalah mudah untuk membangun yang berhenti pada setiap input (dengan demikian keadaan akhirnya tidak sia-sia) jika dan hanya jika berhenti di . Dengan begitu Anda dapat memutuskan Menghentikan Masalah jika Anda dapat memutuskan , yang menghasilkan kontradiksi.x M , x M x M x U S E L E S S T $M$$x$$M,x$$M_x$$M$$x$$\mathrm{USELESS}_{\mathrm{TM}}$

Untuk keperluan bukti ini, kami akan menganggap bahwa dapat dipilih untuk menampilkan kontradiksi.$\mathrm{USELESS}_{\mathrm{TM}}$

Buat TM yang melakukan hal berikut:$R$

• Mengonversi TM ke pushata automata dengan tumpukan santai (mis. Tidak ada persyaratan LIFO). Ini sama dengan grafik terarah yang merinci transisi antara statusP $M$$P$$M$
• Tandai negara mulai dari .$P$
• Dari keadaan awal, mulailah pencarian pertama di sepanjang setiap tepi keluar menandai setiap node yang tidak bertanda.
• Ketika pencarian berakhir, jika ada node tidak bertanda yang cocok dengan , terima ; jika tidak tolak .$q$

Kemudian buat TM = "Pada masukan $$$S$

1. Buat TM seperti yang ditunjukkan di atas.$R$
2. Jalankan pada .$q$$R$
3. Jika kembali menerima, terima ; jika menolak, tolak " $R$$R$

Jadi, jika adalah penentu untuk maka adalah penentu untuk (masalah penerimaan). Karena terbukti tidak dapat diputuskan (lihat Teori Sutan Komputasi Michael Sipser 4.11 pada halaman 174), kami telah mencapai kontradiksi. Oleh karena itu, hipotesis asli salah dan tidak dapat ditentukan.U S E L E S S T M S A T M A T M U S E L E S S T $R$$\mathrm{USELESS}_{\mathrm{TM}}$$S$$A_{\mathrm{TM}}$$A_{\mathrm{TM}}$$\mathrm{USELESS}_{\mathrm{TM}}$