Apa perbedaan antara non-determinisme dan keacakan?

Baru-baru ini saya mendengar ini -
"Mesin non-deterministik tidak sama dengan mesin probabilistik. Dalam istilah kasar, mesin non-deterministik adalah mesin probabilistik di mana probabilitas untuk transisi tidak diketahui".

Saya merasa seolah-olah saya mengerti maksudnya tetapi saya benar-benar tidak mengerti. Bisakah seseorang menjelaskan hal ini kepada saya (dalam konteks mesin atau secara umum)?

Sunting 1:
Hanya untuk memperjelas, kutipan itu dalam konteks otomat terbatas, tetapi pertanyaannya juga bermakna untuk mesin Turing seperti yang dijawab orang lain.

Juga, saya mendengar orang berkata - "... lalu saya memilih objek x dari set yang tidak ditentukan". Dulu saya pikir mereka maksud - "secara acak". Karena itu kebingungan.

Penting untuk dipahami bahwa para ilmuwan komputer menggunakan istilah "nondeterministic" secara berbeda dari bagaimana biasanya digunakan dalam ilmu lain. TM nondeterministic sebenarnya deterministik dalam pengertian fisika - artinya, NTM selalu menghasilkan jawaban yang sama pada input yang diberikan: ia selalu menerima, atau selalu menolak. TM probabilistik akan menerima atau menolak input dengan probabilitas tertentu, jadi pada satu kesempatan mungkin menerima dan pada yang lain ia mungkin menolak.

Secara lebih rinci: Pada setiap langkah dalam perhitungan yang dilakukan oleh NTM, alih-alih memiliki aturan transisi tunggal, ada beberapa aturan yang bisa dijalankan. Untuk menentukan apakah NTM menerima atau menolak, Anda melihat semua cabang perhitungan yang mungkin. (Jadi, jika ada, katakanlah, 2 transisi yang tepat untuk dipilih pada setiap langkah, dan setiap cabang perhitungan memiliki total N langkah, maka akan ada total bran untuk dipertimbangkan.) Untuk NTM standar, input diterima jika salah satu cabang perhitungan menerima.$2^N$

Bagian terakhir dari definisi ini dapat dimodifikasi untuk mendapatkan lainnya, jenis terkait mesin Turing. Jika Anda tertarik pada masalah yang memiliki solusi unik, Anda dapat meminta TM untuk menerima jika salah satu cabang menerima. Jika Anda tertarik pada perilaku mayoritas, Anda dapat menentukan TM untuk menerima jika lebih dari setengah cabang menerima. Dan jika Anda secara acak (menurut beberapa distribusi probabilitas) pilih salah satu cabang yang mungkin, dan terima atau tolak berdasarkan apa yang dilakukan cabang itu, maka Anda memiliki TM probabilistik.

Dalam konteks Mesin Turing, "non-deterministik" benar-benar berarti "paralel". Algoritma acak dapat secara acak menjelajahi cabang-cabang pohon perhitungan dari mesin Turing non-deterministik, tetapi mesin Turing non-deterministik dapat menjelajahi mereka -semua- pada saat yang sama, yang memberikan kekuatannya.

Dalam konteks lain (saya tidak tahu dari kutipan Anda jika Anda berbicara tentang Mesin Turing), suatu algoritma acak mungkin dengan sengaja menggunakan keacakan, sedangkan suatu algoritma yang Anda ingin menjadi deterministik mungkin pada akhirnya menunjukkan non-determinisme karena bug. ...

Menanggapi hasil edit Anda, ketika orang mengatakan "pilih elemen dari himpunan non-deterministik", mungkin saja itu berarti "secara acak". Namun, itu juga mungkin berarti "secara ajaib memilih elemen-kanan dari set". Cara umum untuk melihat mesin turing non-deterministik adalah bahwa mereka pertama kali secara ajaib "menebak" suatu solusi, dan kemudian memeriksa kebenarannya. Tentu saja, Anda dapat melihat tebakan ajaib ini hanya sebagai hasil dari memeriksa semua kemungkinan secara paralel.

Ada beberapa konteks yang berbeda di mana "deterministik", "acak" dan "non-deterministik" berarti tiga hal yang berbeda. Dalam konteks di mana terdapat banyak peserta, seperti keamanan dan konkurensi, intuisi sering kali seperti:

• deterministik berarti "Saya bisa memilih"

• non-deterministik berarti “orang lain dapat memilih”

• acak berarti "tidak ada yang bisa memilih"

Beberapa contoh:

1. [konkurensi, acak] Pertimbangkan protokol jaringan seperti Ethernet , tempat banyak node dapat mengirim pesan kapan saja. Jika dua node mengirim pesan pada interval yang sangat dekat, ada tabrakan: pesan tumpang tindih dan tidak dapat dibaca. Jika terjadi tabrakan, kedua node harus mencoba mengirim pesan lagi nanti. Bayangkan Anda sedang menulis spesifikasi Ethernet. Bagaimana Anda menentukan penundaan antar percobaan? (Penundaan sebaiknya berbeda atau akan ada tabrakan lagi!)

   • deterministic: mendefinisikan suatu algoritma yang harus digunakan oleh kedua node. Ini tidak dilakukan untuk Ethernet karena untuk memberikan hasil yang berbeda, algoritma harus mengistimewakan satu node di atas yang lain (untuk setiap konten pesan yang diberikan), dan Ethernet menghindari melakukan itu.

   • non-deterministik: biarkan setiap pelaksana memutuskan. Ini tidak baik karena pelaksana pada kedua node dapat memilih algoritma yang sama.

   • acak: setiap node harus memilih nilai penundaan secara acak (dengan distribusi yang ditentukan). Begitulah cara kerjanya. Ada kemungkinan kecil bahwa kedua node memilih penundaan yang sama dan ada tabrakan lain, tetapi probabilitas keberhasilan meningkat asimtotik menuju 1 ketika jumlah percobaan ulang meningkat.

2. [concurrency, nondeterministic] Anda menulis algoritma bersamaan. Dalam situasi tertentu, mungkin ada jalan buntu. Bagaimana Anda bisa mencegah kebuntuan terjadi? Itu tergantung pada jenis penjadwalan yang dimiliki lingkungan konkurensi Anda.

   • deterministik: penjadwal selalu beralih di antara utas pada titik tertentu yang ditetapkan dengan baik, misalnya hanya ketika kode menghasilkan secara eksplisit. Maka Anda cukup mengatur agar benang tidak menghasilkan pada saat yang buruk.

   • acak: penjadwal dijamin untuk mengganti utas secara acak. Maka strategi yang dapat dilakukan adalah mendeteksi kebuntuan jika terjadi, dan memulai kembali algoritma dari awal.

   • non-deterministic (kebanyakan penjadwal seperti ini): Anda tidak tahu kapan penjadwal akan beralih di antara utas. Jadi Anda benar-benar harus menghindari jalan buntu. Jika Anda mencoba mendeteksi dan memulai kembali seperti dalam kasus acak, Anda menjalankan risiko bahwa penjadwal akan menjadwalkan utas Anda dengan cara yang persis sama berulang-ulang.

3. [keamanan, acak] Anda menulis aplikasi dengan prompt kata sandi. Bagaimana Anda membuat model penyerang?

   • deterministik: penyerang selalu mencoba kata sandi yang sama. Itu sama sekali bukan model penyerang yang berguna - penyerang tidak dapat diprediksi oleh definisi.

   • nondeterministic: penyerang mengetahui kata sandi Anda dan memasukinya. Ini menunjukkan batasan kata sandi: kata sandi harus dirahasiakan. Jika kata sandi Anda rahasia, penyerang ini tidak realistis.

   • acak: penyerang mencoba kata sandi secara acak. Dalam hal ini, ini adalah model penyerang yang realistis. Anda dapat mempelajari berapa lama waktu yang dibutuhkan penyerang untuk menebak kata sandi Anda tergantung pada distribusi acak apa yang ia gunakan. Kata sandi yang baik adalah kata yang membutuhkan waktu lama untuk distribusi yang realistis.

4. [keamanan, tidak deterministik] Anda menulis aplikasi, dan Anda khawatir itu mungkin memiliki lubang keamanan. Bagaimana Anda membuat model penyerang?

   • deterministik: penyerang tahu semua yang Anda tahu. Sekali lagi, itu bukan model penyerang yang berguna.

   • acak: penyerang membuang sampah acak dan berharap program Anda macet. Itu kadang-kadang bisa berguna ( fuzzing ), tetapi penyerang mungkin lebih pintar dari itu.

   • non-deterministik: jika ada lubang, penyerang akan menemukannya pada akhirnya. Jadi Anda sebaiknya mengeraskan aplikasi Anda (meningkatkan persyaratan intelijen untuk penyerang; perhatikan bahwa karena ini merupakan persyaratan intelijen daripada persyaratan komputasi, ini dianggap sebagai non-deterministik sampai AI datang), atau lebih baik, buktikan bahwa tidak ada lubang keamanan dan karenanya penyerang seperti itu tidak ada.

Contoh untuk memperjelas:

Katakanlah Anda harus memilih pintu untuk membuka di antara 10.000 pintu (katakanlah ada hadiah di balik salah satu pintu). Memilih secara acak berarti Anda akan memilih satu dari 10.000 pintu dan memasukinya. Jika ada hadiah di balik hanya satu pintu, Anda kemungkinan besar tidak akan menemukannya. Mesin non-deterministik akan memasuki semua 10.000 pintu secara bersamaan. Jika ada hadiah di mana saja, mesin non-deterministik akan menemukannya.

Definisi Non-Deterministic Turing Machine : Mesin Turing yang memiliki lebih dari satu keadaan berikutnya untuk beberapa kombinasi konten sel saat ini dan keadaan saat ini. Input diterima jika urutan langkah apa pun mengarah ke penerimaan.

Definisi Probabilitistic Turing Machine : Mesin Turing nondeterministic (TM) yang secara acak memilih antara transisi yang tersedia di setiap titik sesuai dengan beberapa distribusi probabilitas.

Mesin Turing Probabilistic adalah Mesin Turing Non-Deterministik yang dapat membuat kesalahan.

PPT yang saya temukan bermanfaat.

Saya lebih suka definisi berikut:

Tidak ada yang namanya mesin Turing probabilistik!Hanya ada mesin deterministik (dalam setiap langkah satu negara tindak lanjut yang mungkin) dan mesin non-deterministik (dalam setiap langkah jumlah konstan kemungkinan negara tindak lanjut).

Non-determinisme bekerja sebagai berikut: Pertimbangkan mesin non-deterministik yang berhenti pada setiap input (mungkin jika masalah dapat ditentukan), di mana setiap perhitungan yang mungkin menggunakan jumlah langkah yang sama, dan di mana setiap langkah memiliki 2 kemungkinan tindak lanjut yang tepat ( keduanya bukan batasan). Seperti dalam definisi NP, mesin nondeterministic menerima input jika ada setidaknya satu kemungkinan menerima perhitungan, dan itu menolak input jika semua perhitungan menolak.

Keacakan berperan sebagai berikut: Anda dapat memilih secara acak satu jalur perhitungan dari mesin non-deterministik seperti yang dinyatakan di atas. Anda menerima jika dan hanya jika jalur perhitungan yang dipilih secara acak ini menerima. Pendekatan acak ini "memecahkan" masalah Anda jika, dengan probabilitas yang luar biasa, jawaban ini benar.

Jadi perbedaan antara non-determinisme dan keacakan adalah apakah Anda mencari keberadaan jawaban Ya yang benar (dan Tidak ada jawaban yang dapat diandalkan), atau apakah Anda tertarik untuk menyelesaikan masalah Anda "sebagian besar waktu" .

Sederhananya: mesin non-deterministik dapat secara optimal memilih hasil dari setiap flip koin (jika Anda menyukai analogi dengan mesin probabilistik). Anda mungkin juga membayangkan bahwa itu mengeksekusi perhitungan untuk setiap hasil dari flip koin secara paralel.

Melangkah mundur selama debugging sebagai motivasi untuk non-determinisme

Gagasan mesin non-deterministik menunjukkan dirinya ketika Anda ingin melangkah mundur (dalam waktu) melalui program saat debugging. Dalam komputer biasa, setiap langkah hanya memodifikasi jumlah memori yang terbatas. Jika Anda selalu menyimpan informasi ini untuk 10.000 langkah sebelumnya, maka Anda dapat melangkah maju dan mundur dengan baik dalam program ini, dan kemungkinan ini tidak terbatas pada program mainan. Jika Anda mencoba untuk menghapus asimetri antara langkah maju dan langkah mundur, maka Anda berakhir dengan gagasan tentang mesin non-deterministik.

Persamaan dan perbedaan antara non-determinisme dan keacakan

Sementara mesin probabilistik berbagi beberapa karakteristik dengan mesin non-deterministik, simetri antara langkah maju dan langkah mundur ini tidak dibagi. Untuk melihat ini, mari kita memodelkan langkah-langkah atau transisi dari mesin deterministik dengan fungsi (total atau parsial), transisi mesin non-deterministik oleh hubungan (terbatas), dan transisi mesin probabilistik oleh (sub) matriks stokastik . Misalnya, berikut adalah definisi yang sesuai untuk automata terbatas

• $Q$
• $\Sigma$
• $\delta:Q\times \Sigma \to Q$
• $\Delta:Q\times \Sigma \to P(Q)$
• $\Delta\subset Q\times \Sigma \times Q$
• $\Delta: \Sigma \to P(Q \times Q)$
• $\delta: \Sigma \to ssM(Q)$

$P(Q)$$Q$$ssM(Q)$$Q$ . Matriks substokastik kanan adalah matriks nyata non negatif, dengan setiap baris dijumlahkan paling banyak 1.

Ada berbagai kondisi penerimaan yang masuk akal

Transisi hanya satu bagian dari mesin, keadaan awal dan akhir, kemungkinan keluaran dan kondisi penerimaan juga penting. Namun, hanya ada sedikit kondisi penerimaan non-ekivalen untuk mesin deterministik, sejumlah kondisi penerimaan yang masuk akal untuk mesin non-deterministik (NP, coNP, #P, ...), dan banyak kemungkinan kondisi penerimaan untuk mesin probabilistik. Karenanya jawaban ini terutama berfokus pada transisi.

Reversibilitas bersifat non-sepele untuk mesin probabilistik

$P P^T P\neq P$$P$$B$$A$$k$$A$$B$$k$ langkah mundur . Setiap jalur dari A ke B memiliki kemungkinan maju dan mundur yang sama. Jika kondisi penerimaan yang sesuai (dan kondisi batas lainnya) dipilih, maka matriks substokastik ganda adalah gagasan yang tepat tentang reversibilitas untuk mesin probabilistik.

Reversibilitas itu rumit bahkan untuk mesin non-deterministik

$P P^T P\neq P$$R\circ R^{op}\circ R \neq R$$R$$R$$R\circ R^{op}\circ R = R$$R^{op}\circ R\circ R^{op} = R^{op}$$P$$Q$$P\circ Q$

Pertimbangan ini juga masuk akal untuk automata pushdown

Posting ini menunjukkan bahwa satu motivasi untuk non-determinisme adalah untuk menghilangkan asimetri antara langkah maju dan langkah mundur. Apakah simetri non-determinisme ini terbatas pada automata terbatas? Berikut adalah definisi simetris yang sesuai untuk automata pushdown

• $Q$
• $\Sigma$
• $\Gamma$
• $\delta:Q\times\Gamma\times (\Sigma\cup\{\epsilon\}) \to Q\times\Gamma^{\{0,2\}}$$\delta(q,\gamma,\epsilon)\neq\epsilon$$\delta(q,\gamma,\sigma)=\epsilon$$\sigma\in\Sigma$
• $\Delta:Q\times\Gamma^{\{0,1\}}\times (\Sigma\cup\{\epsilon\}) \to P(Q\times\Gamma^{\{0,1\}})$
• $\Delta\subset Q\times\Gamma^{\{0,1\}}\times (\Sigma\cup\{\epsilon\}) \times Q\times\Gamma^{\{0,1\}}$
• $\Delta: \Sigma\cup\{\epsilon\} \to P(Q\times\Gamma^{\{0,1\}}\ \times\ Q\times\Gamma^{\{0,1\}})$
• $\delta: \Sigma\cup\{\epsilon\} \to ssM(Q\times\Gamma^{\{0,1\}})$$\delta(\epsilon)+\delta(\sigma)\in ssM(Q\times\Gamma^{\{0,1\}})$$\sigma\in\Sigma$

Sini $\epsilon$$\Gamma^{\{0,2\}}=\{\epsilon\}\cup\Gamma\cup(\Gamma\times\Gamma)$$\Gamma^{\{0,1\}}=\{\epsilon\}\cup\Gamma$$\Gamma^*$

Verifikasi pembalikan diagram untuk operasi input dan stack yang maju

$b\in\Sigma\subset\Sigma\cup\{\epsilon\}$

$a|bc \to a|\boxed{b}c \to ab|c$
$a|bc \leftarrow a\boxed{b}|c \leftarrow ab|c$
$c|ba \to c|\boxed{b}a \to cb|a$

$\epsilon\in\Sigma\cup\{\epsilon\}$

$a|bc \to a|bc \to a|bc$
$a|bc \leftarrow a|bc \leftarrow a|bc$
$cb|a \to cb|a \to cb|a$

Here is a diagram of an advancing input operation whose reversal would look bad

$\require{cancel}\xcancel{\begin{matrix} a|bc \to \boxed{a}|bc \to ab|c\\ a|bc \leftarrow \boxed{a}b|c \leftarrow ab|c\\ c|ba \to c|b\boxed{a} \to cb|a \end{matrix}}$

For a stack operation $(s,t) \in \Gamma^{\{0,1\}}\times\Gamma^{\{0,1\}}$, there are the three cases $(s,t)=(a,\epsilon)$, $(s,t)=(\epsilon,a)$, and $(s,t)=(a,b)$. The stack operation $(a,\epsilon)$ gets reversed to $(\epsilon,a)$ as follows

$ab\ldots \to \boxed{a}b\ldots \to |b\ldots$
$\boxed{a}b\ldots \leftarrow |b\ldots \leftarrow b\ldots$
$b\ldots \to |b\ldots \to \boxed{a}b\ldots$

The stack operation $(a,b)$ gets reversed to $(b,a)$ as follows

$ac\ldots \to \boxed{a}c\ldots \to \boxed{b}c\ldots$
$\boxed{a}c\ldots \leftarrow \boxed{b}c\ldots \leftarrow bc\ldots$
$bc\ldots \to \boxed{b}c\ldots \to \boxed{a}c\ldots$

A generalized stack operation $(ab,cde)\in\Gamma^*\times\Gamma^*$ would be reversed to $(cde,ab)$

$abf\ldots \to \boxed{ab}f\ldots \to \boxed{cde}f\ldots$
$\boxed{ab}f\ldots \leftarrow \boxed{cde}f\ldots \leftarrow cdef\ldots$
$cdef\ldots \to \boxed{cde}f\ldots \to \boxed{ab}f\ldots$

Reversibility for Turing machines

A machine with more than one stack is equivalent to a Turing machine, and stack operations can easily be reversed. The motivation at the beginning also suggests that reversal (of a Turing machine) should not be difficult. A Turing machine with a typical instruction set is not so great for reversal, because the symbol under the head can influence whether the tape will move left or right. But if the instruction set is modified appropriately (without reducing the computational power of the machine), then reversal is nearly trivial again.

A reversal can also be constructed without modifying the instruction set, but it is not canonical and a bit ugly. It might seem that the existence of a reversal is just as difficult to decide as many other question pertaining to Turing machines, but a reversal is a local construction and the difficult questions often have a global flavor, so pessimism would probably be unjustified here.

The urge to switch to equivalent instruction sets (easier to reverse) shows that these questions are less obvious than they first appear. A more subtle switch happened in this post before, when total functions and stochastic matrices were replaced by partial functions and substochastic matrices. This switch is not strictly necessary, but the reversal is ugly otherwise. The switch to the substochastic matrices was actually the point where it became obvious that reversibility is not so trivial after all, and that one should write down details (as done above) instead of taking just a high level perspective (as presented in the motivation at the beginning). The questions raised by Niel de Beaudrap also contributed to the realization that the high level perspective is slightly shaky.

Conclusion

Non-deterministic machines allow a finite number of deterministic transitions at each step. For probabilistic machines, these transitions additionally have a probability. This post conveys a different perspective on non-determinism and randomness. Ignoring global acceptance conditions, it focuses on local reversibility (as a local symmetry) instead. Because randomness preserves some local symmetries which are not preserved by determinism, this perspective reveals non-trivial differences between non-deterministic and probabilistic machines.

In the context of Turing Machines (TMs) and automata theory, a non-deterministic machine is one in which any instantiation of the machine which accepts is fine. In this sense, it is like running multiple deterministic machines in parallel and take the output of any instances that accept the input. In fact there is a (deterministic) algorithm to transform any non-deterministic automaton (with $n$ states) into an equivalent deterministic one (with $2^n$ states, exponential) by considering equivalence classes of states, no matter if the algorithm implemented in the machine involves randomisation or probabilities (see below).

But if the algorithm implemented in the machine, involves randomisation or probabilities (intrinsic in the algorithm), then it is a randomised (or probabilistic) machine.

In general, it is always possible to remove non-determinism from a machine and construct a deterministic equivalent (see algorithm above), but the same cannot be done (in general) to remove randomisation (in the context of the above) because it is intrinsic to the algorithm implemented.

Note that in the light of the above, both a deterministic machine and a non-deterministic machine can be probabilistic if the algorithm (involved) uses randomisation (or probabilities) in this way.

To sum up, non-determinism in automata (in this context) refers to classes of similar automata, while randomisation or probabilistic machines refer to the (intrinsic application of randomisation in the) actual algorithms implemented by these automata.