Saya menyadari automata pushdown non-deterministik dapat menjadi perbaikan daripada yang deterministik karena mereka dapat "memilih" di antara beberapa negara dan ada beberapa bahasa bebas konteks yang tidak dapat diterima oleh pushdown deterministik.

Meski begitu, saya tidak mengerti bagaimana tepatnya mereka "memilih". Untuk palindormes misalnya setiap sumber yang saya temukan hanya mengatakan otomat "menebak" di tengah kata. Apa artinya?

Saya dapat memikirkan beberapa kemungkinan arti:

1. Ini masuk ke satu negara secara acak dan karena itu mungkin tidak menerima sepatah kata pun, yang sebenarnya dalam bahasa

2. Entah bagaimana itu berlaku "segala cara yang mungkin", jadi jika yang pertama salah itu menguji apakah yang lain mungkin benar

3. Ada beberapa mekanisme yang saya tidak sadari, yang memilih kata tengah dan karena itu tidak acak, tetapi robot selalu menemukan bagian tengah yang benar.
   

Ini hanya sebuah contoh; apa yang ingin saya ketahui adalah cara kerjanya untuk setiap robot yang memiliki beberapa status berikut untuk satu dan kondisi yang sama sebelumnya.

Sederhananya, mekanismenya adalah sihir. Gagasan non-determinisme adalah bahwa ia hanya tahu ke mana ia harus mengambil untuk menerima kata, dan ia pergi seperti itu. Jika ada beberapa cara, itu salah satunya.

Non-determinisme tidak dapat diimplementasikan seperti itu di perangkat keras nyata. Kami mensimulasikannya menggunakan teknik seperti backtracking. Tapi itu terutama perangkat teoritis, yang dapat digunakan untuk menyederhanakan presentasi konsep-konsep tertentu.

Untuk palindrome, Anda dapat memikirkannya dalam dua cara. Entah ada kekuatan magis yang memungkinkan mesin Anda mengatakan "ini adalah kata tengah, waktu untuk beralih dari mendorong ke bermunculan", atau setelah membaca setiap huruf, dikatakan "Aku akan melakukan proses baru di mana surat ini adalah kata tengah, dan lihat apakah kata itu palindrom. Kemudian di utas lainnya, saya akan terus mencoba, dengan asumsi ini bukan kata tengah ".

Cara lain untuk memikirkannya adalah sebagai paralelisme tanpa batas. Jadi model yang setara adalah bahwa, alih-alih memilih jalan baru, secara bersamaan mencoba kedua jalur, bercabang dari "proses," berhasil jika ada dalam keadaan akhir setelah membaca seluruh kata. Sekali lagi, ini tidak dapat dibangun menggunakan perangkat keras nyata, tetapi dapat dimodelkan dengan non-determinisme.

Hal yang menarik tentang nondeterminisme adalah bahwa untuk finite-automata dan mesin Turing, itu tidak meningkatkan daya komputasi mereka sama sekali, hanya efisiensi mereka.

Perbedaan utama (menurut saya) antara otomat deterministik dan otomat non-deterministik adalah bahwa untuk otomat deterministik kata input yang diberikan hanya memiliki satu jalur melalui mesin. Dalam otomat non-deterministik, kata input yang diberikan mungkin memiliki banyak jalur melalui mesin (karena mungkin ada pilihan di beberapa titik).

Mengingat hal ini, kondisi untuk penerimaan kata input juga perlu diubah untuk mengakomodasi fakta bahwa sebuah kata dapat menginduksi beberapa jalur melalui mesin. Definisi penerimaan yang biasa untuk otomat non-deterministik adalah sebagai berikut: Agar sebuah kata diterima oleh otomat harus ada setidaknya satu jalur penerimaan yang diinduksi oleh kata itu.

Ini kemudian mengarah pada ide otomat "tebak," jika sebuah kata diterima oleh otomat non-deterministik maka kita cenderung menganggap automaton itu secara otomatis membuat pilihan yang tepat sehingga (salah satu) jalur penerimaan menerima diikuti ketika kata itu disajikan sebagai input.

Apa artinya ini untuk palindrom adalah bahwa pda pada dasarnya akan memiliki dua mode: mode mendorong di mana ia mendorong huruf saat ini di tumpukan dan mode muncul di mana ia mengeluarkan huruf-huruf itu dan mencocokkannya dengan input. Mesin ini akan memiliki transisi kosong dari negara mendorong ke negara muncul yang akan dapat diikuti pada setiap titik dalam kata. Namun mesin hanya akan mengosongkan tumpukannya dan pindah ke status terima jika telah membaca palindrom dan mengikuti transisi kosong di tengah palindrom. Karena kita hanya membutuhkan keberadaan jalur penerimaan, kita dapat mengatakan bahwa otomat "menebak" di mana kata tengah berada.

Gagasan nondeterminisme cukup sederhana: robot mungkin memiliki beberapa langkah berikutnya dalam situasi tertentu. Otomat menerima jika ada beberapa (mungkin ada beberapa!) Urutan langkah-langkah yang mengarah dari konfigurasi awal ke yang menerima, ia menolak hanya jika tidak ada urutan seperti itu.

Ini berarti "memutuskan" langkah mana yang harus diambil selanjutnya dalam situasi ambigu tersebut. Salah satu cara untuk membicarakan hal ini adalah dengan mengatakannya secara ajaib memilih langkah "benar" berikutnya yang selalu (atau satu, jika ada beberapa langkah "benar"). Cara lain untuk melihatnya adalah dalam situasi seperti itu perhitungan otomat terbagi menjadi beberapa salinan, masing-masing mengejar satu jalur.

Dalam praktiknya, ini dapat diimplementasikan dengan menelusuri ulang, menempatkan beberapa bentuk tag di tempat-tempat pengambilan keputusan, dan kembali dan mencoba alternatif berikutnya jika jalur saat ini tidak berhasil. Ini biasanya ditangani dengan rekursi. Atau melengkapi informasi yang telah "secara hukum" automaton dengan informasi tambahan (itulah yang Anda lakukan ketika Anda menunjukkan bagaimana otomat non-deterministik bekerja di papan tulis, melihat ke depan dan mencari tahu langkah-langkah mana yang mengarah pada kesuksesan).

"Menebak" secara langsung berkaitan dengan interpretasi eksistensial kita tentang non-determinisme

Singkatnya: Gagasan bahwa robot non-deterministik dapat menebak (atau dibantu oleh oracle) secara langsung berkaitan dengan interpretasi eksistensial kita tentang non-determinisme. Interpretasi lain mungkin (mungkin orang lain) di mana "menebak" tidak masuk akal.

Non determinisme itu aneh. Kami memang memiliki satu cara untuk mengartikannya dalam teori automata, tetapi tidak jelas bagaimana kita seharusnya melakukan itu.

Ini mungkin tampak mengejutkan, tetapi non-determinisme adalah situasi yang sangat umum. Ketika seseorang harus membuktikan teorema, mengingat aksioma dari beberapa teori matematika, proses secara alami adalah non deterministik. Itulah sebabnya kita sering tidak tahu apa yang harus dilakukan untuk menyelesaikan masalah, misalnya untuk menemukan solusi persamaan derajat ketiga, atau membuktikan beberapa teorema.

Ada banyak cara untuk menggabungkan apa yang sudah diketahui dengan aturan inferensi untuk mendapatkan hasil baru. Dan situasinya biasanya sama jika kita mencoba merekonstruksi bukti mundur dari hasilnya.

Saat mencoba menyelesaikan masalah seperti itu, kami mencoba " menebak " jalan di beberapa sistem transisi.

Sebenarnya, kita tidak menebak, tetapi membangun dalam pikiran kita beberapa struktur yang mengatur dan / atau menyederhanakan labirin kemungkinan sehingga kita dapat melihat jalan kita melewatinya. Dalam beberapa kasus, pertanyaannya mengikuti pola yang diidentifikasi yang kami punya cara standar untuk (kadang-kadang? Biasanya? Selalu?) Menemukan solusi, dan kami menyebutnya algoritma.

Salah satu teknik (biasanya mahal) yang dapat kita gunakan adalah hanya untuk sepenuhnya menjelajahi labirin: untuk mengikuti semua jalur, melakukannya terlebih dahulu untuk menghindari terperangkap dalam subgraph tak terbatas. Ini adalah apa yang sedang dilakukan dengan menggabungkan semua kemungkinan perhitungan otomat non-deterministik. Komputasi dovetailed turunan ini sendiri merupakan deterministik.

$DC$$A$$A$$A$

Sebenarnya, mungkin ada berbagai cara menafsirkan perhitungan non-deterministik . Afaik mereka semua konsisten, tetapi tidak dengan satu sama lain.

$R$$w$

Gagasan menebak untuk pengenal hanyalah gambar yang diambil dari cara kita sendiri "menebak" bagaimana menemukan pohon bukti itu. Tetapi perbedaan besar adalah bahwa otak kita bukanlah PDA. Mereka adalah perangkat yang jauh lebih kompleks dengan kemampuan untuk mengeksplorasi dan memetakan sekitar struktur transisi sehingga kita dapat menemukan jalan kita melalui mereka, yang kadang-kadang kita anggap sebagai menebak.

Interpretasi perhitungan non-deterministik ini adalah apa yang saya sebut penerimaan eksistensial , mengacu pada fakta bahwa ia hanya membutuhkan keberadaan satu komputasi yang menerima. Ini sesuai dengan penghentian eksistensial yang saya perkenalkan pada jawaban lain .

Namun, kita juga bisa menafsirkan non-determinisme dengan cara universal sebagai: pengenal dikatakan (secara universal) menerima input "w" jika semua perhitungan yang mungkin dihentikan dan menerima input. Penerimaan universal ini sesuai dengan konsep penghentian universal yang diperkenalkan dalam jawaban yang sama.

Penerimaan universal, dan penghentian universal tampaknya mengarah pada pemahaman yang konsisten tentang non-determinisme. Karena itu orang dapat melakukan pekerjaan teoretis dengan definisi itu. Tetapi ini tidak konsisten dengan praktik yang biasa kita lakukan dalam banyak situasi non-deterministik seperti pembuktian teorema, atau dalam situasi kehidupan sehari-hari. Ketika dihadapkan dengan masalah, kami hanya ingin satu cara menyelesaikannya, dan kemudian tidak peduli apakah cara lain berhasil atau tidak (nah ini sedikit disederhanakan).

Jika kita harus mengenali palindrome, kita bisa menebak dengan mengukur panjang dan mencari tengah. PDA tidak bisa. Tapi, karena kita hanya tertarik pada adanya satu solusi, kita selalu bisa berpura-pura bahwa itu bisa ... jika itu akan membantunya. Atau kita dapat menganggap bahwa ia memiliki nubuat yang disediakan oleh mesin yang lebih cerdas (kita?) Untuk membantunya. Atau Anda bahkan dapat menyebutnya sihir, dan berpikir itu adalah (setelah semua, kuantifier eksistensial adalah semacam tongkat sihir). Jika itu bisa membantu, itu akan membantu. Jika tidak ada perhitungan penerimaan, tidak ada bantuan apa pun yang akan digunakan.

Perhatikan bahwa gagasan menebak ini tidak akan ada artinya dalam interpretasi penerimaan universal.