Apakah set mesin Turing yang berhenti paling banyak 50 langkah pada semua input, dapat dipilih?

19

Mari F={M:M is a TM which stops for every input in at most 50 steps} . Saya perlu memutuskan apakah F dapat dipilih atau dihitung secara rekursif. Saya pikir itu dapat diperhitungkan, tetapi saya tidak tahu bagaimana membuktikannya.

Pikiran saya

Bagian "50 langkah" ini langsung mengubah tanda R untuk saya. Jika itu untuk input spesifik maka akan dapat ditentukan. Namun, ini untuk setiap input. Memeriksa input yang tak terbatas membuat saya berpikir bahwa masalahnya adalah co-RE , yaitu komplemennya dapat diterima.

Mungkin, saya dapat memeriksa konfigurasi dan melihat bahwa semua konfigurasi setelah 50 langkah tidak mengarah untuk menerima status - bagaimana saya melakukannya?

Jozef
sumber

Jawaban:

21

NN1

Seperti yang dikatakan swegi dalam respons sebelumnya, jika mesin berhenti setelah paling banyak langkah, maka hanya sel pada kaset yang signifikan. Kemudian cukup untuk mensimulasikan mesin pada semua string input dari bentuk , di mana ada jumlah yang terbatas.N0,1,,N1MxΣN

  • Jika salah satu dari simulasi ini gagal memasuki keadaan terputus-putus olehtransisi, ini menunjukkan bahwa setiap string input yang dimulai dengan adalah string yang mesinnya tidak berhenti dalam langkah-langkah pertama .NthxN
  • Jika semua simulasi ini dihentikan olehtransisi, kemudian berhenti di dalam langkah pada semua input dari panjang apa pun (yang substring panjang adalah semua yang pernah ditindaklanjuti)NthMNN
Niel de Beaudrap
sumber
Dan- Apakah saya berasumsi bahwa sehingga panjangnya lebih panjang dari secara otomatis ditolak? xN
Jozef
Mengapa tidak bisa melompat lebih jauh dari sel N dalam langkah-langkah komputasi N?
Jozef
@ Joef: simulasi hanya iterate melalui semua string input panjang N yang mungkin . Anda bisa mengulangi lebih banyak string, tetapi Anda tidak akan belajar apa-apa lagi, karena hanya simbol N pertama yang penting. Alasan mengapa itu tidak bisa lebih jauh dari sel N adalah karena mesin Turing (atau definisi standar mereka) hanya memindahkan satu sel per langkah.
Niel de Beaudrap
Benar, saya mengerti. jadi Anda hanya memikirkan simbol N pertama dari setiap kata, jadi Anda memeriksa semua kombinasi kata tersebut. mengapa Anda menghapus deskripsi konfigurasi?
Jozef
Itu masih terlihat jika Anda melihat suntingan sebelumnya. Aku direvisi untuk ini karena sementara jawaban lain itu mungkin menarik, banyak apa yang membuatnya "menarik" hanya melayani untuk mengaburkan fakta bahwa prosedur keputusan tidak lebih atau kurang dari simulasi pada semua kemungkinan input panjang N . Saya pikir lebih baik untuk merevisi jawaban untuk sesuatu yang jauh lebih mudah, dan yang pada dasarnya sampai pada akar dari apa yang membuat masalah dapat dipecahkan. MN
Niel de Beaudrap
4

Jika berhenti dalam tidak lebih dari 50 langkah, dari posisi M dapat mencapai pada pita yang biasanya tak terbatas terbatas. Dengan demikian pita tak terbatas dapat disimulasikan oleh yang terbatas. Ini berarti bahwa rekaman itu dapat disimulasikan oleh otomat terbatas. Ini mengikuti bahwa mesin turing M yang berhenti di tidak lebih dari 50 langkah adalah bisimilar untuk beberapa terbatas automaton M ' .MMMM

Misalkan adalah himpunan status M , F Q himpunan status penerimaan dan Γ menjadi alfabet. Kemudian kita membangun set negara Q ' dari M ' sebagai berikut: Q ' = { n , q , s , p , a QMFQΓQM mana p adalah posisi head baca / tulis di atas kaset. Kita bisa membatasi posisi untuk { - 50 , . . . , 50 } karena jumlah langkah komputasi yang diizinkan membatasi jumlah posisi yang dapat dijangkau.Q={n,q,s,p,a|n{0,...,50}qQ,sΓ,p{50,...,50},aqF}p{50,...,50}

Memiliki negara dari robot yang terbatas M ' maka berarti bahwa kita berada di negara q dari otomat asli, dengan s pada pita pada posisi p mana juga membaca / menulis kepala diposisikan , setelah langkah komputasi ke- n . Negara adalah salah satu yang menerima jika suatu t r u e .n,q,s,p,aMqspnatrue

Mengubah hubungan transisi dari mesin turing beton adalah pekerjaan yang sedikit lebih tetapi tidak diperlukan untuk pertanyaan asli, karena cukup untuk menunjukkan bahwa ruang keadaan terbatas (dan dengan demikian kita bisa menguji setiap input dengan panjang paling banyak 50 simbol pada setiap otomat seperti itu). Idenya adalah untuk membangun hubungan transisi baru yang berlangsung dari keadaan ke keadaan n + 1 , q ' , s ' , p ' , sebuah ' di nn,q,s,p,an+1,q,s,p,an-th langkah IFF transisi komputasi adalah dalam hubungan transisi asli.q,s,pq,s,p

swegi
sumber
Bagaimana Anda mensimulasikan penyimpanan pada kaset, yaitu kemampuan untuk meninjau kembali simbol yang sudah Anda baca, pada robot terbatas?
Niel de Beaudrap
@NieldeBeaudrap: Anda menyebutkan seluruh ruang keadaan, yaitu Anda melakukan pengecekan model rekaman terbatas dan otomat kontrol mesin turing.
swegi
1
Mengingat bahwa OP mengajukan pertanyaan mendasar tentang komputabilitas untuk Mesin Turing, Anda mungkin ingin membongkar sketsa itu menjadi sesuatu yang lebih penuh. (Saya sendiri belum pernah mendengar ungkapan "pengecekan model" dalam konteks komputasi sebelumnya.) Dalam konteks, saya biasanya akan berasumsi dengan 'otomat terbatas' yang Anda maksudkan adalah DFA atau sejenisnya kecuali jika Anda menentukan lain, dan tidak jelas bagi saya apa akan sesuai dengan input DFA dalam konstruksi seperti itu. Jika Anda hanya bermaksud grafik yang mewakili kemungkinan lintasan TM, maka saya setuju.
Niel de Beaudrap
Dengan model memeriksa bagian terbatas dari rekaman saya pada dasarnya berarti apa yang Anda tulis dalam jawaban Anda: cukup menguji setiap input ukuran paling banyak 50 dan memeriksa apakah negara penerima telah tercapai.
swegi
1
Saya berharap orang-orang akan berhenti menyebarkan mitos bahwa kaset mesin Turing perlu tanpa batas. Tidak - itu bisa terbatas selama diperpanjang sesuai kebutuhan.
reinierpost