Mengapa simbol kosong tidak dianggap sebagai bagian dari alfabet input mesin Turing?

Definisi mesin Turing selalu eksplisit tentang simbol kosong yang tidak menjadi bagian dari alfabet input.

Aku bertanya-tanya apa yang salah ketika Anda akan menjadikannya bagian dari alfabet input, karena secara efektif simbol kosong sudah tampaknya menjadi bagian dari input.

Untuk menjelaskan bahwa 'sepertinya' di kalimat terakhir, pertimbangkan yang berikut ini.

Dalam pengaturan default, sejumlah simbol kosong muncul di sebelah kanan input. Ketika kepala kaset bergerak di atas simbol kosong pertama, perhitungan bisa terus berlanjut, karena tidak perlu keadaan menerima atau menolak.

Sekarang anggap perhitungan selanjutnya akan menulis simbol dari alfabet input di sebelah kanan simbol kosong pertama, kemudian kembali ke posisi paling kiri sambil juga kembali ke keadaan awal. Kemudian akan 'memulai kembali' dengan rekaman yang berbeda. Secara efektif, sekarang dimulai dengan input yang berbeda, di mana ada simbol input di sebelah kanan kosong yang tidak ada di sana sebelumnya. Masukan tampaknya secara efektif menyertakan simbol kosong. Perilaku lebih lanjut dari mesin sekarang juga bisa berbeda: setelah menemukan kosong lagi, sekarang akan menemukan simbol yang berbeda di sebelah kanan.

Andaikata skenario ini memang mungkin, mengapa Anda tidak menganggap bagian simbol kosong dari alfabet input dan mengapa Anda tidak mengizinkannya sebagai bagian dari input 'awal'?

Mungkin itu hanya cara untuk mendefinisikan input sehingga tidak selalu tanpa batas?

turing-machines Kebingungan
sumber

Ketika saya di kelas saya merancang mesin Turing yang memanfaatkan memungkinkan β (simbol kosong lokal) di input mereka sebagai pemisah lapangan.

Joshua

Jawaban:

Alasan utamanya adalah memungkinkan mesin mendeteksi ujung inputnya: itu (karakter sebelum) kosong pertama. Jika Anda mengosongkan input, mesin tidak akan pernah tahu apakah mungkin menemukan lebih banyak input dengan memindai lebih jauh ke kanan. Tentu saja, Anda dapat menyelesaikannya dengan memiliki karakter "akhir input" khusus tetapi kemudian Anda harus bersikeras bahwa itu tidak dapat muncul dalam input, jadi Anda baru saja menggeser masalah satu tingkat lebih dalam.

Ini juga membuat kondisi awal lebih mudah untuk ditentukan: input adalah bagian yang tidak kosong dari rekaman awal, yang harus terbatas dan berdekatan. Dan jika Anda ingin karakter kosong menjadi bagian dari alfabet input, Anda selalu dapat menambahkan karakter tambahan (sebut saja "spasi" atau sesuatu) dan biarkan mesin berperilaku seperti yang Anda inginkan ketika melihatnya.

David Richerby
sumber

Ah, tentu saja, tanpa bisa menentukan akhir input awal, beberapa perhitungan tidak mungkin dilakukan. Namun sebaliknya tidak ada yang spesial dari simbol tersebut. Dan saya kira itu masalah ekonomi terminologis untuk menggunakan simbol kosong, karena Anda memerlukannya dalam alfabet Anda. Saya pikir itu akan menjadi lebih jelas bagi saya ketika awalnya didefinisikan dengan simbol end-of-input eksplisit dan pernyataan itu tidak sepenuhnya diperlukan dan sering ditinggalkan.

Kebingungan

{00} \to 0, {11} \to 1, {10, 01} \to b

$\{00\} \rightarrow 0, \{11\} \rightarrow 1, \{10, 01\} \rightarrow b$

Melihat sebagai mesin Turing membutuhkan aturan yang mengatur apa yang dilakukannya jika ia membaca kosong, dan mungkin memiliki aturan yang mengatakannya untuk menulis kosong, bukankah itu berarti bahwa kosong itu memang bagian dari alfabetnya? Saya tidak melihat mengapa input mungkin tidak mengandung kosong. Bagaimana dengan mengkodekan input-item menggunakan karakter yang tidak kosong, dan satu kosong sebagai pemisah? Kemudian beberapa kosong berturut-turut menunjukkan bagian akhir input.

Rosie F

@YonatanN Tentu. Itu "sederhana" tetapi memiliki simbol kosong lebih sederhana.

David Richerby

@RosieF Kosong adalah bagian dari alfabet rekaman; alfabet input adalah bagian dari itu. Dan, tentu saja, Anda dapat mengatur konvensi untuk bagaimana input dapat mengandung kekosongan dalam keadaan tertentu (seperti yang Anda lakukan) tetapi itu hanya membuat definisi lebih kompleks. Definisi yang lebih kompleks berarti lebih sulit untuk membuktikan hal-hal tentang mesin Turing. Dan, karena mesin Turing benar-benar hanya digunakan untuk membuktikan hal-hal (jika Anda ingin merancang komputer yang sebenarnya, itu tidak akan menjadi TM) itu bukan trade-off yang baik.

David Richerby

Anda dapat menetapkan simbol kosong untuk menjadi bagian dari alfabet. Masalah dengan itu adalah bahwa jika mesin Turing dengan input b010010b (di mana b singkatan kosong ) tidak pernah membaca melewati b yang kedua, maka mesin akan berperilaku dengan cara yang persis sama pada semua input mulai dengan b010010b.

Mesin Turing ini disebut mesin Turing awalan , dan mereka sangat berguna untuk membuktikan beberapa teorema tentang kompleksitas Kolmogorov.

Peter Shor
sumber

Jawaban yang sangat singkat: alfabet kaset adalah himpunan simbol yang dapat muncul pada kaset, dan itu termasuk simbol kosong. The masukan alfabet adalah himpunan simbol-simbol yang dapat muncul di masukan awal , dan itu tidak termasuk simbol kosong. Alfabet utama yang dipedulikan mesin adalah alfabet tape: ia masih membutuhkan aturan untuk apa yang harus dilakukan ketika melihat kosong, misalnya

Perbedaan ini penting, seperti yang dikatakan orang lain, sehingga mesin dapat mengetahui di mana inputnya berakhir. Itu alasan yang sama Anda tidak dapat (berguna) menempatkan karakter-nol di tengah-tengah string di C: karakter-nol dicadangkan untuk berarti "karakter bukan-nol terakhir sebelum ini adalah akhir data, jadi ketika Anda melihat ini, Anda selesai ". Jika Anda membutuhkan nol-karakter di tengah-tengah string, menulis strlenmenjadi jauh lebih sulit.

Draconis
sumber