Pembatasan Turing Machine yang membuat halting decidable

Jika seseorang membatasi Mesin Turing ke pita hingga (yaitu, untuk menggunakan ruang terbatas ), maka masalah penghentian dapat ditentukan, pada dasarnya karena setelah sejumlah langkah (yang dapat dihitung dari jumlah negara , dan , dan ukuran alfabet), konfigurasi harus diulang.$S$$Q$$S$

Apakah ada pembatasan Turing Machine alami lainnya yang membuat halting dapat diputuskan?

Tentu saja jika grafik transisi-negara tidak memiliki loop atau siklus, penghentian dapat ditentukan. Ada yang lain

Variasi yang cukup alami dan dipelajari adalah mesin Tape-Reversal Bounded Turing (jumlah tape-pembalikan dibatasi); lihat misalnya:

Juris Hartmanis: Komputasi Mesin Turing Pita-Pembalikan. J. Comput. Syst. Sci. 2 (2): 117-135 (1968)

Sunting : [variasi ini lebih artifisial] masalah penghentian dapat dipilih untuk mesin Turing Non-penghapus yang memiliki paling banyak dua instruksi kiri pada alfabet ; lihat Maurice Margenstern: Mesin Turing Nonerasing: Sebuah Batas Antara Masalah Pemutusan yang Diputus dan Universalitas. Teor Komputasi. Sci. 129 (2): 419-424 (1994)$\{0,1\}$

Mempertimbangkan bagaimana melewati parameter ke subrutin dan bagian besar manajemen memori dalam bahasa komputer mainstream adalah stack, variasi yang jelas dan alami adalah untuk membatasi memori tanpa batas dari mesin Turing menjadi tumpukan.

Model seperti itu memiliki sifat-sifat yang bagus , selain berhenti menjadi decidable (terkenal dengan PDA ):

Gagasan PDA dapat digeneralisasi ke otomat bantu pushdown ( S ( n ) -AuxPDA)$S(n)$$S(n)$ . Terdiri dari

1. input tape read-only, dikelilingi oleh endmarkers,
2. kontrol negara yang terbatas,
3. kaset penyimpanan baca-tulis dengan panjang , di mana n adalah panjang dari string input, dan$S(n)$$n$
4. setumpuk

Dalam "Hopcroft / Ullman (1979) Pengantar Teori Automata, Bahasa, dan Komputasi (1st ed.) Kami menemukan:

Teorema 14.1 Berikut ini adalah setara untuk .$S(n)\geq\log n$

1. diterima oleh S ( n ) -AuxPDA deterministik$L$$S(n)$
2. diterima oleh S ( n ) -AuxPDA nondeterministic$L$$S(n)$
3. ada di DTIME ( c S ( n ) ) untuk beberapa konstanta c .$L$$\operatorname{DTIME}(c^{S(n)})$$c$

dengan mengejutkan:

wajar dalam P jika dan hanya jika L diterima oleh log n -AuxPDA.$L$$\mathsf P$$L$$\log n$

frasa dari pertanyaan ini sedikit bermasalah karena mesin Turing dengan pita hingga bisa dibilang tidak banyak terkait dengan mesin Turing dan lebih dekat ke / pada dasarnya mesin keadaan terbatas. sama dengan semua "pembatasan" lainnya pada mesin Turing, hampir semua pembatasan tampaknya merupakan fenomena yang sama sekali berbeda (yaitu selain dari kelengkapan Turing dengan properti yang sama sekali berbeda). sebenarnya beberapa makalah sekarang memanggil / mempelajari batas ini secara rinci dan mungkin memiliki beberapa kesamaan kasar dengan batas komputasi terkenal lainnya yaitu transisi fase lengkap NP.

dan agak berlawanan dengan intuisi bahwa teori FSM yang "lebih sederhana secara komputatif / dapat diputuskan sepenuhnya" muncul lama setelah penemuan mesin Turing, agaknya agak terinspirasi olehnya. jadi mungkin salah satu cara untuk mengulangi hal itu adalah untuk meminta "model decidable paling canggih" dari komputasi atau "studi batas antara model komputasi yang tidak dapat ditentukan dan decidable".

jadi bagaimanapun kemudian sedikit dirumuskan kembali dengan cara ini, jawaban / teori / program penelitian yang masuk akal belum terdaftar adalah sekarang dikembangkan secara signifikan dan secara aktif meneliti / memajukan teori automata waktunya yang baru saja memenangkan hadiah Gereja untuk Alur / Dill. Inilah contoh makalah tentang automata waktunya dan studi model komputasi (un) batas decidability dan ada banyak yang lain dalam nada ini.

• Hasil Desidabilitas dan Kompleksitas untuk Automata Jangka Waktu melalui Kanal Mesin / Abdulla, Deneux, Worrell

• Penghargaan Gereja Alonzo 2016, Timed Automata, Alur / Dill

• Teori Automata / Alur Jangka Waktu , Dill

• Wawancara dengan Rajeev Alur dan David Dill, penerima Penghargaan Alonzo Church 2016 / Aceto, Process Algebra Diary