Apakah dapat diputuskan apakah TM mencapai beberapa posisi pada rekaman itu?

Saya memiliki pertanyaan-pertanyaan ini dari ujian lama yang saya coba selesaikan. Untuk setiap masalah, input adalah encoding dari beberapa Turing mesin .$M$

Untuk bilangan bulat , dan tiga masalah berikut:$c>1$

1. Benarkah bahwa untuk setiap input , M tidak lulus posisi saat dijalankan pada ?$x$$|x|+c$$x$

2. Benarkah bahwa untuk setiap input , M tidak melewati posisi ketika dijalankan pada x ?maks { $x$$\max \{|x|-c,1 \}$$x$

3. Apakah benar bahwa untuk setiap input $x$ , M tidak melewati posisi $(|x|+1)/c$ saat dijalankan pada $x$ ?

Berapa banyak masalah yang bisa diputuskan?

Nomor masalah (1), menurut saya, ada di $\text {coRE} \smallsetminus \text R$ karena saya mengerti benar karena, saya bisa menjalankan semua input secara paralel, dan berhenti jika beberapa input mencapai posisi ini dan untuk menunjukkan bahwa itu bukan di $\text R$ saya bisa mengurangi komplemen Atm untuk itu. Saya membangun mesin Turing $M'$ sebagai berikut: untuk input $y$ saya memeriksa apakah $y$ adalah sejarah perhitungan, jika ya, maka $M'$ berjalan dengan benar dan tidak berhenti, jika tidak, maka ia berhenti.

Untuk (3), saya percaya bahwa itu dapat dipilih karena untuk $c \geqslant 2$ itu semua mesin Turing yang selalu tetap pada sel pertama dari garis, karena untuk string satu karakter dapat melewati sel pertama, jadi saya perlu mensimulasikan semua string dengan panjang 1 untuk $|Q|+1$ langkah (Apakah ini benar?), dan lihat apakah saya hanya menggunakan sel pertama di semuanya.

Saya tidak tahu apa yang harus saya lakukan dengan (2).

Setiap situasi yang menanyakan apakah Mesin Turing terbatas pada bagian terbatas dari rekaman (katakanlah panjang ) pada input yang diberikan dapat ditentukan.$n$

Argumennya berfungsi sebagai berikut. Pertimbangkan Mesin Turing, tape, dan posisi Mesin Turing pada tape. Semua ini memiliki sejumlah konfigurasi yang terbatas. Untuk lebih spesifik, hanya adakonfigurasi yang mungkin. adalah himpunan simbol rekaman dan adalah himpunan negara. Saya akan terus menggunakan kata "konfigurasi" untuk menggambarkan keadaan Mesin Turing yang dikombinasikan dengan keadaan kaset dan posisinya pada kaset untuk sisa jawaban ini, tetapi itu bukan kosakata standar.$t = n|\Gamma|^n|Q|$$\Gamma$$Q$

Jalankan mesin, catat semua konfigurasi sebelumnya. Jika pernah melampaui titik , kembalikan "ya, melewati posisi ". Jika tidak, mesin berada di antara 0 dan . Jika mesin pernah mengulangi konfigurasi - keadaannya, simbol pada pita, dan posisinya pada pita identik dengan apa yang sebelumnya - mengembalikan "tidak, tidak pernah melewati posisi ."$n$$M$$n$$n$$M$$n$

Dengan prinsip pidgeonhole, ini harus terjadi tidak lebih dari langkah. Jadi semua hal di atas dapat dipilih; setelah paling banyak langkah simulasi Anda mendapatkan jawaban.$t+1$$t+1$

Catatan singkat mengapa ini bekerja: ketika mesin, selotip, dan posisinya pada pita itu berulang, pasti ada urutan konfigurasi di antara pengulangan-pengulangan ini. Urutan ini akan terjadi lagi, mengarah ke konfigurasi yang sama sekali lagi - mesin berada dalam loop yang tak terbatas. Ini karena kami melacak setiap aspek dari Mesin Turing; tidak ada yang di luar konfigurasi yang dapat berdampak pada apa yang terjadi. Jadi ketika sebuah konfigurasi berulang, itu akan diulang lagi, dengan serangkaian konfigurasi yang identik di antaranya.

Jadi membatasi pita ke bagian yang terbatas dari string itu dapat ditentukan. Oleh karena itu, dengan mengulangi semua kemungkinan input string, masalahnya ada pada untuk ketiga pertanyaan. Anda mungkin sudah menyadari hal ini (antara ide Anda untuk 1 dan 3 dan jawaban Ran G untuk 2 tampaknya sudah terpecahkan sepenuhnya), tetapi saya pikir mungkin ada baiknya untuk memposting.$\text{coRE}$

(2) sangat mirip dengan (3) dan alasan yang sama dengan (3) berlaku di sini juga: perhatikan bahwa mesin yang di memiliki properti aneh - mereka tidak membaca seluruh input (mereka tidak pernah mencapai itu terakhir) bits.) Dan ini berlaku untuk setiap input.$L_2$$c$

Ok, jadi sekarang mari kita pertimbangkan hanya input hingga panjang . Untuk masing-masing dari mereka, hanya ada dua pilihan: mesin loop / berhenti tanpa menggerakkan kepala, atau itu menggerakkan kepala. Jika memindahkan kepala pada beberapa (dengan ), mesin itu tidak ada dalam karena input . Kalau tidak, saya mengklaim mesin di . Karena tidak pernah menggerakkan kepala - ia tidak tahu ukuran inputnya! ini artinya berperilaku sama untuk semua input panjang . Oleh karena itu, dapat dipilih.x | x | ≤ c L 2 x L 2 | x | > c L $c$$x$$|x|\le c$$L_2$$x$$L_2$$|x|>c$$L_2$