Apakah mesin Turing tanpa kemampuan menulis di sel kosong kurang kuat daripada Turing standar?

Apakah mesin Turing tanpa kemampuan menulis di sel kosong kurang kuat daripada Turing standar?

Saya pikir jawabannya adalah ya tetapi saya tidak dapat menemukan perhitungan yang dapat dilakukan mesin standar Turing tetapi mesin ini tidak bisa.

Ada ide?

Dengan kata lain, " Apakah komputer dengan memori terbatas kurang kuat daripada komputer dengan memori tidak terbatas. "?

Nat

Jawaban:

Jenis mesin Turing yang Anda gambarkan adalah otomat terikat linier (hanya dapat menulis pada bagian-bagian pita yang berisi input). BBA adalah akseptor untuk bahasa konteks-sensitif sehingga untuk menemukan contoh spesifik dari masalah yang tidak dapat diselesaikan dengan pembatasan ini tetapi dapat diselesaikan secara umum dengan mesin Turing, Anda hanya perlu bahasa yang dapat ditentukan tetapi tidak konteks- peka.

Contoh yang diberikan di Wikipedia adalah:

Contoh bahasa rekursif yang tidak peka konteks adalah bahasa rekursif apa pun yang keputusannya merupakan masalah sulit EXPSPACE, katakanlah, serangkaian pasangan ekspresi reguler yang setara dengan eksponensial.

Untuk lebih banyak contoh, lihat Apakah ada contoh bahasa rekursif yang tidak peka konteks?

roctothorpe
sumber

Mesin Turing yang tidak dapat menulis pada bagian yang kosong adalah dengan versi ruang dari teorema speedup linier, sebuah automaton yang dibatasi linier. Karenanya setiap masalah keputusan di luar tidak dapat diputuskan olehnya. Masalah seperti itu memang ada oleh teorema hierarki ruang. $\textsf{DSPACE}(O(n))$

quicksort
sumber

Tidak bisakah Anda memberikan sufiks yang cukup panjang, untuk masalah apa pun, simbol khusus di akhir kaset yang dapat digunakan sebagai blanko?

Kej

@ gen Tidak secara umum. Dalam kasus yang paling umum, catat saja bahwa mengetahui akhiran yang panjang akan membuat masalah penghentian dapat diputuskan. Akibatnya, komputasi awalan yang cukup panjang dapat diputuskan, secara umum - jadi tidak masuk akal untuk mengasumsikan bahwa sufiks seperti itu diberikan.

chi

Apakah akurat untuk menafsirkan jawaban ini sebagai, " Mesin Turing dengan memori terbatas tidak akan memiliki cukup memori untuk menjalankan program sembarang karena beberapa program mungkin membutuhkan lebih banyak memori daripada apa pun yang mereka miliki. "?

Nat

@Nat: Saya akan menyebutnya sebagai "jumlah memori yang dibutuhkan oleh suatu program secara umum tidak diketahui sampai program dijalankan". Yang aneh (paradoks matematika yang hebat) adalah bahwa untuk setiap bilangan bulat triplet X, Y, Z, ada batas atas jumlah sel kaset yang diperlukan untuk program yang akan berakhir dan yang berisi paling banyak negara X, pada kaset yang dapat menampung paling banyak jenis Y simbol, dan diinisialisasi dengan simbol Z pada pita, tetapi tidak ada batas atas yang dapat dibuktikan kecuali untuk nilai-nilai sepele dari X, Y, dan Z.

supercat