Dlaczego niedeterminizm jest użyteczną koncepcją?

23

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?

tanmoy
źródło
1
Być może pomogłoby zapytać, kto pierwotnie opisał NTM i jaki był ich cel / cel w tym czasie.
usul
2
Zauważ, że fakt, że maszyna jest deterministyczna, nie zawsze oznacza, że ​​nasz kod jest. Każdy, kto wykonał wielozadaniowość / wielowątkowość, może zaświadczyć, że czasy, w których następuje przełączanie zadań, są często nieprzewidywalne pod względem praktycznym i musimy zaprojektować wyraźne blokady, aby ich zachowanie wydawało się deterministyczne. (Zasadniczo w stanie są ukryte zmienne.) Komunikacja wiąże się z tym samym problemem. Naprawdę nie wiem, czy NDA pomagają rozwiązać te problemy - jestem inżynierem oprogramowania, a nie informatykiem - ale w prawdziwym świecie twoje przesłanie jest zbyt optymistyczne.
keshlam
Kiedy mówimy o wielowątkowość, zapewne pan mieć non-determinizm, przynajmniej jeśli wziąć pod uwagę metalu i OS tworząc maszynę. Zabawne jest to, że sam kod jest deterministyczny.
Raphael
@ Raphael, @keshlam Innymi słowy, możemy powiedzieć, że „Modele niedeterministyczne są również przydatne do symulacji równoległego wykonywania kodu”
Grijesh Chauhan
@keshlam Dodałem twój punkt do mojej odpowiedzi, @ Tanmoy przeczytałem zaktualizowałem moją odpowiedź.
Grijesh Chauhan

Odpowiedzi:

16

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:

Figa

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 0 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 2 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:

rys. 2

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

Grijesh Chauhan
źródło
@Grijest: wielkie dzięki za tak ogromne opracowanie. Tylko jedno zamieszanie: „Modele deterministyczne przeciwstawne lepiej reprezentują wydajne, zminimalizowane i mniej redundantne rozwiązania.” - Myślę jednak, że modele deterministyczne są mniej skuteczne niż model niedeterministyczny. (Dlatego właśnie problemy NP są bardziej złożone niż P. Czyż nie?)
tanmoy
@tan Właściwie użycie słowa „wydajny” jest błędne, i tak, masz rację, że modele niedeterministyczne są bardziej zdolne niż modele deterministyczne. Klasą problemów objętych modelami deterministycznymi jest podzbiór modelu niedeterministycznego.
Grijesh Chauhan
więc w jakim kontekście modele deterministyczne są „wydajne” niż niedeterministyczne (jak wspomniałeś)?
tanmoy
@tan Załóżmy, że jeśli chcesz wykonać dalszą operację (np. chcesz przekonwertować FA na RE, lub wyjaśnić dowód na pompowanie lematu, lub jakiś inny ...), to model deterministyczny daje lepsze wyniki (powiedziałem, że wydajne).
Grijesh Chauhan
@tan Czy rozumiesz niejednoznaczne gramatyki?
Grijesh Chauhan
9

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.

vonbrand
źródło
Myślę, że pierwsza część twojej odpowiedzi jest nieprawdziwa. Jak myślisz, dlaczego automaty powstały jako pierwsze? Zarówno DFA, jak i NFA zdefiniowano ponad 10 lat po zdefiniowaniu TM przez Turinga. Zobacz dyskusję o cstheory
Artem Kaznatcheev
@ArtemKaznatcheev, model maszyny Turinga jest automatem i na pewno wyprzedza komputery o co najmniej dekadę.
vonbrand,
tak, ale kiedy ludzie mówią, że automaty nie mają na myśli TM, mają na myśli automaty skończone i ich bezpośrednie rozszerzenia (PDA, NPDA itp.). Zobacz pytanie, które połączyłem, aby tam znaleźć historię, a zobaczysz, że zarówno TM, jak i architektura von Neumanna zostały opracowane niezależnie od tego, co obecnie nazywamy teorią automatów.
Artem Kaznatcheev
4
@ArtemKaznatcheev, DFA / NFA, PDA, LBA, TM są automatami. Podobnie jak przetworniki (FA z wyjściem, PDA z wyjściem).
vonbrand,
1
Ostatni akapit jest zły. Prolog poprzedza GCL, a nawet jest wciąż obecny i dość popularny. Prolog oczywiście nie został zaprojektowany w próżni, bazując na wcześniejszych niedeterministycznych językach programowania, takich jak PLANNER. Zasługą jest prawdopodobnie Golomb i Baumert „Backtrack Programming” z 1965 r.
pseudonim
7

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).

Yuval Filmus
źródło
rozumiem twoją odpowiedź, ale nie potrafisz jej właściwie zrozumieć. czy mógłbyś wyjaśnić, w jaki sposób można łatwo wykonać konstrukcję zestawu za pomocą niedeterminizmu?
tanmoy
„Niedeterminizm jest również ważny dla złożoności obliczeń, gdy służy do definiowania klasy NP”. - który potwierdza znaczenie niedeterminizmu tylko wtedy, gdy założymy, że NP jest użyteczną koncepcją, i tylko wtedy, gdy niedeterminizm jest użyteczny.
Raphael
@ Rafael NP-kompletność jest ważną koncepcją niezależnie od twojego stanowiska wobec niedeterminizmu.
Yuval Filmus
2
@Tanmoy Jeśli masz niedeterminizm, nie potrzebujesz konstrukcji powerset, ale niestety prawdziwe komputery są deterministyczne. Niemniej jednak może być łatwiej symulować bezpośrednio NFA niż najpierw przekonwertować go na DFA. Sprawdź odpowiedź, do której link, aby uzyskać więcej informacji.
Yuval Filmus
4

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.

    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.

Raphael
źródło
4

(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.

reinierpost
źródło
2

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.

Massimo Cafaro
źródło
Bezkontekstowy czy deterministyczny Bezkontekstowy?
alt
@alto Co z tym?
babou
@babou Próbowałem wskazać, że „niedeterminizm nie jest czymś potężniejszym od determinizmu”, jest fałszywym stwierdzeniem. NPDA mają większą moc niż PDA.
alt
1
@alto: nie, nie rozumiesz oświadczenia. Z punktu widzenia obliczalności są one w pełni równoważne, ponieważ klasa problemów (lub języków, jeśli wolisz), które możesz rozwiązać NIEZALEŻNIE od tego, ile zasobów obliczeniowych jest wymaganych, jest taka sama. I rzeczywiście, MOŻESZ symulować niedeterministyczną maszynę z deterministyczną. Ponownie, wymagany czas i miejsce NIE MA LICZBY w kontekście obliczalności.
Massimo Cafaro,
1
@MassimoCafaro Teoretycznie nie można się zgodzić. W praktyce wydaje się, że wolę spierać się o semantykę.
alt
2

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.

vzn
źródło
3
Hej, widziałem twój profil i wygląda na to, że ktoś celowo głosuje w dół na twoje odpowiedzi (wszędzie tam, gdzie masz tylko dwa głosy negatywne) ... Ta odpowiedź nie jest zła , odpowiedź dodaje użytecznych informacji. +1
Grijesh Chauhan
0

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.

tanmoy
źródło
Błędem jest twierdzenie, że niedeterministyczna maszyna jest maszyną, która zawsze podąża ścieżką wykonania, która prowadzi do akceptacji ciągu . Nie robi tego! Maszyna niedeterministyczna to maszyna, której działanie pozwala na dokonywanie pewnych nieprecyzyjnych (= niedeterministycznych) wyborów podczas wykonywania. W takich maszynach nie ma nic nierealnego, np. Mogą poprosić środowisko o dokonanie tych wyborów. Te maszyny są następnie stosowane do zadań, dla których uważa, że ​​niektóre wybory spowodują stan akceptacji.
reinierpost
@reinierpost: Mówisz więc, że w rzeczywistości istnieją niedeterministyczne maszyny.
tanmoy
Tak. Oto przykład: załóżmy, że prowadzisz samochód i nie podejmujesz żadnych decyzji dotyczących trasy, którą chcesz podążać. Na przykład możesz jeździć bez celu lub kierować się wskazówkami nawigatora lub urządzenia nawigacyjnego. Samochód i ty jesteś niedeterministycznym systemem kierowania miejscami. Poruszasz się w ruchu ulicznym i ciągle napotykasz wybór kierunku. Dla ciebie i samochodu te wybory nie są deterministyczne: nie decydujesz, w którą stronę pójść, ale biorąc pod uwagę tę decyzję, podążasz za nią.
reinierpost
@reinierpost: Czy istnieje jakiś niedeterministyczny komputer? Moja odpowiedź brzmi nie. ponieważ jeśli istnieje, to problemy NP miałyby wielomianową złożoność czasową. prawda?
tanmoy
To, czy komputery są deterministyczne czy niedeterministyczne, zależy od tego, jak na nie spojrzysz. Gdy komputer zatrzymuje się i czeka, aż użytkownik coś zrobi, a jego następne działania będą zależały od tego, co zrobi użytkownik, można powiedzieć, że jest to wybór niedeterministyczny. Nie, nie oznacza to, że P = NP.
reinierpost
0

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.

Tomek
źródło
Nie jestem pewien, czy rzekome linki do rzeczywistości są w ogóle pomocne. Jest całkiem jasne, że nie możemy zbudować maszyny niedeterministycznej (przynajmniej dzisiaj), więc jest to konstrukcja całkowicie teoretyczna.
Raphael
Możemy zbudować niedeterministyczną maszynę, pozwalając, aby niedeterministyczne decyzje były podejmowane przez coś zewnętrznego względem maszyny.
reinierpost
@ reinierpost, co ważniejsze, możemy budować maszyny niedeterministyczne jako deterministyczne, bez ponoszenia wykładniczego obciążenia. patrz Twierdzenie Savitcha. en.wikipedia.org/wiki/Savitch's_theorem
Tom
@ Raphael, niektóre odniesienia do prawdziwego świata są ważne. Dlaczego działa buforowanie? Ponieważ zdarzenia w świecie rzeczywistym, który ostatecznie jest źródłem wszystkich danych, mają normalny rozkład. patrz miejscowość czasowa: durablescope.blogspot.co.at/2009/11/…
Tom
@ reinierpost, i że coś zewnętrznego jest tym, co Turing nazwał maszyną wyroczni. Myślę, że możesz pomyśleć, czy to jako dane wychodzące z pamięci podręcznej lub coś w rodzaju maszyny z wieloma taśmami, czy nawet sięgające do pamięci o dostępie swobodnym.
Tom
0

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ć.

Thomas Klimpel
źródło
Czy możesz podać konkretny przykład? Trudno mi tutaj zrozumieć, co rozumiesz przez „symetrię”.
Raphael
@Raphael Co powiesz na odwrócenie (01) * 01 (0 + 1) * do (0 + 1) * 10 (10) * w taki sposób, że rozpoznaje odwrócony ciąg wejściowy i stosuje tę symetrię do maszyny niedeterministycznej poprzez odwrócenie wszystkich strzałka i zamiana stanu początkowego i końcowego? Nie jestem pewien, czy istnieją znacznie bardziej interesujące przykłady maszyn o skończonych stanach, ale zamiast tego mógłbym spróbować wymyślić ciekawy przykład dla urządzeń PDA.
Thomas Klimpel
O mojej odpowiedzi na podobne pytanie pisałem w poście na blogu dotyczącym odwracalności relacji binarnych, macierzy podochastycznych i funkcji cząstkowych .
Thomas Klimpel