Mengapa non-determinisme merupakan konsep yang bermanfaat?

23

Otomat adalah model abstrak dari komputer digital. Komputer digital sepenuhnya deterministik; status mereka kapan saja dapat diprediksi secara unik dari input dan kondisi awal.

Ketika kita mencoba memodelkan sistem nyata, mengapa memasukkan nondeterminisme dalam teori Automata?

tanmoy
sumber
1
Mungkin akan membantu untuk menanyakan siapa yang awalnya menggambarkan NTM dan apa tujuan / tujuannya pada saat itu.
usul
2
Perhatikan bahwa fakta bahwa mesin itu deterministik tidak selalu berarti kode kita. Siapa pun yang melakukan multitasking / multithreading dapat membuktikan fakta bahwa saat-saat di mana pengalihan tugas sering kali tidak dapat diprediksi dalam istilah praktis apa pun dan kami harus merancang interlock secara eksplisit untuk membuat perilakunya tampak deterministik. (Pada dasarnya, ada variabel tersembunyi di negara bagian.) Komunikasi menimbulkan masalah yang sama. Jujur saya tidak tahu apakah NDA membantu mengatasi ini - saya seorang insinyur perangkat lunak, bukan ilmuwan komputer - tetapi di dunia nyata premis Anda terlalu optimis.
keshlam
Ketika Anda berbicara tentang multithreading, bisa dibilang, Anda memiliki non-determinisme, setidaknya jika Anda mempertimbangkan logam dan OS untuk membentuk mesin. Yang lucu adalah bahwa kode itu sendiri bersifat deterministik.
Raphael
@ Raphael, @keshlam Dengan kata lain kita dapat mengatakan bahwa "model non-deterministik juga berguna untuk mensimulasikan eksekusi kode secara paralel"
Grijesh Chauhan
@keshlam Saya menambahkan poin Anda dalam jawaban saya, @ Tanmoy baca memperbarui jawaban saya
Grijesh Chauhan

Jawaban:

16

Ya, Anda benar bahwa komputer adalah otomatisasi deterministik. Model non-deterministik lebih berguna untuk tujuan teoretis, kadang-kadang solusi deterministik tidak sejelas definisi (atau mengatakan pernyataan masalah) dan sedikit sulit untuk menemukan solusi. Kemudian satu pendekatan adalah bahwa pertama merancang model non-deterministik yang mungkin relatif mudah untuk dirancang dan kemudian mencoba mengubahnya menjadi model deterministik. Di bawah, saya telah mencoba menunjukkan apa yang saya maksud dengan contoh. Pertimbangkan ekspresi reguler:

(01)*01(0 + 1)*  

Sekarang anggaplah, jika Anda diminta untuk menggambar DFA untuk bahasa yang dihasilkan oleh RE di atas.

Dengan pengetahuan saya dalam mendesain FA, saya tahu bahwa (1) ketika sebuah *present dalam ekspresi reguler mengindikasikan bahwa saya memerlukan loop yang sesuai dalam FA (2) operasi gabungan seperti a.bberarti sesuatu seperti:(q0)─a→(q1)─b→(q2) .

Jadi, pada usaha pertama saya, saya akan menggambar NFA seperti:

fig

Berpikir ini bukan solusi deterministik tetapi terlihat FA sangat sederhana yang dapat dengan mudah dirancang menggunakan ekspresi reguler yang diberikan. Jenis analogi saya untuk menunjukkan kesamaan antara ekspresi reguler di atas dan NFA saya adalah sebagai berikut:

  1. Loop pada state q 0 seharusnya untuk(01)*
  2. 01(setelah (01)*) memberi(q0)─0→(q1)─1→(q2)
  3. (0 + 1)* memberikan loop diri pada keadaan q 2 untuk label 0, 1

Menurut analogi saya, saya pikir FA yang saya gambar di atas relatif mudah untuk diambil dari RE yang diberikan. Dan untungnya di kelas automata terbatas setiap model Non-deterministik dapat dikonversi menjadi model deterministik yang setara. Kami memiliki metode algoritmik untuk mengubah NFA menjadi DFA . Jadi saya dapat dengan mudah mengkonversi NFA di atas menjadi DFA:

fig-2

Bagian lain sayangnya ini tidak selalu memungkinkan untuk mengubah model non-deterministik menjadi model deterministik, misalnya kelas untuk deterministic push down automate adalah subset dari kelas deterministic push-down automate "periksa diagram venn " dan Anda tidak selalu dapat mengonversi NPDA menjadi PDA.

Biasanya ketika tidak mungkin untuk mengubah solusi non-deterministik menjadi solusi deterministik maka dengan bantuan solusi non-deterministik kami mendefinisikan solusi deterministik dalam sub-domain (atau katakanlah domain parsial) alih-alih domain lengkap. Atau kami mendefinisikan solusi dengan beberapa cara lain (misalnya pendekatan serakah) yang tentu saja tidak dapat memberi Anda solusi optimal .

Terkadang non-determinisme adalah mekanisme yang efektif untuk menggambarkan beberapa masalah / solusi rumit secara tepat dan efektif, sebagai contoh mesin non-deterministik dapat berfungsi sebagai model algoritma pencarian-dan-lacak (baca: Bagaimana proses string dalam model non-deterministik menggunakan backtrack ). Model deterministik berlawanan lebih baik mewakili solusi yang efisien, diminimalkan dan kurang redundan.

Di sini saya juga ingin mengutip dari Wikipedia Penggunaan algoritma Nondeterministic :

Dalam desain algoritma, algoritma nondeterministic sering digunakan ketika masalah diselesaikan oleh algoritma yang secara inheren memungkinkan hasil ganda (atau ketika ada hasil tunggal dengan beberapa jalur dimana hasilnya dapat ditemukan, masing-masing sama-sama lebih disukai). Yang terpenting, setiap hasil yang dihasilkan algoritma nondeterministic valid, terlepas dari pilihan mana yang dibuat algoritma saat berjalan.

Sejumlah besar masalah dapat dikonseptualisasikan melalui algoritma nondeterministic, termasuk pertanyaan yang paling tidak terselesaikan dalam teori komputasi, P vs NP.

Seperti @keshlam juga disebutkan dalam komentarnya : "Nondeterminism" dalam praktiknya digunakan untuk merujuk pada setiap ketidakpastian dalam hasil dari beberapa proses. Sebagai contoh, program bersamaan menunjukkan perilaku non-deterministik - dua eksekusi program yang sama dengan input yang sama dapat menghasilkan hasil yang berbeda (jika mekanisme kontrol konkurensi tidak diterapkan). Baca lebih lanjut tentang ini di "Kegunaan Non Determinisme" .

Saya juga menyarankan Anda untuk membaca tautan berikut:
1. Apa perbedaan antara non-determinisme dan keacakan?
2. 9.2.2 Model Nondeterministic vs. Probabilistic: (a). Nondeterministic: Saya tidak tahu apa yang akan dilakukan alam. (b). Probabilistik: Saya mengamati alam dan mengumpulkan statistik.
3. pemrograman nondeterministic

Grijesh Chauhan
sumber
@Grijest: terima kasih banyak untuk penjabaran yang sangat besar. Hanya satu kebingungan: "Model deterministik yang berlawanan lebih baik mewakili solusi yang efisien, diminimalkan dan kurang redundan." - Tapi saya pikir model deterministik kurang efisien daripada yang non-deterministik. lebih kompleks dari P. bukan?)
tanmoy
@tan Sebenarnya menggunakan kata "efisien" itu salah, Dan Ya, Anda benar bahwa model non-deterministik lebih mampu daripada yang deterministik. Kelas masalah yang dicakup oleh model deterministik adalah subset dari model Non-deterministik.
Grijesh Chauhan
jadi di mana model deterministik konteks "efisien" daripada yang nondeterministic (Seperti yang Anda sebutkan)?
tanmoy
@tan Misalkan jika Anda ingin melakukan operasi lebih lanjut (misalnya ingin mengubah FA ke RE, atau menjelaskan bukti untuk memompa lemma, atau lainnya ..) maka model Deterministic memberikan hasil yang lebih baik (jadi saya katakan efisien).
Grijesh Chauhan
@tan Apakah Anda mengerti tata bahasa yang ambigu?
Grijesh Chauhan
9

Ini lebih sebaliknya: automata muncul lebih dulu, sebagai model matematika. Dan nondeterminisme cukup alami, Anda sering memiliki beberapa jalur terbuka sebelum Anda. Alih-alih cara berantakan menentukan bahwa semua jalur harus diikuti sampai akhir dalam urutan tertentu, dan mungkin terjebak oleh cabang-cabang yang tak terbatas, dan ... hanya menggunakan nondeterminisme.

Dan sementara bahasa pemrograman nondeterministik bukan arus utama, mereka memiliki sejarah yang termasyhur, mungkin dimulai dengan GCL Dijkstra . Ketika mesin semakin banyak core (prosesor independen), beberapa bentuk nondeterminisme merembes ke semua pemrograman.

vonbrand
sumber
Saya pikir bagian pertama dari jawaban Anda secara faktual salah. Menurut Anda mengapa automata muncul lebih dulu? Baik DFA dan NFA didefinisikan 10+ tahun setelah Turing mendefinisikan TM. Lihat diskusi tentang sejarah
Artem Kaznatcheev
@ArtemKaznatcheev, model mesin Turing adalah automaton, dan sudah pasti ada sebelum komputer paling tidak satu dekade.
vonbrand
ya, tetapi ketika orang mengatakan automata mereka tidak bermaksud TM tetapi mereka berarti automata keadaan terbatas dan ekstensi langsungnya (PDA, NPDA, dll.). Lihat pertanyaan yang saya tautkan untuk sejarah di sana dan Anda akan melihat bahwa TM dan arsitektur von Neumann dikembangkan secara independen dari apa yang sekarang kita sebut teori automata.
Artem Kaznatcheev
4
@ArtemKaznatcheev, DFA / NFA, PDA, LBA, TM semuanya automata. Seperti halnya transduser (FA dengan output, PDA dengan output).
vonbrand
1
Paragraf terakhir salah. Prolog mendahului GCL, dan bahkan masih ada dan cukup umum. Prolog tentu saja tidak dirancang dalam ruang hampa, membangun pada bahasa pemrograman nondeterministik sebelumnya seperti PLANNER. Penghargaan mungkin jatuh pada Golomb dan Baumert "Backtrack Programming" mulai tahun 1965.
Nama samaran
7

NFA mungkin digunakan dalam praktik, periksa jawaban ini di stackexchange. Alasannya adalah bahwa konstruksi powerset dapat disimulasikan secara langsung. Untuk mensimulasikan NFA pada komputer deterministik, kami hanya melacak kemungkinan bahwa NFA bisa masuk. Biasanya, jumlah ini akan kecil, sehingga simulasi akan cepat. Ini jauh lebih praktis daripada menjalankan konstruksi powerset yang sebenarnya: otomat yang dihasilkan bisa sangat besar, meskipun dalam praktiknya sebagian besar set jarang akan tercapai.

Nondeterminisme juga penting untuk kompleksitas komputasi, di mana ia digunakan untuk mendefinisikan NP kelas. (Kelas NP juga memiliki definisi lain yang setara, misalnya menggunakan saksi.)

Yuval Filmus
sumber
memahami jawaban Anda tetapi tidak bisa menangkapnya dengan benar. Bisakah Anda menguraikan fakta bahwa bagaimana konstruksi powerset dapat dilakukan dengan mudah menggunakan nondeterminisme?
tanmoy
"Nondeterminisme juga penting untuk kompleksitas komputasi, di mana ia digunakan untuk mendefinisikan NP kelas." - yang mendukung pentingnya non-determinisme hanya jika kita mengasumsikan bahwa NP adalah konsep yang berguna, yang hanya jika non-determinisme berguna.
Raphael
Kelengkapan NP @Raphael adalah konsep penting terlepas dari sikap Anda tentang non-determinisme.
Yuval Filmus
2
@Tanmoy Jika Anda memiliki nondeterminisme Anda tidak memerlukan konstruksi powerset, tetapi sayangnya komputer nyata adalah deterministik. Namun demikian, mungkin lebih mudah untuk mensimulasikan NFA secara langsung daripada mengubahnya menjadi DFA terlebih dahulu. Lihat jawaban yang saya tautkan untuk lebih jelasnya.
Yuval Filmus
4

Anda menyatakan dengan benar bahwa automata adalah model, jadi ada dua bagian penggunaan yang tidak dapat ditentukan:

  1. Gunakan dalam pemodelan masalah nyata.

    Tidak semua automata sama kuatnya jika Anda menghapus nondeterminisme, misalnya pushdown automata (CFL DCFL). Jadi, sementara kita harus mensimulasikan NPDA secara deterministik pada akhirnya, yaitu ketika kita benar-benar mengimplementasikan parser, kita perlu sebagai model untuk beberapa bahasa.

    Selain itu, automata non-deterministik dapat memberikan representasi bahasa yang lebih kompak. Sebagai contoh, sudah diketahui bahwa ada NFA yang minimal DFA-nya setara secara eksponensial lebih besar.

  2. Gunakan secara teori.

    Menggunakan non-determinisme dapat menyederhanakan bukti, lihat misalnya mengubah ekspresi reguler menjadi automata terbatas.

Raphael
sumber
4

(Ini adalah penulisan ulang dari beberapa jawaban lain tetapi saya tetap akan mempostingnya :)

Anda menulis: Otomat adalah model abstrak dari komputer digital.

Saya tidak setuju! Automata memodelkan bagaimana kita manusia menentukan komputasi, bukan hanya bagaimana komputer menjalankannya. Ketidakpastian adalah perbedaannya. Spesifikasi kami sering tidak deterministik.

Misalnya, ambil semacam penggabungan . Sortir gabungan adalah penyortiran dengan memisahkan item yang akan diurutkan menjadi dua bagian dengan ukuran yang kira-kira sama, menyortir setiap bagian menggunakan gabungan, dan menggabungkan hasil yang diurutkan. Ini benar-benar menentukan ide penggabungan, tetapi tidak deterministik: tidak menentukan urutan untuk menyortir bagian (untuk semua yang kami pedulikan, mungkin dilakukan bersamaan), juga tidak menentukan cara yang tepat untuk tentukan split. Detail tersebut perlu diisi untuk sampai pada versi deterministik, sekuensial dari gabungan yang dapat diimplementasikan oleh program komputer single-threaded, tapi saya akan mengatakan mereka adalah bagian dari cara tertentu dalam melakukan penggabungan, bukan ide menggabungkan semacam itu sendiri.

Hal yang sama berlaku untuk algoritma secara umum - misalnya resep buku resep. Beberapa orang mendefinisikan algoritma sebagai deterministik, dalam hal ini lebih umum dan menurut saya pengertian yang lebih alami tentang 'algoritma' membutuhkan nama yang berbeda.

Gagasan bekerja dengan spesifikasi nondeterministik diformalkan dengan metode pemrograman Dijkstra, yang dimulai dengan spesifikasi yang hanya memberikan pra dan pasca kondisi yang harus dipenuhi oleh program, dan secara sistematis mengembangkan program deterministik, imperatif dari mereka. Dijkstra mungkin akan mengatakan: penyortiran adalah masalahnya, hubungan antara kondisi sebelum dan sesudah kami coba bangun; menggabungkan semacamadalah pendekatan untuk melakukan itu, di suatu tempat di tengah-tengah antara spesifikasi masalah dan solusi deterministik; khusus, deterministic merge sorting algorithm adalah solusi deterministik yang konkret. Tetapi pendekatan umum yang sama dapat digunakan untuk mengembangkan program bersamaan, di mana program akhirnya masih nondeterministik. Program semacam itu misalnya dapat dijalankan dalam lingkungan komputasi terdistribusi.

reinierpost
sumber
2

Anda benar, kami TIDAK dapat membangun mesin nondeterministic. Karena itu, tujuannya bukan menggunakan konsep untuk membangun mesin yang lebih baik. Sebaliknya, nondeterminisme adalah konsep yang berguna ketika mencoba memahami perhitungan. Sebagai contoh, kita sekarang tahu bahwa, dari perspektif komputabilitas, nondeterminisme bukanlah sesuatu yang lebih kuat daripada determinisme, yang berarti bahwa kita dapat mensimulasikan mesin nondeterministic dengan menggunakan yang deterministik. Namun, dari perspektif kompleksitas, nondeterminisme memungkinkan kita, misalnya, untuk bernalar dan mencoba memahami hubungan di antara kesulitan menemukan solusi yang efisien untuk suatu masalah dan kesulitan memverifikasi solusi (yang merupakan masalah P versus NP yang terkenal) . Dan seterusnya. Oleh karena itu, alasan utama untuk mempelajari nondeterminisme adalah teori.

Massimo Cafaro
sumber
Bebas Konteks versus Bebas Deterministik?
alto
@ juga Bagaimana dengan itu?
babou
@ Babou, saya mencoba menunjukkan bahwa "nondeterminisme bukanlah sesuatu yang lebih kuat daripada determinisme," adalah pernyataan yang salah. NPDA lebih kuat dari pada PDA.
alto
1
@alto: no, you are misunderstanding the statement. From a computability perspective, they are fully equivalent, since the class of problems (or languages if you prefer) that you may solve INDEPENDENTLY of how much computational resources are required is the same. And indeed, you CAN simulate a nondeterministic machine with a deterministic one. Again, time and space required DOES NOT MATTERS in the computability context.
Massimo Cafaro
1
@MassimoCafaro Couldn't agree more, in theory. In practice it appears I prefer to quibble about semantics.
alto
2

the invention of the Turing Machine was in 1936 by Turing. FSM-like models were introduced by McCulloch and Pitts, two neurophysiologists, as a model for neurobiological activity in 1943. from the Stanford CS history page:

Sejarah yang menarik tentang bagaimana automata yang terbatas menjadi cabang ilmu komputer menggambarkan berbagai aplikasinya. Orang pertama yang mempertimbangkan konsep mesin negara terbatas termasuk tim ahli biologi, psikolog, matematikawan, insinyur, dan beberapa ilmuwan komputer pertama. Mereka semua memiliki minat yang sama: untuk memodelkan proses berpikir manusia, baik di otak maupun di komputer. Warren McCulloch dan Walter Pitts, dua ahli neurofisiologi, adalah orang pertama yang menyajikan deskripsi automata terbatas pada tahun 1943. Makalah mereka, berjudul, "Kalkulus Logial yang Imanen dalam Aktivitas Saraf", memberikan kontribusi signifikan pada studi teori jaringan saraf, teori automata, teori komputasi dan sibernetika. Kemudian, dua ilmuwan komputer, GH Mealy dan EF Moore, menggeneralisasikan teori ke mesin yang jauh lebih kuat di kertas terpisah, diterbitkan pada tahun 1955-56. Mesin negara-terbatas, mesin Mealy dan mesin Moore, dinamai sebagai pengakuan atas pekerjaan mereka.

not a CS historian, but suspect that the McCulloch-Pitts model did not include nondeterminism and the Mealy-Moore model did, in a natural generalizing/abstraction of the formal/theoretical concept. note that DFAs and NFAs have the same representational power so that if one wishes to model real systems there is a choice of either. one basic difference is that an NFA may be much smaller than an equivalent DFA (so for example there is a natural element of data/information compression). there are also natural aspects/analogs of parallelism in NFA study.

vzn
sumber
3
Hai, saya melihat Anda profil dan sepertinya seseorang dengan sengaja memberikan suara untuk memilih jawaban Anda (setiap tempat Anda hanya memiliki dua downvotes) ... Jawaban ini tidak salah , jawabannya menambah informasi yang bermanfaat. +1
Grijesh Chauhan
0

First of all I would like to say thanks to all the people who answered the question.All the answers are important and add some useful information.But as it is a tricky question to the beginners, and need sufficient time to understanding it well, I would try to summarize what I have gained from all the answers and from some books:

Sebenarnya saya memiliki kebingungan yaitu tentang mekanisme model nondeterministic. Saya selalu bertanya-tanya tentang mesin nondeterministic karena ini adalah mesin non-mekanis yang tidak ada di dunia nyata. Saya selalu membandingkan Automata dengan komputer kita sekarang yang sepenuhnya bersifat deterministik. Sebenarnya saya tidak benar memahami model nondeterministic. Sekarang saya pikir saya memahami model nonderministic dengan cukup baik: Mesin nondeterministic adalah mesin yang selalu mengikuti jalur eksekusi yang mengarah pada penerimaan string (Tanpa Backtracking). Tetapi bagaimana hal ini dapat dimungkinkan dalam kehidupan nyata? : Sangat mustahil bagi komputer saat ini untuk menjadi secerdas itu untuk memprediksi masa depan. Jadi mengapa nondeterminisme sama sekali? Jawaban dari pertanyaan ini cukup sulit. Yang saya simpulkan tentang pertanyaannya adalah: Teori Automata memang ada ketika komputer tidak ada (Teori Pertama kemudian praktis). Ini adalah subjek yang sepenuhnya teoretis dan konsep nondeterminisme datang secara intuitif. Motif subjek 'Automata Theory' bukanlah untuk berurusan dengan komputer praktis. Tetapi ketika praktis komputer datang kemudian menggunakan Teori Automata kita dapat mendefinisikan komputer praktis secara tepat: apa keterbatasan komputer saat ini. Masalah algoritmik yang sangat kompleks untuk komputer dan sangat tidak praktis (Di sini peran nondererminisme sangat krusial dimana kita dapat membedakan dua kelas kompleksitas P dan NP). Apa solusi untuk masalah tidak praktis ini yang dapat dieksekusi relatif lebih cepat. Inilah kegunaan nondeterminisme. Ini adalah subjek yang sepenuhnya teoretis dan konsep nondeterminisme datang secara intuitif. Motif subjek 'Automata Theory' bukanlah untuk berurusan dengan komputer praktis. Tetapi ketika praktis komputer datang kemudian menggunakan Teori Automata kita dapat mendefinisikan komputer praktis secara tepat: apa keterbatasan komputer saat ini. Masalah algoritmik yang sangat kompleks untuk komputer dan sangat tidak praktis (Di sini peran nondererminisme sangat krusial dimana kita dapat membedakan dua kelas kompleksitas P dan NP). Apa solusi untuk masalah tidak praktis ini yang dapat dieksekusi relatif lebih cepat. Inilah kegunaan nondeterminisme. Ini adalah subjek yang sepenuhnya teoretis dan konsep nondeterminisme datang secara intuitif. Motif subjek 'Automata Theory' bukanlah untuk berurusan dengan komputer praktis. Tetapi ketika praktis komputer datang kemudian menggunakan Teori Automata kita dapat mendefinisikan komputer praktis secara tepat: apa keterbatasan komputer saat ini. Masalah algoritmik yang sangat kompleks untuk komputer dan sangat tidak praktis (Di sini peran nondererminisme sangat krusial dimana kita dapat membedakan dua kelas kompleksitas P dan NP). Apa solusi untuk masalah tidak praktis ini yang dapat dieksekusi relatif lebih cepat. Inilah kegunaan nondeterminisme. Tetapi ketika praktis komputer datang kemudian menggunakan Teori Automata kita dapat mendefinisikan komputer praktis secara tepat: apa keterbatasan komputer saat ini. Masalah algoritmik yang sangat kompleks untuk komputer dan sangat tidak praktis (Di sini peran nondererminisme sangat krusial dimana kita dapat membedakan dua kelas kompleksitas P dan NP). Apa solusi untuk masalah tidak praktis ini yang dapat dieksekusi relatif lebih cepat. Inilah kegunaan nondeterminisme. Tetapi ketika praktis komputer datang kemudian menggunakan Teori Automata kita dapat mendefinisikan komputer praktis secara tepat: apa keterbatasan komputer saat ini. Masalah algoritmik yang sangat kompleks untuk komputer dan sangat tidak praktis (Di sini peran nondererminisme sangat krusial dimana kita dapat membedakan dua kelas kompleksitas P dan NP). Apa solusi untuk masalah tidak praktis ini yang dapat dieksekusi relatif lebih cepat. Inilah kegunaan nondeterminisme. Apa solusi untuk masalah tidak praktis ini yang dapat dieksekusi relatif lebih cepat. Inilah kegunaan nondeterminisme. Apa solusi untuk masalah tidak praktis ini yang dapat dieksekusi relatif lebih cepat. Inilah kegunaan nondeterminisme.

Harap perbaiki saya jika ada yang salah.

tanmoy
sumber
Adalah keliru untuk mengatakan bahwa mesin nondeterministic adalah mesin yang selalu mengikuti jalur eksekusi yang mengarah pada penerimaan string . Itu tidak melakukan itu! Mesin nondeterministic adalah mesin yang operasinya memungkinkan pilihan tertentu yang tidak direncanakan (= nondeterministic) dibuat selama eksekusi. Tidak ada yang tidak realistis tentang mesin seperti itu, misalnya mereka dapat meminta lingkungan untuk membuat pilihan-pilihan itu. Mesin-mesin ini kemudian diterapkan pada tugas-tugas yang dipegangnya bahwa pilihan-pilihan tertentu akan menghasilkan status penerimaan.
reinierpost
@reinierpost: Jadi Anda mengatakan bahwa mesin non-deterministik memang ada dalam kehidupan nyata.
tanmoy
Iya nih. Berikut ini sebuah contoh: misalkan Anda mengendarai mobil, dan Anda tidak membuat keputusan tentang rute yang harus diikuti. Misalnya, Anda mungkin berkeliling tanpa tujuan, atau mengambil arah dari navigator manusia atau perangkat navigasi. Mobil dan Anda adalah sistem nondeterministik untuk mengemudi tempat. Anda bergerak melalui lalu lintas dan terus menemukan pilihan arah mana yang harus diambil. Bagi Anda dan mobil, pilihan-pilihan ini tidak deterministik: Anda tidak memutuskan ke arah mana harus pergi, tetapi mengingat keputusan itu, Anda akan mengikutinya.
reinierpost
@reinierpost: Is there any non-deterministic computer exist? My answer is NO. because if it exists then NP problems would have polynomial time complexity. isn't it?
tanmoy
Whether computers are deterministic or nondeterministic depends on how you look at them. When a computer stops and waits for the user to do something, and its next actions will depend on what the user does, you can say that is a nondeterministic choice. No, this doesn't imply that P = NP.
reinierpost
0

non-determinism is useful because it helps you understand determinism, but not the other way around. You could say non-determinism is the bigger idea. A deterministic turing machine is a special case of a non-deterministic one. - Nondeterminism can help us understand why, on todays platforms, some problems are hard to pin down. There are a number of computational problems that have no efficient solution on a deterministic computing platform, but we understand that there can be efficient solutions on nondeterministic ones. ... state, encoding, nondeterminism they are all linked http://people.cs.umass.edu/~rsnbrg/teach-eatcs.pdf

In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation. A non-deterministic Turing machine(NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation. http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine If you can build a software box that can manage state transitions so well that it can handle more than one action you can get performance beyond deterministic machines.

Tom
sumber
I'm not sure the alleged links to reality are at all helpful. It's quite clear that we can not build a non-deterministic machine (today at least) so it's an entirely theoretic construct.
Raphael
We can build a nondeterministic machine by letting the nondeterministic decisions be made by something external to the machine.
reinierpost
@ reinierpost, more importantly we can build non-deterministic machines as deterministic ones, without incurring exponential overhead. see Savitch's Theorem. en.wikipedia.org/wiki/Savitch's_theorem
Tom
@ Raphael, some references to the real world are important. Why does caching work? Because events in the real world, which is ultimately the source of all data, happen to follow a normal distribution. see Temporal locality: durablescope.blogspot.co.at/2009/11/…
Tom
@ reinierpost, and that something external is what Turing called an oracle machine. I think you can think if that as data coming out of cache or something like a multi-tape machine or even tapping into to random access memory.
Tom
0

Why is non-determinism useful concept?

Determinism has a strong tendency to break symmetries. This tendency is even stronger for sequential determinism, but the notion of an acyclic directed graph and a topological order of such a graph allows to ignore the difference between determinism and sequential determinism. Non-determinism is a superset of determinism, which allows to preserve more symmetries. When designing the solution of a problem, starting with the non-deterministic solution allows to preserve useful symmetries, and which keeps the description of the solution small and compact. The breaking of the symmetries can then be delegated to a later stage during implementation, while converting the non-deterministic solution to a deterministic solution.

Often non-determinism means that the notion of a partial function is replaced by the notion of a relation. In that case, a non-deterministic machine can run both forward and backward in time, while this is not possible in general for a deterministic machine. If we work with total functions for determinism and multivalued total functions for non-determinsim instead, the symmetry is no longer as nice, but it still can be made to work.

Thomas Klimpel
sumber
Can you give a specific example? I find it hard to see what you mean by "symmetry" here.
Raphael
@Raphael How about reversing (01)*01(0 + 1)* to (0 + 1)*10(10)* such that it recognizes the reversed input string, and apply this symmetry to the non-deterministic machine by reversing all arrow and swapping start and end state? I'm not sure whether there are significantly more interesting examples for finite state machines, but I could try to come up with an interesting example for a PDA instead.
Thomas Klimpel
I wrote about my answer to a similar question in a blog post about Reversibility of binary relations, substochastic matrices, and partial functions.
Thomas Klimpel