Dlaczego niedeterminizm jest użyteczną koncepcją?

Automat jest abstrakcyjnym modelem komputera cyfrowego. Komputery cyfrowe są całkowicie deterministyczne; ich stan w dowolnym momencie jest wyjątkowo przewidywalny na podstawie stanu wejściowego i początkowego.

Kiedy próbujemy modelować prawdziwe systemy, dlaczego włączamy niedeterminizm do teorii automatów?

Tak, masz rację, komputery są deterministyczne automatyzacji. Modele niedeterministyczne są bardziej przydatne do celów teoretycznych, czasem rozwiązanie deterministyczne nie jest tak oczywiste w definicji (lub powiedzmy opisie problemu) i tak trudno jest je znaleźć. Następnie jedno podejście polega na tym, że najpierw projektuje się model niedeterministyczny, który może być stosunkowo łatwy do zaprojektowania, a następnie próbuje przekształcić go w model deterministyczny. Poniżej próbowałem wykazać, co mam na myśli na przykładzie. Rozważ wyrażenie regularne:

(01)*01(0 + 1)*  

Załóżmy teraz, że jeśli zostaniesz poproszony o narysowanie DFA dla języka wygenerowanego przez powyższe RE.

Z mojej wiedzy o projektowaniu federacjami, wiem, że (1) gdy *występuje w wyrażeniu regularnym wskazany Potrzebuję odpowiada pętli w FA (2) operacje oddzielając podobnego a.bśrodka coś takiego: .(q0)─a→(q1)─b→(q2)

Więc przy pierwszej próbie narysowałem NFA, takie jak:

Myślałem, że nie jest to rozwiązanie deterministyczne, ale wygląda na bardzo prosty FA, ​​który można łatwo zaprojektować przy użyciu danego wyrażenia regularnego. Mój rodzaj analogii do pokazania podobieństwa między powyższym wyrażeniem regularnym a moim NFA jest następujący:

1. Pętla w stanie q ₀ powinna być dla(01)*
2. 01(po (01)*) daje(q0)─0→(q1)─1→(q2)
3. (0 + 1)* daje pętlę własną w stanie q ₂ dla etykiety 0, 1

Według mojej analogii uważam, że FA, który narysowałem powyżej, jest stosunkowo łatwy do wyciągnięcia z danego RE. I na szczęście w klasie automatów skończonych każdy model niedeterministyczny można przekształcić w równoważny model deterministyczny. Mamy algorytmiczną metodę konwersji NFA na DFA . Więc mogę łatwo przekonwertować powyżej NFA na DFA:

Inna część jest niestety nie zawsze możliwa jest konwersja modelu niedeterministycznego na model deterministyczny, na przykład klasa deterministycznego automatyzmu push-down jest podzbiorem klasy deterministycznego automatyzmu push-down „ diagram Venna ” i nie zawsze można przekonwertować NPDA na PDA.

Zwykle, gdy nie jest możliwe przekształcenie rozwiązania niedeterministycznego w deterministyczne, wówczas za pomocą rozwiązania niedeterministycznego definiujemy rozwiązanie deterministyczne w subdomenie (lub, powiedzmy, częściowej), zamiast w domenie pełnej. Lub definiujemy rozwiązanie na kilka innych sposobów (np. Chciwe podejście), które oczywiście mogą nie dać optymalnego rozwiązania .

Czasami niedeterminizm jest skutecznym mechanizmem precyzyjnego i skutecznego opisywania niektórych skomplikowanych problemów / rozwiązań, na przykład maszyny niedeterministyczne mogą służyć jako model algorytmu wyszukiwania i cofania się (czytaj: Jak ciąg znaków w modelu niedeterministycznym z wykorzystaniem wstecznego ). Modele przeciwstawne deterministyczne lepiej reprezentują wydajne, zminimalizowane i mniej zbędne rozwiązania.

W tym miejscu chciałbym również zacytować z Wikipedii użycie niedeterministycznego algorytmu :

W projektowaniu algorytmów często stosuje się niedeterministyczne algorytmy, gdy problem rozwiązany przez algorytm z natury pozwala na wiele wyników (lub gdy istnieje jeden wynik z wieloma ścieżkami, za pomocą których można go odkryć, każdy z nich jest równie preferowany). Co najważniejsze, każdy wynik, który wytwarza algorytm niedeterministyczny, jest prawidłowy, niezależnie od tego, jakie wybory algorytm dokonuje podczas pracy.

Wiele problemów można konceptualizować za pomocą niedeterministycznych algorytmów, w tym najbardziej znanego nierozwiązanego pytania w teorii obliczeń, P vs NP.

Jak wspomniał także @Keshlam w swoim komentarzu : „Niedeterminizm” jest w praktyce używany w odniesieniu do jakiejkolwiek nieprzewidywalności w wyniku jakiegoś procesu. Na przykład programy współbieżne wykazują zachowanie niedeterministyczne - dwa wykonania tego samego programu z tymi samymi danymi wejściowymi mogą dawać różne wyniki (jeśli nie zastosowano mechanizmu kontroli współbieżności ). Przeczytaj więcej na ten temat w „Przydatności braku determinizmu” .

Sugerowałbym również przeczytanie następujących linków:
1. Jaka jest różnica między niedeterminizmem a przypadkowością?
2. 9.2.2 Modele niedeterministyczne vs. probabilistyczne: (a). Niedeterministyczny: nie mam pojęcia, co zrobi natura. (b). Probabilistyczny: Obserwuję przyrodę i zbieram statystyki.
3. Programowanie niedeterministyczne

Jest raczej na odwrót: najpierw powstały automaty jako modele matematyczne. Niedeterminizm jest całkiem naturalny, często masz przed sobą kilka ścieżek. Zamiast niechlujnego sposobu określania, że ​​wszystkie ścieżki muszą podążać do końca w pewnej kolejności, a być może utknięcia w nieskończonych gałęziach i ... po prostu użyj niedeterminizmu.

I choć niedeterministyczne języki programowania nie są głównym nurtem, mają wspaniałą historię, być może zaczynającą się od GCL Dijkstry . Ponieważ maszyny mają coraz więcej rdzeni (niezależne procesory), pewna forma niedeterminizmu przenika do wszystkich programów.

NFA mogą być stosowane w praktyce, sprawdź tę odpowiedź na stackexchange . Powodem jest to, że można powiedzieć, że konstrukcja zestawu zasilającego może być symulowana w locie. Aby zasymulować NFA na komputerze deterministycznym, po prostu śledzimy możliwe stany, w których NFA może się znajdować. Zazwyczaj liczba ta byłaby mała, a więc symulacja byłaby szybka. Jest to o wiele bardziej praktyczne niż uruchamianie rzeczywistej konstrukcji zestawu zasilającego: wynikowy automat może być bardzo duży, chociaż w praktyce większość zestawów byłaby rzadko osiągana.

Niedeterminizm jest również ważny dla złożoności obliczeń, gdzie służy do definiowania klasy NP. (Klasa NP ma również inne równoważne definicje, na przykład wykorzystujące świadków).

Prawidłowo stwierdzasz, że automaty są modelami, więc istnieją dwie części zastosowania, które mogą mieć niedeterminizm:

1. Użyj w modelowaniu prawdziwych problemów.

   $\neq$

   Ponadto, niedeterministyczne automaty mogą zapewniać bardziej zwartą reprezentację języków. Na przykład dobrze wiadomo, że istnieją NFA, których minimalny równoważny DFA jest wykładniczo większy.

2. Zastosowanie w teorii.

   Używanie niedeterminizmu może uprościć dowody, patrz np. Konwersja wyrażeń regularnych do automatów skończonych.

(To jest przeredagowanie niektórych innych odpowiedzi, ale i tak opublikuję :)

Piszesz: Automat to abstrakcyjny model komputera cyfrowego.

Nie zgadzam się! Automaty modelują sposób, w jaki my, ludzie, określamy obliczenia, a nie tylko sposób ich wykonywania przez komputery. Niedeterminizm jest dokładnie różnicą. Nasze specyfikacje są często niedeterministyczne.

Na przykład weź sortowanie po scaleniu . Sortowanie według sortowania polega na dzieleniu sortowanych elementów na dwie połowy o mniej więcej równej wielkości, sortowaniu każdej połowy za pomocą sortowania scalającego i scalaniu sortowanych wyników. To całkowicie określa ideę sortowania scalającego, ale nie jest deterministyczne: nie określa kolejności sortowania połówek (dla nas wszystko to obchodzi, może być wykonywane jednocześnie), ani nie określa dokładnego sposobu określić podział. Te szczegóły będą musiały zostać wypełnione, aby uzyskać deterministyczną, sekwencyjną wersję sortowania scalającego, która może zostać zaimplementowana przez jednowątkowy program komputerowy, ale powiedziałbym, że są one częścią szczególnego sposobu wykonywania sortowania scalającego, a nie sama idea sortowania.

To samo dotyczy ogólnie algorytmów - np. Przepisów na książki kucharskie. Niektóre osoby definiują algorytmy jako deterministyczne, w takim przypadku to bardziej ogólne i moim zdaniem bardziej naturalne pojęcie „algorytmu” wymaga innej nazwy.

Idea pracy z niedeterministycznymi specyfikacjami została sformalizowana przez metodę programowania Dijkstry, która zaczyna się od specyfikacji, które dają jedynie warunki wstępne i dodatkowe, które ma spełniać program, i systematycznie opracowuje z nich deterministyczny, imperatywny program. Dijkstra prawdopodobnie powiedziałby: sortowanie jest problemem, relacją między warunkami wstępnymi i późniejszymi, które próbujemy ustalić; scalanie sortujjest podejściem do tego, gdzieś w połowie drogi między specyfikacją problemu a rozwiązaniem deterministycznym; szczególny deterministyczny algorytm sortowania scalonego jest konkretnym deterministycznym rozwiązaniem. Ale to samo ogólne podejście można zastosować do opracowania współbieżnych programów, w których ostateczny program wciąż nie jest deterministyczny. Takie programy można np. Uruchamiać w rozproszonych środowiskach komputerowych.

Masz rację, NIE możemy zbudować niedeterministycznej maszyny. Dlatego celem nie jest wykorzystanie koncepcji budowy lepszych maszyn. Niedeterminizm jest raczej użyteczną koncepcją przy próbie zrozumienia obliczeń. Na przykład wiemy teraz, że z perspektywy obliczeniowej niedeterminizm nie jest czymś potężniejszym niż determinizm, co oznacza, że ​​możemy symulować maszynę niedeterministyczną za pomocą maszyny deterministycznej. Jednak z punktu widzenia złożoności niedeterminizm pozwala nam na przykład rozumować i próbować zrozumieć związek między trudnością znalezienia skutecznego rozwiązania problemu a trudnością weryfikacji rozwiązania (który jest znanym problemem P kontra NP) . I tak dalej. Dlatego głównym powodem badania niedeterminizmu jest teoretyczny.

wynalazek maszyny Turinga nastąpił w 1936 r. przez Turinga. Modele podobne do FSM zostały wprowadzone przez McCullocha i Pittsa , dwóch neurofizjologów, jako model aktywności neurobiologicznej w 1943 r. Ze strony historii Stanford CS :

Ekscytująca historia tego, jak automaty skończone stały się gałęzią informatyki, ilustruje jej szeroki zakres zastosowań. Pierwszymi osobami, które rozważyły ​​koncepcję maszyny o stanie skończonym, byli zespół biologów, psychologów, matematyków, inżynierów i kilku pierwszych informatyków. Wszyscy mieli wspólny interes: modelować ludzki proces myślowy, czy to w mózgu, czy w komputerze. Warren McCulloch i Walter Pitts, dwaj neurofizjolodzy, jako pierwsi przedstawili opis automatów skończonych w 1943 r. Ich praca zatytułowana „Logical Calculus Immanent in Nervous Activity” wniosła znaczący wkład w badania teorii sieci neuronowej, teorii automaty, teoria obliczeń i cybernetyka. Później dwóch informatyków, GH Mealy i EF Moore, uogólniono teorię na znacznie mocniejsze maszyny w osobnych artykułach, opublikowanych w latach 1955-56. Maszyny o stanie skończonym, Mealy i Moore, zostały nazwane w uznaniu ich pracy.

nie historyk CS, ale podejrzewa, że ​​model McCullocha-Pittsa nie zawiera niedeterminizmu, a model Mealy - Moore'a , w naturalny uogólnienie / abstrakcję koncepcji formalnej / teoretycznej. zauważ, że DFA i NFA mają taką samą moc reprezentacji, więc jeśli ktoś chce modelować rzeczywiste systemy, może wybrać jedno z nich. jedną podstawową różnicą jest to, że NFA może być znacznie mniejszy niż równoważny DFA (więc na przykład istnieje naturalny element kompresji danych / informacji). istnieją również naturalne aspekty / analogie równoległości w badaniu NFA.

Przede wszystkim chciałbym podziękować wszystkim osobom, które odpowiedziały na pytanie. Wszystkie odpowiedzi są ważne i zawierają przydatne informacje. Ale ponieważ jest to trudne pytanie dla początkujących i potrzebuję wystarczająco dużo czasu, aby dobrze je zrozumieć, ja postaram się podsumować to, co uzyskałem na podstawie wszystkich odpowiedzi i niektórych książek:

Właściwie miałem zamieszanie dotyczące mechanizmu modelu niedeterministycznego. Zawsze zastanawiałem się nad niedeterministyczną maszyną, ponieważ jest to niemechaniczna maszyna, która nie istnieje w prawdziwym świecie. Zawsze porównywałem Automaty z dzisiejszymi komputerami, które mają całkowicie deterministyczny charakter. Właściwie nie rozumiałem właściwie modelu niedeterministycznego. Teraz myślę, że całkiem dobrze rozumiem model niedeterministyczny: niedeterministyczna maszyna to maszyna, która zawsze podąża ścieżką wykonania, która prowadzi do akceptacji łańcucha (bez cofania). Ale jak to możliwe w prawdziwym życiu? : Absolutnie niemożliwe jest, aby dzisiejszy komputer był tak inteligentny, aby przewidywać przyszłość. Skąd więc w ogóle niedeterminizm? Odpowiedź na to pytanie jest dość trudna. Doszłam do wniosku, że: Teoria automatów istniała, gdy komputery nie istniały (najpierw teoria praktyczna). Jest to przedmiot czysto teoretyczny, a koncepcja niedeterminizmu pojawiła się intuicyjnie. Motywem „teorii automatów” nie było zajmowanie się praktycznymi komputerami. Ale kiedy praktycznie pojawia się komputer, wtedy przy użyciu Teorii Automatów jesteśmy w stanie precyzyjnie zdefiniować praktyczne komputery: jakie są ograniczenia współczesnych komputerów. Których problem algorytmiczny jest bardzo złożony dla komputerów i tak niepraktyczny (tutaj rola niederemininizmu jest bardzo kluczowa, przez co potrafi rozróżnić dwie klasy złożoności P i NP). Jakie są rozwiązania tych niepraktycznych problemów, dzięki którym można je wykonać stosunkowo szybciej. itp. Taka jest przydatność niedeterminizmu. Jest to przedmiot czysto teoretyczny, a koncepcja niedeterminizmu pojawiła się intuicyjnie. Motywem „teorii automatów” nie było zajmowanie się praktycznymi komputerami. Ale kiedy praktycznie pojawia się komputer, wtedy przy użyciu Teorii Automatów jesteśmy w stanie precyzyjnie zdefiniować praktyczne komputery: jakie są ograniczenia współczesnych komputerów. Których problem algorytmiczny jest bardzo złożony dla komputerów i tak niepraktyczny (tutaj rola niederemininizmu jest bardzo kluczowa, przez co potrafi rozróżnić dwie klasy złożoności P i NP). Jakie są rozwiązania tych niepraktycznych problemów, dzięki którym można je wykonać stosunkowo szybciej. itp. Taka jest przydatność niedeterminizmu. Jest to przedmiot czysto teoretyczny, a koncepcja niedeterminizmu pojawiła się intuicyjnie. Motywem „teorii automatów” nie było zajmowanie się praktycznymi komputerami. Ale kiedy praktycznie pojawia się komputer, wtedy przy użyciu Teorii Automatów jesteśmy w stanie precyzyjnie zdefiniować praktyczne komputery: jakie są ograniczenia współczesnych komputerów. Których problem algorytmiczny jest bardzo złożony dla komputerów i tak niepraktyczny (tutaj rola niederemininizmu jest bardzo kluczowa, przez co potrafi rozróżnić dwie klasy złożoności P i NP). Jakie są rozwiązania tych niepraktycznych problemów, dzięki którym można je wykonać stosunkowo szybciej. itp. Taka jest przydatność niedeterminizmu. Ale kiedy praktycznie pojawia się komputer, wtedy przy użyciu Teorii Automatów jesteśmy w stanie precyzyjnie zdefiniować praktyczne komputery: jakie są ograniczenia współczesnych komputerów. Których problem algorytmiczny jest bardzo złożony dla komputerów i tak niepraktyczny (tutaj rola niederemininizmu jest bardzo kluczowa, przez co potrafi rozróżnić dwie klasy złożoności P i NP). Jakie są rozwiązania tych niepraktycznych problemów, dzięki którym można je wykonać stosunkowo szybciej. itp. Taka jest przydatność niedeterminizmu. Ale kiedy praktycznie pojawia się komputer, wtedy przy użyciu Teorii Automatów jesteśmy w stanie precyzyjnie zdefiniować praktyczne komputery: jakie są ograniczenia współczesnych komputerów. Których problem algorytmiczny jest bardzo złożony dla komputerów i tak niepraktyczny (tutaj rola niederemininizmu jest bardzo kluczowa, przez co potrafi rozróżnić dwie klasy złożoności P i NP). Jakie są rozwiązania tych niepraktycznych problemów, dzięki którym można je wykonać stosunkowo szybciej. itp. Taka jest przydatność niedeterminizmu. Jakie są rozwiązania tych niepraktycznych problemów, dzięki którym można go wykonać stosunkowo szybciej. Etc. Taka jest przydatność niedeterminizmu. Jakie są rozwiązania tych niepraktycznych problemów, dzięki którym można go wykonać stosunkowo szybciej. Etc. Taka jest przydatność niedeterminizmu.

Popraw mnie, jeśli coś jest nie tak.

niedeterminizm jest użyteczny, ponieważ pomaga zrozumieć determinizm, ale nie na odwrót. Można powiedzieć, że niedeterminizm jest większym pomysłem. Deterministyczna maszyna Turinga jest szczególnym przypadkiem maszyny niedeterministycznej. - Niedeterminizm może pomóc nam zrozumieć, dlaczego na dzisiejszych platformach niektóre problemy są trudne do zidentyfikowania. Istnieje szereg problemów obliczeniowych, które nie mają skutecznego rozwiązania na deterministycznej platformie obliczeniowej, ale rozumiemy, że mogą istnieć wydajne rozwiązania na niedeterministycznych. ... stan, kodowanie, niedeterminizm są one wszystkie powiązane http://people.cs.umass.edu/~rsnbrg/teach-eatcs.pdf

W deterministycznej maszynie Turinga zestaw reguł określa co najwyżej jedno działanie, które należy wykonać w danej sytuacji. Natomiast niedeterministyczna maszyna Turinga (NTM) może mieć zestaw reguł, które nakazują więcej niż jedno działanie w danej sytuacji. http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine Jeśli potrafisz zbudować skrzynkę oprogramowania, która może tak dobrze zarządzać przejściami stanów, że może obsłużyć więcej niż jedną akcję, możesz uzyskać wydajność wykraczającą poza deterministyczne maszyny.

Dlaczego niedeterminizm jest przydatną koncepcją?

Determinizm ma silną tendencję do łamania symetrii. _{Tendencja ta jest jeszcze silniejsza w przypadku determinizmu sekwencyjnego, ale pojęcie acyklicznego grafu kierowanego i porządku topologicznego takiego wykresu pozwala zignorować różnicę między determinizmem a determinizmem sekwencyjnym.} Niedeterminizm jest nadzbiorem determinizmu, który pozwala zachować więcej symetrii. Projektując rozwiązanie problemu, rozpoczęcie od rozwiązania niedeterministycznego pozwala zachować użyteczne symetrie, dzięki czemu opis rozwiązania jest mały i zwarty. Łamanie symetrii może być następnie delegowane na późniejszy etap podczas implementacji, przy jednoczesnym przekształceniu niedeterministycznego rozwiązania w deterministyczne.

Często niedeterminizm oznacza, że ​​pojęcie funkcji cząstkowej zastępuje się pojęciem relacji. W takim przypadku niedeterministyczna maszyna może działać zarówno do przodu, jak i do tyłu w czasie, podczas gdy ogólnie nie jest to możliwe w przypadku deterministycznej maszyny. Jeśli zamiast tego pracujemy z funkcjami totalnymi dla determinizmu i wielowymiarowymi funkcjami totalnymi dla non-determininsim, symetria nie jest już tak przyjemna, ale nadal można ją uruchomić.