Menentukan masalah penghentian untuk automata non-deterministik

18

Definisi utama Turing machine (TM), setidaknya dalam buku referensi saya sendiri (Hopcroft + Ullman 1979) adalah deterministik.

Oleh karena itu pemahaman saya sendiri tentang masalah penghentian terutama untuk TM deterministik, meskipun saya sadar bahwa itu dapat dipertimbangkan untuk jenis automata lainnya.

Saya juga memperhatikan bahwa determinisme sering kurang lebih tersirat dalam cara orang sering merujuk pada TM atau masalah yang terhenti. Halaman wikipedia tentang masalah penghentian adalah contoh yang bagus untuk itu.

Tapi, sepertinya tidak ada alasan untuk pembatasan seperti itu. Mengingat keluarga automata yang dapat bersifat non-deterministik, masalah penghentian untuk dapat didefinisikan sebagai: $\mathcal F$ $\mathcal F$

Apakah ada prosedur pengambilan keputusan yang seragam sehingga, diberikan otomat dan input , dapat memutuskan apakah ada penghentian perhitungan pada input . $A\in\mathcal F$ $x$ $A$ $x$

(Ini tidak sama dengan mengatakan bahwa perhitungan dengan input akan berakhir.) $A$ $x$

Memang, itu tampaknya satu-satunya cara untuk memberikan beberapa pengertian untuk diskusi tentang masalah berhenti untuk Linear Bounded Automata (LBA) yang terutama automata non-deterministik.

Jadi pertanyaan saya adalah apakah saya benar, dan apakah ada alasan (dan alasan apa) untuk perawatan kelas dua yang tampaknya menghentikan masalah untuk automata non-deterministik.

turing-machines automata nondeterminism halting-problem linear-bounded-automata babou
sumber

Jika Anda berpikir ada sesuatu yang salah dalam pertanyaan ini, apakah Anda akan berbaik hati untuk mengatakan apa itu, sehingga kami semua dapat mengambil manfaat dari pengetahuan Anda dan meningkatkan postingan untuk semua pengguna. Terima kasih.

babou

12

Ada beberapa alasan saya pikir kita kurang berupaya dalam masalah Menghentikan untuk model non-deterministik.

Yang pertama adalah, pada kenyataannya, ada dua masalah penghentian yang relevan untuk model ND. Diberikan input dan mesin non-deterministik : $x$ $M$

Apakah ada menjalankan valid pada yang berhenti? $M$ $x$
Apakah ada menjalankan pada yang tidak berhenti? yaitu apakah semua menjalankan yang valid berhenti? $M$ $x$

Untuk mesin deterministik, ini identik, karena hanya ada satu proses valid pada input . Tetapi untuk mesin non-deterministik, mungkin ada beberapa kali proses. Yang mana Anda tertarik tergantung pada aplikasi Anda. $M$ $x$

Kedua, model non-deterministik sudah tidak realistis: mereka berasumsi bahwa Anda memiliki kotak ajaib yang memberi tahu Anda jalan mana yang harus diambil, atau bahwa Anda memiliki semacam paralelisme tanpa batas. Karena Mesin Turing yang non-deterministik dan deterministik memiliki kekuatan yang setara, dalam kebanyakan kasus Anda hanya mengonversi mesin tersebut menjadi yang determinstik sebelum Anda khawatir akan berhenti.

Sebagai perpanjangan dari ini, kami tidak peduli karena membuktikan sesuatu tentang mesin non-deterministik setidaknya sama sulitnya dengan membuktikan sesuatu tentang mesin deterministik yang setara. Kita sudah tahu bahwa tidak ada solusi untuk Masalah Putus yang deterministik, jadi yang benar-benar bermanfaat adalah membuktikan masalah lain yang tidak dapat diputuskan melalui pengurangan. Dan itu akan selalu kurang untuk mengurangi masalah berhenti deterministik, karena itu lebih mudah daripada rekan non-deterministik.

Ya ampun
sumber

Anda menyatakan: " Tetapi untuk mesin non-deterministik, mungkin ada beberapa kali proses. Yang mana yang Anda minati tergantung pada aplikasi Anda. " Bisakah Anda mengilustrasikan pernyataan itu dengan sebuah contoh? Kemudian Anda menyatakan " Anda baru saja mengubah mesin menjadi yang deterministik sebelum Anda khawatir tentang berhenti ". Bagaimana itu dilakukan untuk LBA?

babou

LBA adalah subset dari Mesin Turing non-deterministik, sehingga mereka selalu dapat dikonversi menjadi Mesin Turing deterministik menggunakan metode biasa. Saya menduga ada konstruksi khusus yang dapat digunakan untuk mengkonversi ke mesin dengan properti tertentu, sehingga kami dapat menjaga kemampuan penalaran tambahan yang kami dapatkan dari LBA. Saya pikir ini akan terlihat seperti algoritma backtracking di mana ruang linear digunakan, kecuali stack panggilan berpotensi besar secara eksponensial (saya tidak yakin, saya harus mencarinya).

jmite

Untuk beberapa jalur, pertimbangkan dua mesin

, satu yang selalu berhenti pada input

, dan satu yang tidak pernah berhasil untuk

. Kita dapat membuat LBA

yang dimulai dengan secara non-deterministik memilih nilai boolean. Jika benar, ia menjalankan

pada input x. Jika memilih false, ia menjalankan

pada

. Setiap pilihan benar dan salah adalah "jalan" yang berbeda. Apakah mesin ini berhenti untuk

? Ada jalur di mana ia berhenti di

, tetapi tidak berhenti untuk semua jalur yang membaca

.

M_{1}, M_{2}

$M_1, M_2$

x

$x$

x

$x$

M

$M$

M_{1}

$M_1$

M_{2}

$M_2$

x

$x$

x

$x$

x

$x$

x

$x$

tungau

1

@ HendrikJan Tampaknya penghentian NLBA agak ditangani dengan teorema Savitch . Tapi itu mengubah batas linear menjadi kuadrat.

babou

1

@Raphael yang saya maksud dengan ini adalah bahwa, untuk menunjukkan masalah

tidak dapat diputuskan, Anda menunjukkan bahwa Anda dapat menggunakan

untuk mensimulasikan masalah lain yang tidak dapat ditentukan. Karena ada pemetaan injeksi sepele dari DTM ke NTM, setiap pengurangan dari penghentian NTM juga merupakan pengurangan dari penghentian DTM. Biasanya akan lebih sedikit pengurangan dari penghentian DTM, karena ini adalah masalah yang tidak terlalu sulit untuk Anda coba simulasikan.

P

$P$

P

$P$

jmite

4

Masalah penghentian adalah masalah lengkap , karena dapat dinyatakan sebagai: $\Sigma_1$

. $H(P,x) \leftrightarrow \exists c \, \text{ s. t. $c$ is a halting computing of $P$ on $x$}$

Ini menunjukkan bahwa definisi Anda adalah yang benar. Secara umum, setiap definisi -Lengkap adalah "benar". $\Sigma_1$

Yuval Filmus
sumber

Sayangnya, saya hampir tidak tahu tentang hierarki aritmatika. Apakah saya benar dalam memahami bahwa

merupakan masalah semi-decidable? Bagaimana dengan:

Σ_{1}

$\Sigma_1$

. Saya bertanya karena kuantifikasi eksistensial dan universal tampaknya berakhir di kelas yang berbeda, tetapi semuanya kabur bagi saya.

juga semi-decidable.

K (P, x) \leftrightarrow \forall c, c is a computing of P on x ⟹ c is halting.

$K(P,x)\leftrightarrow\forall c, c\text{ is a computing of $P$ on $x\implies c$ is halting.}$

K

$K$

babou

Itulah yang saya khawatir Anda akan jawab. Saya bertanya karena saya pikir saya memiliki prosedur semi-keputusan untuk itu. Jadi bukti saya salah, atau saya meresmikan masalah saya dengan salah. Pada dasarnya itu adalah saran jmite bahwa penghentian non-deterministik pada input

dapat didefinisikan dengan mengharuskan semua perhitungan pada

berhenti. Dan saya percaya sampai sekarang saya memiliki semi-keputusan untuk itu.

x

$x$

x

$x$

babou

Sebenarnya definisi Anda tidak bagus karena alasan lain: apa yang Anda maksud dengan "

sedang berhenti"? Entah maksud Anda bahwa

, yang merupakan a-priori hanya perhitungan yang tidak lengkap, sebenarnya lengkap. Dalam hal ini,

tidak pernah benar, karena Anda dapat menganggap

sebagai komputasi kosong. Dalam kasus lain, tidak jelas bahwa deskripsi

adalah terbatas, dan juga tidak jelas bahwa predikat "

sedang terhenti" dapat dihitung.

c

$c$

c

$c$

K (P, x)

$K(P,x)$

c

$c$

c

$c$

c

$c$

Yuval Filmus

Jadi sebenarnya masalahnya ada di

tetapi mungkin tidak

lengkap.

Π_{1}

$\Pi_1$

Π_{1}

$\Pi_1$

Yuval Filmus

Terima kasih, dan maaf untuk bacaan naif saya. Saya pikir

Anda gunakan adalah singkatan dari "complete" computations, yang tampaknya merupakan kesalahan pada domain yang dikuantifikasi. Saya kira orang hanya dapat menggunakan domain yang dapat dihitung dan set perhitungan non-stop dari TM nondeterministic tidak memenuhi syarat. Juga saya kira pembilang memberitahu kita seberapa buruk komputabilitas mungkin, tetapi tidak memberikan jaminan bahwa itu adalah yang buruk. Jadi sepertinya proposal jmite tidak mudah diungkapkan secara langsung dalam "format" yang diperlukan, tetapi prosedur semi-keputusan saya mungkin benar.

c

$c$

babou

2

Anda mengatakan ada "perlakuan kelas dua yang jelas" dari masalah berhenti untuk mesin nondeterministic. Tampaknya nondeterminisme tidak dianggap secara historis sampai lama setelah pembuatan Turings dari deterministik TM & ini mungkin ada hubungannya dengan fokus penelitian di daerah tersebut. Namun poin utama di sini adalah bahwa masalah nondeterministik dapat dengan mudah direduksi menjadi masalah deterministik, sehingga orang hanya perlu mempelajari masalah deterministik "tanpa kehilangan generalitas".

lebih jauh lagi, untuk melawan ide "kelas 2" di sini adalah setidaknya satu ref / paper yang mempelajari masalah berhenti untuk mesin nondeterministic dan menemukan koneksi yang berguna / mendalam. beberapa bukti tidak langsung di sepanjang garis bahwa penelitian CS begitu luas / terspesialisasi, kadang-kadang beberapa penelitian awal telah dilakukan di sebagian besar wilayah, bahkan tampaknya sempit, dan dapat mendekati hampir tidak berarti atau memotong rambut untuk mengurutkan masalah yang berbeda dalam kepentingan mereka. dan sebaliknya, nondeterminisme tampaknya konsep yang sangat dalam / di mana-mana / lintas sektor dalam CS (pertanyaan kunci terbuka seperti P vs NP ada di dalamnya) & aspek itu kemungkinan akan berlanjut lama ke masa depan.

Masalah Tersendat Parameter / Chen, Kegagalan

Abstrak. Masalah parameterized p-Halt mengambil sebagai input mesin Turing nondeterministic M dan bilangan alami n, ukuran M menjadi parameter. Ia bertanya apakah setiap proses penerimaan M pada kaset input kosong membutuhkan lebih dari n langkah. Masalah ini adalah di kelas XPuni, kelas "seragam XP," jika ada algoritma yang memutuskannya, yang untuk mesin tetap M berjalan dalam polinomial waktu dalam n. Ternyata berbagai masalah terbuka dari berbagai bidang ilmu komputer teoritis terkait atau bahkan setara dengan p-Hentikan XPuni. Dengan demikian pernyataan ini membentuk jembatan yang memungkinkan untuk memperoleh kesetaraan antara pernyataan dari area yang berbeda (teori bukti, teori kompleksitas, kompleksitas deskriptif, ...) yang pada pandangan pertama tampaknya tidak berhubungan. Seperti yang ditunjukkan oleh presentasi kami,

vzn
sumber

2

Pendeknya

Tampaknya tidak ada alasan yang baik untuk mengabaikan masalah penghentian dalam pengaturan yang bukan merupakan salah satu klasik dari mesin Turing deterministik, selain fakta bahwa masalah penghentian klasik menjawab beberapa pertanyaan matematika utama (seperti Entscheidungsproblem ), sementara varian hanya masalah teknis yang menarik (?), tetapi kurang berdampak pada fondasi.

$A$ $x$

Menurut jawaban jmite, penghentian non-deterministik ini dapat didefinisikan sebagai sesuai dengan keberadaan setidaknya satu penghentian perhitungan ( penghentian eksistensial ), atau sebagai alternatif untuk mengharuskan semua perhitungan yang mungkin dihentikan ( penghentian universal ). Dua definisi ini sesuai dengan dua definisi yang berbeda dari masalah penghentian nondeterministik.

Saya menunjukkan bahwa, untuk mesin Turing, dua definisi berhubungan dengan dua cara berbeda untuk menentukan mesin dengan cara pas. Dari sini, saya menyimpulkan bahwa dua varian dari masalah penghentian nondeterministik keduanya Turing setara dengan masalah penghentian deterministik klasik .

Namun, saya juga menunjukkan bahwa masing-masing definisi penghentian ini secara langsung berkaitan dengan definisi yang sesuai dari bahasa yang dikenali oleh mesin Turing, dan hubungan ini dapat dengan mudah dinyatakan dengan syarat memilih definisi yang konsisten.

Oleh karena itu, mengingat definisi bahasa yang biasa dikenali oleh otomat nondeterministik, definisi alami dari penghentian nondeterministik adalah penghentian eksistensial, seperti yang diusulkan dalam pertanyaan awal.

Sebagian besar analisis ini secara alami meluas ke jenis automata lain, meskipun konstruksi yang saling terkait sering tidak tersedia dalam keluarga yang kurang kuat daripada mesin Turing.

pengantar

Saya menulis ini sebagai jawaban karena sebagian menjawab pertanyaan saya setelah lebih banyak memikirkannya, mempertimbangkan jawaban yang ada. Juga, mengedit pertanyaan saya setelah tiga jawaban mungkin dalam kasus ini membingungkan masalah, dan saya lebih suka meninggalkan pertanyaan seperti aslinya ditulis untuk menghindari itu.

Saya pertama kali membahas beberapa ketidaksepakatan saya dengan jawaban yang diberikan. Intinya bukan untuk meremehkan upaya adil dalam menjawab pertanyaan saya (terima kasih atas semua jawaban), tetapi untuk menyelesaikan masalah dengan membahas atau memperdebatkan poin teknis.

Saya pikir pertanyaan awal tidak membutuhkan konteks atau motivasi. Masalah penghentian adalah salah satu pertanyaan utama yang kami tanyakan tentang automata di satu sisi, dan nondeterminisme adalah salah satu fitur yang sangat umum dan berguna dari banyak automata di sisi lain. Lebih jauh, nondeterminisme bukan hanya alat teoritis umum untuk menyederhanakan bukti, tetapi fitur penting dari beberapa keluarga automata, seperti linear bounded automaton (LBA), setidaknya pada saat penulisan ini.

Oleh karena itu sangat wajar untuk bertanya-tanya apakah masalah penghentian memiliki makna, atau makna yang lebih disukai, yang dan mengapa, dalam kasus automata nondeterministic.

Apakah masalah penghentian administrasi ditangani dengan baik?

Pertanyaan saya bertanya-tanya mengapa masalah berhenti untuk automata nondeterministic tampaknya menerima perlakuan kelas dua , yang memang menghasilkan downvote dan jawaban oleh vzn. The jawaban dengan vzn , yang benar-benar lebih komentar panjang, menegaskan bahwa " nondeterminism tampaknya sangat dalam / di mana-mana / crosscutting konsep di CS", yang tidak pernah saya ragukan. Itu juga memberikan satu referensi untuk beberapa penelitian tentang penghentian untuk mesin nondeterministik yang tidak mengejutkan, tetapi tidak benar-benar membahas maksud saya. Maksud saya adalah bahwa saya tidak ingat benar-benar melihat definisi dari masalah penghentian yang ditujukan di mesin nondeterministic, meskipun saya memang membaca beberapa litterature di lapangan. Itu tidak dibahas, AFAIK, dalam buku referensi saya (Hopcroft + Ullman 1979). Tampaknya sering tersirat dalam pikiran orang-orang bahwa mereka mempertimbangkan automata deterministik, biasanya Turing mesin, yang definisi rujukannya deterministik.

Sebagai contoh, dalam pertanyaan Mengapa masalah penghentian dapat dianggap sebagai keputusan untuk LBA? , Yuval Filmus lupa dalam jawabannya bahwa LBA adalah perangkat yang tidak ditentukan - tetapi dengan brilian menyimpan jawabannya dengan komentar 4 kata .

Sebagai saksi terakhir terhadap fakta bahwa masalah ini tidak ditangani dengan baik secara umum (meskipun ada beberapa penelitian khusus), saya akan menyebut fakta bahwa masalah ini harus dibahas di sini.

The jawaban dari jmite adalah satu-satunya yang benar-benar mencoba untuk menjelaskan mengapa itu mungkin tidak akan baik ditangani. Argumen pertamanya adalah bahwa ada dua definisi yang mungkin, tetapi saya percaya bahwa situasi ini seharusnya mendorong lebih banyak analisis untuk menentukan definisi mana yang paling tepat. Saya berusaha melakukan itu di bawah.

Dia juga menyarankan bahwa, karena TM non-deterministik selalu dapat dikonversi menjadi deterministik yang setara, maka tidak ada gunanya mengkhawatirkan masalah berhenti pada kasus non-deterministik. Saya tidak sepenuhnya yakin, tetapi mungkin dianggap sebagai alasan yang baik oleh banyak orang. Namun, argumen tidak berlaku untuk Linear Bounded Automata (LBA), karena masih merupakan masalah terbuka apakah LBA deterministik setara dengan LBA nondeterministic. Dan ada keluarga automata lain yang keluarga deterministiknya lebih lemah daripada keluarga nondeterministik (PDA misalnya).

Saya juga tidak setuju dengan poin terakhir, menegaskan bahwa kita tidak boleh khawatir dengan penghentian nondeterministik karena bukti lebih mudah dengan mesin deterministik. Raphael keberatan dengan itu dalam komentar : " Saya biasanya menemukan pengurangan untuk masalah yang lebih sulit lebih mudah ". Memang, untuk banyak jenis automata, versi nondeterministic berfungsi terutama untuk menyederhanakan bukti, seperti pengurangan tipe otomat itu. Selain itu ada dua bentuk penghentian yang dapat digunakan, seperti yang disarankan oleh jmite sendiri, bahkan dapat dianggap sebagai keuntungan karena memberikan lebih banyak fleksibilitas untuk mengatasi masalah.

Pada definisi masalah penghentian nondeterministic

_{Catatan: penggunaan kata "universal" dalam teks berikut ini mengacu pada kuantifikasi universal , BUKAN ke mesin Turing universal}

The jawaban dari jmite adalah yang paling rinci.

Jawaban ini menduga bahwa automata nondeterministic membantu kurang upaya pada masalah penghentian karena dapat didefinisikan dalam dua cara yang berbeda (terminologi adalah milikku):

$M$ $x$
$M$ $x$

Satu-satunya definisi yang saya sarankan memadai adalah penghentian eksistensial .

$x$

Bukti : Ini mudah dibuktikan dengan lemma König , karena jumlah kemungkinan pilihan non-deterministik pada setiap langkah dibatasi untuk otomat yang diberikan. Jika ada banyak penghentian perhitungan yang tak terhingga, kita dapat memberi label setiap konfigurasi dengan masing-masing jalur komputasi yang mengarah ke sana, yang akan membuat grafik perhitungan dengan banyak sekali node, tetapi hanya bercabang nondeterministik hingga pada setiap node. Oleh lemma König, ini menyiratkan adanya jalur komputasi yang tak terbatas, yang sesuai dengan perhitungan yang tidak berhenti.

Kasus mesin Turing (nondeterministic)

Jadi sekarang, mari kita periksa penghentian dalam kasus mesin Turing nondeterministic (NTM).

Untuk menganalisis dua definisi tersebut, yang paling sederhana adalah dengan mempertimbangkan versi deterministik dari mesin non deterministik, yang dapat dicapai, seperti diingat oleh Hendrik Jan , dengan menggabungkan semua perhitungan yang mungkin.

Tetapi ada (setidaknya) dua cara perhitungan yang sesuai untuk penentuan, meskipun hanya satu yang biasanya dipertimbangkan:

determinasi dovetailing eksistensial yang mensimulasikan semua perhitungan secara paralel dan berakhir ketika salah satu perhitungan simulasi berakhir.
determinasi universal dovetailing yang mensimulasikan semua perhitungan secara paralel dan berakhir hanya ketika semua perhitungan simulasi berakhir. Tapi itu bisa saja menghitung dengan cara tertentu penghentian perhitungan, atau menghitungnya.

Proposisi 2 :

$M$ $x$ $M_\exists$ $x$
$M$ $x$ $M_\forall$ $x$

$M$ $x$ $M_\forall$ $x$

Teorema 3 : Masalah penghentian untuk deterministik TM, dan masalah penghentian eksistensial dan universal untuk TM nondeterministik adalah setara Turing.

Bukti : Ini hasil dari proposisi 2 dan dari fakta bahwa TM deterministik adalah subset dari TM non-deterministik, di mana keduanya berhenti eksistensial dan universal mengurangi menjadi berhenti deterministik sederhana.

Oleh karena itu, dari sudut pandang komputabilitas, dan saya tergoda untuk mengatakan dari sebuah simbol yang mendorong sudut pandang, tampaknya tidak terlalu penting definisi mana yang dipilih, eksistensial atau universal, untuk masalah penghentian nondeterministik.

Mengapa memilih satu definisi penghentian NTM, dan yang

Namun, apakah ada banyak arti bagi proses penentuan yang tidak mempertahankan bahasa yang dikenali oleh robot asli?

Esensi dari penggunaan nondeterminisme dalam pengenalan bahasa adalah bahwa ia mengasumsikan sebuah ramalan yang seharusnya menebak jalur komputasi yang tepat setiap kali ada yang akan mengarah pada penerimaan, pandangan eksistensial yang fundamental .

$\epsilon$

Dengan demikian penerimaan dengan penghentian dapat dilihat sebagai bentuk penerimaan kanonik untuk automata nondeterministic.

Mempertimbangkan pandangan kanonik ini, masalah penghentian juga dapat dinyatakan secara setara sebagai masalah pengakuan :

$L$ $M$ $x$ $x\in L$

$M$ $x$ $x$ $M$

Namun, dalam hal penghentian universal, hubungan dekat ini hilang. Pernyataan serupa dapat dibuat, tetapi untuk bahasa yang berbeda dari yang diakui oleh NTM (atau sebagai alternatif untuk definisi yang universal dan berbeda dari apa yang bahasa itu diakui oleh NTM).

Ketika mengembangkan teori, penting untuk menggunakan definisi yang konsisten untuk menekankan struktur dan hubungan dalam bentuk paling sederhana dan paling mudah dipahami. Cukup jelas bahwa dalam kasus ini, konsistensi dengan definisi lain menunjukkan bahwa penghentian eksistensial adalah definisi alami penghentian untuk mesin Turing nondeterministic.

$x$ $x$

Kasus keluarga automata lainnya

Bagian dari analisis di atas tidak dapat diperluas ke sebagian besar keluarga automata nondeterministic. Misalnya, pushdown atomaton (PDA) dapat mendefinisikan bahasa yang tidak dapat dikenali oleh PDA deterministik. Hal yang sama mungkin berlaku untuk LBA. Bagian lain dapat diperluas untuk semua keluarga nondeterministik.

Mengenai definisi penghentian nondeterministik, meskipun alasan yang digunakan dalam kasus mesin Turing mungkin tidak dapat digunakan, tampaknya satu-satunya pilihan yang masuk akal adalah mengadopsi definisi yang konsisten dengan yang digunakan untuk mesin Turing nondeterministik, maka definisi eksistensial .

Definisi masalah Henti untuk keluarga automata nondeterministik ini mengikuti, dan sesuai dengan definisi yang diajukan dalam pertanyaan.

babou
sumber

Menentukan masalah penghentian untuk automata non-deterministik

Jawaban:

Pendeknya

pengantar

Apakah masalah penghentian administrasi ditangani dengan baik?

Pada definisi masalah penghentian nondeterministic

Kasus mesin Turing (nondeterministic)

Mengapa memilih satu definisi penghentian NTM, dan yang

Kasus keluarga automata lainnya