Turing Dapat Dikenali => enumerable

Saya mendapatkan bukti pergi dari pencacah ke Mesin Turing (tetap menjalankan pencacah dan melihat apakah itu cocok dengan input) tetapi saya tidak melihat bagaimana cara lain bekerja.

Menurut catatan dan buku saya (Pengantar Teori Komputasi - Sipser), untuk mendapatkan enumerator Turing dari mesin Turing, pada dasarnya kami menulis semua kombinasi alfabet. Anda kemudian menjalankan TM pada input ini, jika menerima cetak itu, ganti dengan string baru ulangi infinitum.

Masalah yang saya alami adalah tentu saja ini membutuhkan bahasa yang dapat memutuskan. Kalau tidak, mungkin akan terjebak pada kata ketiga dalam beberapa loop tak terbatas yang pasti tidak akan menerima atau menolak dan tentu saja tidak pernah mencetak seluruh bahasa.

Apa yang saya lewatkan?

Apa yang hilang adalah cara Anda menjalankan Mesin Turing pada string untuk mendapatkan Enumerator. Daripada menghasilkan setiap string, jalankan , dan kemudian output string ini jika menerima - yang seperti yang Anda identifikasi tidak akan berfungsi - Anda melakukan sesuatu seperti berikut ini, yang mengadopsi strategi mensimulasikan banyak contoh pada string yang berbeda "di paralel".M M $M$$M$$M$$M$

Asumsikan rekaman itu memiliki konten , di mana adalah beberapa kata yang sedang dipertimbangkan dan adalah keadaan terkini dari beroperasi pada . Ini menunjukkan bahwa salinan sedang disimulasikan. disimpan sehingga kami tahu apa input aslinya.w i S i M w i n M w $\langle w_1, S_1\rangle \# \cdots \# \langle w_n, S_n\rangle$$w_i$$S_i$$M$$w_i$$n$$M$$w_i$

Sekarang jalankan loop berikut

1. Di akhir rekaman, tulis string berikutnya dari , bersama dengan konfigurasi awal dari , yaitu, tulis . S M # ⟨ w , S $w\in\Sigma^*$$S$$M$$\# \langle w, S\rangle$
2. Simulasikan setiap salinan pada pita untuk satu langkah. (Agaknya menggunakan kaset lain.)$M$
3. Jika salah satu memasuki kondisi penerimaan, masukkan string yang sesuai ke pita keluaran. Hapus instance dari kaset.$M$$M$
4. Jika ada yang memasuki kondisi penolakan, lepaskan instance dari pita.$M$$M$
5. Pergi langkah 1.

Tidak sulit untuk berargumen bahwa semua string yang ada diterima oleh pada akhirnya akan menjadi output pada rekaman itu.$w\in\Sigma^*$$M$