Zdaję sobie sprawę z tego, że niedeterministyczne automaty wypychające mogą być ulepszeniem w stosunku do automatów deterministycznych, ponieważ mogą „wybierać” spośród kilku stanów i istnieje kilka języków bezkontekstowych, których nie można zaakceptować przez deterministyczne przepychanie.

Nadal nie rozumiem, jak dokładnie „wybierają”. Na przykład w przypadku palindormes każde znalezione źródło mówi tylko, że automat „zgaduje” środek słowa. Co to znaczy?

Mogę wymyślić kilka możliwych znaczeń:

1. Przechodzi losowo w jeden stan i dlatego może nie zaakceptować słowa, które faktycznie jest w języku

2. W jakiś sposób idzie to „każdą możliwą drogą”, więc jeśli pierwszy jest błędny, sprawdza, czy którykolwiek z nich może być poprawny

3. Istnieje pewien mechanizm, którego nie znam, który wybiera środek słowa i dlatego nie jest przypadkowy, ale automat zawsze znajduje właściwy środek.
   

To tylko przykład; Chcę wiedzieć, jak to działa dla każdego automatu, który ma kilka następujących stanów dla tego samego stanu przed nim.

Po prostu mechanizm jest magiczny. Idea niedeterminizmu polega na tym, że po prostu wie, którą drogą powinien przyjąć, aby zaakceptować słowo, i idzie w tym kierunku. Jeśli istnieje wiele sposobów, idzie jeden z nich.

Niedeterminizm nie może być zaimplementowany jako taki na prawdziwym sprzęcie. Symulujemy to za pomocą technik takich jak cofanie. Ale jest to przede wszystkim urządzenie teoretyczne, które można wykorzystać w celu uproszczenia prezentacji niektórych pojęć.

W przypadku palindromu możesz o tym myśleć na dwa sposoby. Albo istnieje magiczna moc, która pozwala twojej maszynie powiedzieć „to jest środek słowa, czas na przejście od pchania do poppingu”, lub po przeczytaniu każdej litery, mówi: „Rozwiążę nowy proces, niż ta litera jest w środku słowa i sprawdź, czy znajdzie palindrom. Następnie w tym drugim wątku spróbuję, zakładając, że to nie jest środek słowa ".

Innym sposobem myślenia o tym jest nieskończony paralelizm. Tak więc równoważnym modelem byłoby to, że zamiast wybierać nową ścieżkę, jednocześnie wypróbowuje obie ścieżki, rozgałęziając nowe „procesy”, odnosząc sukces, jeśli są w końcowym stanie po przeczytaniu całego słowa. Ponownie, nie można tego zbudować przy użyciu prawdziwego sprzętu, ale można go modelować z niedeterminizmem.

Interesującą cechą niedeterminizmu jest to, że w przypadku automatów skończonych i maszyn Turinga wcale nie zwiększa to ich mocy obliczeniowej, a jedynie ich wydajność.

Główną różnicą (moim zdaniem) między automatem deterministycznym a automatem niedeterministycznym jest to, że dla automatu deterministycznego dane słowo wejściowe ma tylko jedną ścieżkę przez maszynę. W niedeterministycznym automacie dane słowo wejściowe może mieć wiele ścieżek przez maszynę (ponieważ w niektórych punktach może istnieć wybór).

W świetle tego warunek akceptacji słowa wejściowego również wymaga zmiany, aby uwzględnić fakt, że słowo może indukować kilka ścieżek przez maszynę. Zwykła definicja akceptacji dla niedeterministycznego automatu jest następująca: Aby słowo zostało zaakceptowane przez automat, musi istnieć co najmniej jedna ścieżka akceptacji indukowana przez to słowo.

To z kolei prowadzi do idei „zgadywania” automatu, jeśli słowo zostanie zaakceptowane przez niedeterministyczny automat, wówczas uważamy, że automat automatycznie dokonuje właściwych wyborów, tak aby (jedna z) ścieżek akceptacji następuje, gdy to słowo jest przedstawiane jako wejście.

Dla palindromów oznacza to, że pda będzie zasadniczo miał dwa tryby: tryb pchania, w którym wypycha bieżące litery na stosie, i tryb pstrykania, w którym wypycha te litery i dopasowuje je do wejścia. Ta maszyna będzie miała puste przejście ze stanu pchania do stanu wyskakiwania, które będzie mogła podążać w dowolnym punkcie słowa. Jednak maszyna opróżni swój stos i przejdzie do stanu akceptacji tylko wtedy, gdy przeczytała palindrom i podąży za pustym przejściem na środku palindromu. Ponieważ wymagamy jedynie istnienia ścieżki akceptacji, możemy powiedzieć, że automat „zgaduje”, gdzie jest środek słowa.

Idea niedeterminizmu jest dość prosta: w niektórych sytuacjach automat może wykonać kilka kolejnych kroków. Automat akceptuje, jeśli istnieje pewna (może być kilka!) Sekwencja kroków prowadząca od konfiguracji początkowej do akceptowalnej, odrzuca tylko wtedy, gdy takiej sekwencji nie ma .

Oznacza to, że „decyduje”, jaki krok podjąć w tych dwuznacznych sytuacjach. Jednym ze sposobów mówienia o tym jest powiedzenie, że magicznie wybiera zawsze „właściwy” następny krok (lub jeden, jeśli jest kilka „właściwych” kroków). Innym sposobem na zobaczenie jest to, że w takich sytuacjach obliczenia automatu dzielą się na kilka kopii, z których każda podąża jedną ścieżką.

W praktyce można to zrealizować przez cofnięcie, umieszczenie jakiejś formy znacznika w miejscach, w których podjęto decyzję, i wrócenie i wypróbowanie kolejnej alternatywy, jeśli bieżąca ścieżka nie zadziała. Zwykle jest to obsługiwane przez rekurencję. Lub uzupełnienie informacji, które ma „legalnie” automat o dodatkowe informacje (to właśnie robisz, gdy pokazujesz, jak automat niedeterministyczny działa na tablicy, patrząc w przyszłość i zastanawiając się, który krok prowadzi do sukcesu).

„Zgadywanie” jest bezpośrednio związane z naszą egzystencjalną interpretacją niedeterminizmu

W skrócie: Idea, że ​​automat niedeterministyczny może odgadnąć (lub wyrocznia może mu pomóc) jest bezpośrednio związana z naszą egzystencjalną interpretacją niedeterminizmu. Możliwa jest inna interpretacja (być może inne), w której „zgadywanie” nie miałoby sensu.

Brak determinizmu jest dziwny. Mamy jeden sposób interpretacji tego w teorii automatów, ale z góry nie jest oczywiste, jak powinniśmy to zrobić.

Może się to wydawać zaskakujące, ale niedeterminizm jest bardzo częstą sytuacją. Kiedy trzeba udowodnić twierdzenie, biorąc pod uwagę aksjomaty niektórych teorii matematycznych, proces ten jest oczywiście niedeterministyczny. Dlatego często nie wiemy, co zrobić, aby rozwiązać problem, na przykład znaleźć rozwiązania równania trzeciego stopnia lub udowodnić jakieś twierdzenie.

Istnieje wiele sposobów łączenia tego, co już wiadomo, z regułami wnioskowania, aby uzyskać nowe wyniki. Sytuacja jest zwykle taka sama, jeśli próbujemy zrekonstruować dowód wstecz od wyniku.

Próbując rozwiązać taki problem, staramy się „ odgadnąć ” ścieżkę w jakimś systemie przejściowym.

Właściwie nie zgadujemy, ale budujemy w umyśle jakąś strukturę, która organizuje i / lub upraszcza labirynt możliwości, dzięki czemu możemy zobaczyć naszą ścieżkę. W niektórych przypadkach pytanie jest zgodne ze zidentyfikowanym wzorcem, dla którego mamy standardowy sposób (czasem? Zwykle? Zawsze?) Znalezienia rozwiązania, i nazywamy to algorytmem.

Jedną (zwykle kosztowną) techniką, którą możemy zastosować, jest po prostu pełne zbadanie labiryntu: podążanie wszystkimi ścieżkami, robiąc to najpierw, aby uniknąć złapania w nieskończony podgraf. Tak właśnie się dzieje poprzez łączenie wszystkich możliwych obliczeń niedeterministycznego automatu. To pochodne obliczenie typu „jaskółczy ogon” samo w sobie jest deterministyczne.

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

W rzeczywistości mogą istnieć różne sposoby interpretacji obliczeń niedeterministycznych . Afaik wszyscy są konsekwentni, ale nie ze sobą.

$R$$w$

Pomysł zgadywania dla programu rozpoznającego jest tylko obrazem z naszego własnego sposobu „zgadywania”, jak znaleźć to drzewo dowodu. Ale duża różnica polega na tym, że nasze mózgi nie są palmtopami. Są to znacznie bardziej złożone urządzenia z możliwością eksploracji i mapowania w przybliżeniu struktur przejściowych, dzięki czemu możemy znaleźć drogę przez nie, co czasem postrzegamy jako zgadywanie.

Ta interpretacja obliczeń niedeterministycznych jest tym, co nazwałbym akceptacją egzystencjalną , w odniesieniu do faktu, że wymaga ona tylko jednego obliczenia akceptującego. Odpowiada to zahamowaniu egzystencjalnym, które wprowadziłem w innej odpowiedzi .

Jednak można również interpretować niedeterminizm w sposób uniwersalny, ponieważ: mówi się, że rozpoznający (uniwersalnie) akceptuje dane wejściowe „w”, jeśli wszystkie możliwe obliczenia zostają zatrzymane i akceptują dane wejściowe. Ta uniwersalna akceptacja odpowiada koncepcji uniwersalnego zatrzymania wprowadzonej w tej samej odpowiedzi.

Powszechna akceptacja i uniwersalne wstrzymanie wydają się prowadzić do spójnego zrozumienia niedeterminizmu. Stąd można teoretycznie pracować z tą definicją. Nie jest to jednak zgodne z naszą zwykłą praktyką w wielu sytuacjach niedeterministycznych, takich jak dowodzenie twierdzeń, lub w sytuacjach życia codziennego. Kiedy napotykamy problem, chcemy tylko jednego sposobu jego rozwiązania, a potem nie dbamy o to, czy inne sposoby się powiodą, czy nie (cóż, jest to nieco zbyt uproszczone).

Jeśli musimy rozpoznać palindrom, możemy zgadywać, mierząc długość i szukając środka. PDA nie może. Ale ponieważ jesteśmy zainteresowani istnieniem tylko jednego rozwiązania, zawsze możemy udawać, że może ... jeśli to pomoże. Albo możemy uznać, że ma wyrocznie dostarczone przez bardziej inteligentne maszyny (nam?), Aby im pomóc. Lub możesz nawet nazwać to magią i myśleć, że tak (w końcu kwantyfikator egzystencjalny jest rodzajem magicznej różdżki). Jeśli to pomoże, to pomoże. Jeśli obliczenia nie będą akceptowane, żadna pomoc nie będzie przydatna.

Zauważ, że ta koncepcja zgadywania byłaby bez znaczenia w uniwersalnej interpretacji akceptacji.