Jaka jest różnica między niedeterminizmem a przypadkowością?

38

Niedawno to usłyszałem -
„Maszyna niedeterministyczna to nie to samo, co maszyna probabilistyczna. Mówiąc prymitywnie, maszyna niedeterministyczna to maszyna probabilistyczna, w której prawdopodobieństwa przejścia nie są znane”.

Czuję, że rozumiem, ale tak naprawdę nie. Czy ktoś mógłby mi to wyjaśnić (w kontekście maszyn lub ogólnie)?

Edycja 1:
Aby wyjaśnić, cytat był w kontekście skończonego automatu, ale pytanie to ma również znaczenie dla maszyn Turinga, ponieważ inni na nie odpowiedzieli.

Słyszę też, jak ludzie mówią - „... następnie wybieram obiekt x ze zbioru niedeterministycznie”. Kiedyś myślałem, że mają na myśli - „losowo”. Stąd zamieszanie.


źródło
5
W informatyce ludzie czasami używają terminu „deterministyczny”, aby podkreślić, że algorytm nie jest losowy. Stąd zamieszanie: deterministyczny oznacza nierandomizowany, ale niedeterministyczny nie oznacza randomizowany.
Jukka Suomela
2
Zobacz także Różnice i relacje między algorytmami losowymi i niedeterministycznymi?
Gilles 'SO - przestań być zły'
To pytanie prowadzi mnie do tego zakątka SE ...
Troy Woo

Odpowiedzi:

27

Ważne jest, aby zrozumieć, że informatycy używają terminu „niedeterministyczny” inaczej niż zwykle w innych naukach. Niedeterministyczna TM jest faktycznie deterministyczna w sensie fizyki - to znaczy, NTM zawsze daje taką samą odpowiedź na danym wejściu: albo zawsze przyjmuje, albo zawsze odrzuca. Probabilistyczna TM przyjmie lub odrzuci dane wejściowe z pewnym prawdopodobieństwem, więc przy jednym uruchomieniu może je zaakceptować, a przy innym może odrzucić.

Bardziej szczegółowo: Na każdym etapie obliczeń wykonywanych przez NTM zamiast jednej reguły przejścia istnieje wiele reguł, które można wywołać. Aby ustalić, czy NTM akceptuje, czy odrzuca, należy spojrzeć na wszystkie możliwe gałęzie obliczeń. (Więc jeśli, powiedzmy, dokładnie 2 przejścia do wyboru na każdym kroku, a każda gałąź obliczeń ma w sumie N kroków, wówczas będą branych pod uwagę do rozważenia.) W przypadku standardowego NTM, wejście jest akceptowane jeśli jakakolwiek gałąź obliczeniowa akceptuje.2N

Ostatnią część definicji można zmodyfikować, aby uzyskać inne powiązane typy maszyn Turinga. Jeśli jesteś zainteresowany problemami, które mają unikalne rozwiązanie, możesz poprosić TM o zaakceptowanie, jeśli akceptuje dokładnie jeden oddział. Jeśli interesuje Cię zachowanie większościowe, możesz zdefiniować bazę danych do akceptacji, jeśli akceptuje ją więcej niż połowa oddziałów. A jeśli losowo (według pewnego rozkładu prawdopodobieństwa) wybierzesz jedną z możliwych gałęzi i zaakceptujesz lub odrzucisz na podstawie tego, co robi ta gałąź, to masz probabilistyczną bazę TM.

Kurt
źródło
Kurt, czy możesz wyjaśnić, w jaki sposób uzyskano liczbę 2 ^ N. Jeśli dla każdej gałęzi istnieją 2 możliwości i jest N takich etapów, aby dojść do rozwiązania, czy nie byłoby to 2 ^ (N + 1) -1. Próbuję myśleć o tym jak o wykresie i mogę się mylić. Czy możesz wyjaśnić, w jaki sposób doszedłeś do numeru 2 ^ N. Dziękuję Ci.
Gangadhar
Cóż, jeśli reprezentujesz obliczenia jako drzewo, z korzeniem reprezentującym początkową konfigurację jako krok 0, to po N krokach masz 2 ^ N liści, a to, co nazywam gałęzią, jest ścieżką od katalogu głównego do liść. Prawdą jest, że będziesz miał 2 ^ (N + 1) -1 wszystkich węzłów, reprezentujących wszystkie możliwe konfiguracje w pewnym momencie obliczeń. Mam nadzieję, że moja terminologia jest w porządku!
Kurt
Wszystkie nauki stosują tę samą definicję niedeterminizmu zjednoczoną na koncepcji nieograniczonej entropii. Nieprzewidywalne wyniki we wszystkich naukach wynikają z niemożności wyliczenia z góry wszystkich możliwych wyników algorytmu (lub systemu), ponieważ akceptuje on stany nieograniczone, tj. Klasę złożoności NP. Określenie konkretnego wkładu w celu zaobserwowania, czy się on zatrzymuje, i zauważenie, że wynik jest idempotentny, jest równoważne w innych naukach z utrzymaniem reszty entropii wszechświata na stałym poziomie, powtarzając tę ​​samą zmianę stanu. Obliczenia umożliwiają izolację entropii, podczas gdy nauki przyrodnicze nie.
Shelby Moore III,
1
@ShelbyMooreIII Nie. Źle zrozumiałeś pojęcie niedeterminizmu, które pojawia się w informatyce.
David Richerby,
@DavidRicherby przepraszam David. Przejdź do drugiego wątku i przekonaj się, że głośno cię obaliłem. Możesz spróbować obalić logikę, którą tam przedstawiłem. Samo twierdzenie bez dowodów i wyjaśnień nie daje ci żadnej prawdy.
Shelby Moore III,
18

W kontekście Maszyn Turinga „niedeterministyczny” naprawdę oznacza „równoległy”. Randomizowany algorytm może losowo eksplorować gałęzie drzewa obliczeniowego niedeterministycznej maszyny Turinga, ale niedeterministyczna maszyna Turinga może eksplorować je jednocześnie, co daje jej moc.

W innych kontekstach (nie mogę powiedzieć z twojego cytatu, czy mówisz o Maszynach Turinga), algorytm randomizowany może celowo używać losowości, podczas gdy algorytm, który chciałeś być deterministyczny, może w efekcie wykazywać niedeterminizm z powodu błędu ...

W odpowiedzi na Twoją edycję, gdy ludzie mówią „wybierz element ze zbioru niedeterministycznie”, możliwe, że mogą oznaczać „losowo”. Jednak możliwe jest również, że oznaczają one „magicznie wybierz element -right- ze zbioru”. Częstym sposobem przeglądania niedeterministycznych maszyn Turinga jest to, że najpierw magicznie „odgadną” rozwiązanie, a następnie sprawdzą jego poprawność. Oczywiście możesz zobaczyć tę magiczną domysł jako wynik sprawdzania wszystkich możliwości równolegle.

Aaron Roth
źródło
Powiązane z „magicznym wyborem właściwego elementu”: kiedy w tym znaczeniu używa się słowa „niedeterminizm”, ludzie czasem określają go mianem „anielski”. Istnieje również „demoniczny” niedeterminizm. (Mimo to, jak mówisz, istotą jest to, że rzeczy
dzieją
13

Istnieje kilka różnych kontekstów, w których „deterministyczny”, „losowy” i „niedeterministyczny” oznaczają trzy różne rzeczy. W kontekstach, w których jest wielu uczestników, takich jak bezpieczeństwo i współbieżność, intuicja często przypomina:

  • deterministyczne oznacza „mogę wybrać”

  • niedeterministyczny oznacza „ktoś inny może wybrać”

  • losowy oznacza „nikt nie może wybrać”

Kilka przykładów:

  1. [współbieżność, losowa] Rozważ protokół sieciowy, taki jak Ethernet , w którym wiele węzłów może wysłać wiadomość w dowolnym momencie. Jeśli dwa węzły wysyłają wiadomość w bardzo krótkich odstępach czasu, dochodzi do kolizji: wiadomości nakładają się i są nieczytelne. Jeśli dojdzie do kolizji, oba węzły muszą spróbować wysłać wiadomości ponownie później. Wyobraź sobie, że piszesz specyfikację Ethernet. Jak określić opóźnienie między ponownymi próbami? (Opóźnienia powinny być inne, inaczej nastąpi kolizja!)

    • deterministyczny: zdefiniuj algorytm, którego muszą używać oba węzły. Nie dzieje się tak w przypadku sieci Ethernet, ponieważ w celu uzyskania różnych wyników algorytm musiałby uprzywilejować jeden węzeł nad drugim (dla dowolnej zawartości wiadomości), a Ethernet tego nie robi.

    • niedeterministyczny: niech każdy implementator decyduje. Nie jest to dobre, ponieważ implementatory w obu węzłach mogą wybrać ten sam algorytm.

    • random: każdy węzeł musi losowo wybrać wartość opóźnienia (o określonym rozkładzie). Tak to działa. Istnieje małe prawdopodobieństwo, że dwa węzły wybiorą to samo opóźnienie i nastąpi kolejna kolizja, ale prawdopodobieństwo sukcesu wzrasta asymptotycznie w kierunku 1 wraz ze wzrostem liczby ponownych prób.

  2. [współbieżność, niedeterministyczny] Piszesz algorytm współbieżny. W konkretnej sytuacji może wystąpić impas. Jak możesz zapobiec impasowi? To zależy od tego, jaki rodzaj planowania ma środowisko współbieżności.

    • deterministyczny: program planujący zawsze przełącza się między wątkami w pewnych ściśle określonych punktach, np. tylko wtedy, gdy kod wyraźnie ustępuje. Następnie po prostu zadbaj o to, aby nici nie ustępowały w złych momentach.

    • random: program planujący gwarantuje losowe przełączanie wątków. Wtedy wykonalną strategią może być wykrycie impasu, jeśli wystąpi, i zrestartowanie algorytmu od początku.

    • niedeterministyczny (większość harmonogramów jest taka): nie wiesz, kiedy harmonogram przełącza się między wątkami. Więc naprawdę musisz uniknąć impasu. Jeśli spróbujesz wykryć i uruchomić ponownie, jak w przypadkowym przypadku, ryzykujesz, że program planujący zaplanuje twoje wątki w dokładnie ten sam sposób.

  3. [bezpieczeństwo, losowo] Piszesz aplikację z pytaniem o hasło. Jak modelujesz napastnika?

    • deterministyczny: atakujący zawsze próbuje tych samych haseł. To wcale nie jest użyteczny model atakującego - napastnicy nie są z definicji przewidywalni.

    • niedeterministyczny: atakujący w jakiś sposób zna twoje hasło i je wprowadza. To pokazuje ograniczenie haseł: należy je utrzymywać w tajemnicy. Jeśli twoje hasło jest tajne, ten atakujący jest nierealny.

    • random: atakujący losowo próbuje hasła. W tym przypadku jest to realistyczny model atakującego. Możesz dowiedzieć się, ile czasu zajmie osobie atakującej odgadnięcie hasła, w zależności od tego, jakiej używa losowej dystrybucji. Dobre hasło to takie, które długo zajmuje realistyczną dystrybucję.

  4. [bezpieczeństwo, niedeterministyczny] Piszesz aplikację i martwisz się, że może mieć dziurę w zabezpieczeniach. Jak modelujesz napastnika?

    • deterministyczny: atakujący wie wszystko, co wiesz. Znowu nie jest to przydatny model atakującego.

    • random: atakujący wyrzuca losowe śmieci i ma nadzieję, że twój program się zawiesi. Czasami może to być przydatne ( fuzzing ), ale atakujący może być bardziej sprytny.

    • niedeterministyczny: jeśli jest dziura, atakujący ją w końcu znajdzie. Lepiej więc zahartuj swoją aplikację (podnieś wymaganie inteligencji atakującego; zwróć uwagę, że ponieważ jest to wymóg inteligencji, a nie wymóg obliczeniowy, liczy się to jako niedeterministyczne, dopóki nie pojawi się AI), lub lepiej, udowodnij, że nie ma dziura w zabezpieczeniach i dlatego taki atakujący nie istnieje.

Gilles „SO- przestań być zły”
źródło
Korekta obraca się wokół brakującego słowa udowodnić w twoich wypowiedziach: Deterministyczny to „Mogę udowodnić, że wybieram (tj. W pełni określając wynik, który kończy się na moim wejściu w klasie złożoności P)”, Niedeterministyczny jest „Nie mogę udowodnić, że wybieram (tj. dowód zakończenia jest niezdecydowany w klasie złożoności NP) ”, a losowy to„ Mogę udowodnić, że mogę wybrać ½ czasu (tj. klasa złożoności ZPP) ”.
Shelby Moore III,
@ShelbyMooreIII Nie rozumiem, do czego zmierzasz. Determinizm na ogół nie polega na udowodnieniu, że coś jest rzeczywiście deterministyczne, ani na tym, że jakiś problem należy do określonej klasy złożoności. Co więcej, klasy złożoności nie polegają na tym, że sam system jest w stanie udowodnić coś o swoim determinizmie (większość problemów nawet nie ma pojęcia o udowodnieniu w systemie!).
Gilles „SO - przestań być zły”,
Niedeterminizm jest zawsze wynikiem nieograniczonej entropii, dlatego też można powiedzieć, że nie mogę udowodnić, że wybieram wynik (ponieważ nie mogę udowodnić, że mój wybór się skończy). Wszystko, co mogę zrobić, to spróbować, co oznacza, że ​​muszę wymienić każdy wybór, który chcę podjąć, zanim będę wiedział, czy to się skończy. Natomiast determinizmem mogę udowodnić, że wybieram wynik, który musi zakończyć. Randomizacja jest miejscem, w którym mogę udowodnić, że wybieram tylko losową ilość czasu, ponieważ część entropii nie jest pod moją kontrolą. Jeśli znam kwotę, która nie jest pod moją kontrolą, mogę udowodnić dokładne statystyki.
Shelby Moore III,
Zgadza się, że to nie klasa złożoności NP powoduje niedeterminizm, a NP jest zależnością. Turing-complete jest przykładem niedeterminizmu. Proszę zobaczyć mój komentarz pod odpowiedzią Kurta, a także moją odpowiedź na powiązany wątek . Chodzi mi o to, co dokładnie zostało udowodnione i nieprzewidywalne dla terminów deterministycznych, niedeterministycznych i przypadkowych. Chodzi o entropię (a nie bas )
Shelby Moore III
9

Przykład, aby wyjaśnić:

Powiedz, że musisz wybrać drzwi do otwarcia wśród 10000 drzwi (powiedz, że za jednymi z nich stoi nagroda). Wybór losowy oznacza, że ​​wybierzesz jedno ze 10000 drzwi i wejdziesz do niego. Jeśli za jednymi drzwiami jest nagroda, najprawdopodobniej jej nie znajdziesz. Niedeterministyczna maszyna wszedłaby jednocześnie do wszystkich 10000 drzwi. Jeśli gdziekolwiek jest nagroda, niedeterministyczna maszyna ją znajdzie.

Robin Kothari
źródło
8
Alternatywnie, niedeterministyczna maszyna otworzyłaby tylko jedne drzwi, ale zawsze byłaby właściwa.
Jeffε
3
Tak, dokładnie. To byłaby „najszczęśliwsza możliwa zgadywanka” charakterystyka niedeterministycznych maszyn.
Robin Kothari
@RobinKothari: „Alternatywnie, niedeterministyczna maszyna otworzyłaby tylko jedne drzwi, ale zawsze byłaby właściwa”. I „Niedeterministyczna maszyna wszedłaby do wszystkich 10000 drzwi jednocześnie”? - Która z nich jest poprawna?
tanmoy
3
@tan: Obie są poprawnymi interpretacjami. W przeciwieństwie do deterministycznych i losowych maszyn, które są fizycznie możliwe do zrealizowania, niedeterministyczna maszyna jest wyimaginowanym obiektem. Możesz więc sobie to wyobrazić, jak chcesz, chodzi o to, że zawsze znajdzie właściwe drzwi. Może to najlepszy zgadywacz, może ktoś potajemnie powiedział maszynie, gdzie była nagroda, może po prostu magicznie sprawdza wszystkie drzwi itp.
Robin Kothari
5

Definicja niedeterministycznej maszyny Turinga : Maszyna Turinga, która ma więcej niż jeden następny stan dla niektórych kombinacji zawartości bieżącej komórki i bieżącego stanu. Dane wejściowe są akceptowane, jeśli jakakolwiek sekwencja ruchu prowadzi do akceptacji.

Definicja probabilitycznej maszyny Turinga : niedeterministyczna maszyna Turinga (TM), która losowo wybiera pomiędzy dostępnymi przejściami w każdym punkcie zgodnie z pewnym rozkładem prawdopodobieństwa.

Probabilistyczna maszyna Turinga to niedeterministyczna maszyna Turinga, która może popełniać błędy.

PPT uważam za pomocny.

Pratik Deoghare
źródło
5

Wolę następującą definicję:

Nie ma czegoś takiego jak probabilistyczna maszyna Turinga! Istnieją tylko maszyny deterministyczne (na każdym etapie pojedynczy możliwy stan kontrolny) i maszyny niedeterministyczne (na każdym etapie stała liczba możliwych stanów kontrolnych).

Niedeterminizm działa w następujący sposób: Rozważ maszynę niedeterministyczną, która zatrzymuje się na każdym wejściu (możliwe, jeśli problem jest rozstrzygalny), w której każde możliwe obliczenie wykorzystuje tę samą liczbę kroków i gdzie każdy krok ma dokładnie 2 możliwe stany kontrolne ( oba nie są tak naprawdę ograniczeniem). Podobnie jak w definicji NP, niedeterministyczna maszyna przyjmuje dane wejściowe, jeśli istnieje co najmniej jedno możliwe obliczenie akceptujące, a odrzuca dane wejściowe, jeśli wszystkie obliczenia odrzucają.

Losowość wchodzi w grę w następujący sposób: Możesz wybrać jednolicie losowo pojedynczą ścieżkę obliczeń z takiej niedeterministycznej maszyny, jak wspomniano powyżej. Akceptujesz wtedy i tylko wtedy, gdy ta losowo wybrana ścieżka obliczeniowa akceptuje. To randomizowane podejście „rozwiązuje” Twój problem, jeśli z ogromnym prawdopodobieństwem ta odpowiedź jest poprawna.

Tak więc różnica między niedeterminizmem a przypadkowością polega na tym, czy szukasz zwykłego istnienia prawidłowej odpowiedzi typu „tak” (i wiarygodnych odpowiedzi „nie”), czy też jesteś zainteresowany rozwiązaniem swojego problemu „przez większość czasu” .

MRA
źródło
-1 Błędy w pierwszym akapicie. Istnieją probabilistyczne maszyny Turinga i próbkują rzut monetą z zewnętrznej entropii, por. Klasa złożoności ZPP. Niedeterminizm ma nieograniczoną, a nie skończoną liczbę stanów alternatywnych, patrz klasa złożoności NP. Determinizm jest klasą złożoności P i poprawnie to zrozumiałeś.
Shelby Moore III,
Myślę, że źle rozumiesz moją odpowiedź. Twierdzę, że nie potrzebujesz żadnej innej maszyny (z rzucaniem monetą lub innymi możliwościami) niż „zwykła” niedeterministyczna TM do definiowania probabilistycznych klas złożoności. Równie dobrze możesz użyć NTM i po prostu użyć innej definicji akceptacji, a mianowicie definicji, w której „większość ścieżek obliczeniowych akceptuje dane wejściowe”, w przeciwieństwie do „istnieje przynajmniej jedna ścieżka akceptacji danych wejściowych”.
MRA,
3

Mówiąc prościej: niedeterministyczna maszyna może optymalnie wybrać wynik każdego rzutu monetą (jeśli podoba ci się analogia z maszyną probabilistyczną). Można sobie również wyobrazić, że wykonuje obliczenia dla każdego wyniku rzutu monetą równolegle.

Serge Gaspers
źródło
1

Cofanie się podczas debugowania jako motywacja do niedeterminizmu

Pojęcie niedeterministycznej maszyny sugeruje się, gdy chcesz przejść wstecz (w czasie) przez program podczas debugowania. Na typowym komputerze każdy krok modyfikuje tylko skończoną ilość pamięci. Jeśli zawsze zapisujesz te informacje dla poprzednich 10000 kroków, możesz ładnie poruszać się zarówno do przodu, jak i do tyłu w programie, a ta możliwość nie ogranicza się do programów zabawkowych. Jeśli spróbujesz usunąć asymetrię między krokami naprzód i krokami wstecznymi, to skończy się to pojęciem niedeterministycznej maszyny.

Podobieństwa i różnice między niedeterminizmem a przypadkowością

Chociaż maszyny probabilistyczne mają pewne cechy wspólne z maszynami niedeterministycznymi, ta symetria między krokami do przodu i krokami do tyłu nie jest wspólna. Aby to zobaczyć, modelujmy kroki lub przejścia maszyny deterministycznej za pomocą (całkowitych lub częściowych) funkcji, przejścia maszyny niedeterministycznej przez (skończone) relacje oraz przejścia maszyny probabilistycznej za pomocą (pod) macierzy stochastycznych . Na przykład tutaj są odpowiednie definicje automatów skończonych

  • Q
  • Σ
  • δ:Q×ΣQ
  • Δ:Q×ΣP(Q)
  • ΔQ×Σ×Q
  • Δ:ΣP(Q×Q)
  • δ:ΣssM(Q)

P(Q)QssM(Q)Q

Istnieje wiele różnych uzasadnionych warunków akceptacji

Przejścia są tylko jedną częścią maszyny, stany początkowe i końcowe, możliwe warunki wyjściowe i akceptacyjne są również ważne. Istnieje jednak bardzo niewiele nierównoznacznych warunków akceptacji dla maszyn deterministycznych, szereg rozsądnych warunków akceptacji dla maszyn niedeterministycznych (NP, coNP, #P, ...) i wiele możliwych warunków akceptacji dla maszyn probabilistycznych. Dlatego odpowiedź ta koncentruje się przede wszystkim na przejściach.

Odwracalność nie jest trywialna dla maszyn probabilistycznych

PPTPPPBAkABk

Odwracalność jest trudna nawet w przypadku maszyn niedeterministycznych

PPTPPRRopRRRRRRopR=RRopRRop=RopPQPQ

Te rozważania mają również sens w przypadku automatów wypychających

Ten post sugeruje, że jedną z motywacji dla niedeterminizmu jest usunięcie tej asymetrii między krokami naprzód i krokami wstecz. Czy ta symetria niedeterminizmu ogranicza się do automatów skończonych? Oto odpowiednie definicje symetryczne dla automatów pushdown

  • Q
  • Σ
  • Γ
  • δ:Q×Γ×(Σ{ϵ})Q×Γ{0,2}δ(q,γ,ϵ)ϵδ(q,γ,σ)=ϵσΣ
  • Δ:Q×Γ{0,1}×(Σ{ϵ})P(Q×Γ{0,1})
  • ΔQ×Γ{0,1}×(Σ{ϵ})×Q×Γ{0,1}
  • Δ:Σ{ϵ}P(Q×Γ{0,1} × Q×Γ{0,1})
  • δ:Σ{ϵ}ssM(Q×Γ{0,1})δ(ϵ)+δ(σ)ssM(Q×Γ{0,1})σΣ

ϵΓ{0,2}={ϵ}Γ(Γ×Γ)Γ{0,1}={ϵ}ΓΓ

Schematyczna weryfikacja odwrócenia dla (nie) zaawansowanych operacji wprowadzania i stosu

bΣΣ{ϵ}

a|bca|bcab|c
a|bcab|cab|c
c|bac|bacb|a

ϵΣ{ϵ}

a|bca|bca|bc
a|bca|bca|bc
cb|acb|acb|a

Oto schemat postępującej operacji wprowadzania, której odwrócenie wyglądałoby źle

a|bca|bcab|ca|bcab|cab|cc|bac|bacb|a

Dla operacji na stosie istnieją trzy przypadki , i . Operacja na stosie zostaje odwrócona na w następujący sposób(s,t)Γ{0,1}×Γ{0,1}(s,t)=(a,ϵ)(s,t)=(ϵ,a)(s,t)=(a,b)(a,ϵ)(ϵ,a)

abab|b
ab|bb
b|bab

Operacja na stosie zostaje odwrócona do w następujący sposób(a,b)(b,a)

acacbc
acbcbc
bcbcac

Uogólniona operacja stosu zostałaby odwrócona do(ab,cde)Γ×Γ(cde,ab)

b f ... c d e f ... c d e f ... c d e f ... c d e f ... b f ...abfabfcdef
abfcdefcdef
cdefcdefabf

Odwracalność dla maszyn Turinga

Maszyna z więcej niż jednym stosem jest równoważna maszynie Turinga, a operacje na stosie można łatwo odwrócić. Motywacja na początku sugeruje również, że odwrócenie (maszyny Turinga) nie powinno być trudne. Maszyna Turinga z typowym zestawem instrukcji nie jest tak świetna do cofania, ponieważ symbol pod głową może wpływać na to, czy taśma przesunie się w lewo czy w prawo. Ale jeśli zestaw instrukcji zostanie odpowiednio zmodyfikowany (bez zmniejszania mocy obliczeniowej maszyny), wówczas odwrócenie jest znowu prawie banalne.

Odwrócenie można również wykonać bez modyfikowania zestawu instrukcji, ale nie jest ono kanoniczne i trochę brzydkie. Może się wydawać, że istnienie odwrócenia jest równie trudne do rozstrzygnięcia, jak wiele innych pytań dotyczących maszyn Turinga, ale odwrócenie jest lokalną konstrukcją, a trudne pytania często mają charakter globalny, więc pesymizm byłby tutaj prawdopodobnie nieuzasadniony.

Chęć przejścia na równoważne zestawy instrukcji (łatwiejsze do odwrócenia) pokazuje, że pytania te są mniej oczywiste, niż się pojawiają. Bardziej subtelna zmiana miała miejsce w tym poście wcześniej, gdy funkcje całkowite i macierze stochastyczne zostały zastąpione funkcjami częściowymi i macierzami podochastycznymi. Ten przełącznik nie jest absolutnie konieczny, ale w przeciwnym razie zmiana jest brzydka. Przejście na macierze substochastyczne było w rzeczywistości punktem, w którym stało się oczywiste, że odwracalność wcale nie jest tak trywialna, i że należy zapisać szczegóły (jak to zrobiono powyżej) zamiast przyjmować jedynie perspektywę na wysokim poziomie (przedstawioną w motywacji na początek). Pytania zadane przez Niel de Beaudrap przyczyniły się również do uświadomienia sobie, że perspektywa wysokiego poziomu jest nieco niepewna.

Wniosek

Maszyny niedeterministyczne umożliwiają skończoną liczbę deterministycznych przejść na każdym etapie. W przypadku maszyn probabilistycznych przejścia te mają dodatkowo prawdopodobieństwo. Ten post przedstawia inne spojrzenie na niedeterminizm i przypadkowość. Ignorując globalne warunki akceptacji, koncentruje się na lokalnej odwracalności (jako lokalnej symetrii). Ponieważ losowość zachowuje pewne lokalne symetrie, których determinizm nie zachowuje, perspektywa ta ujawnia nietrywialne różnice między maszynami niedeterministycznymi i probabilistycznymi.

Thomas Klimpel
źródło
Czy zakładasz, że niedeterministyczne przejścia są relacjami jeden do wielu? Co zrobić, jeśli dwie różne konfiguracje mogą przejść między innymi do wspólnej konfiguracji? - Wydaje mi się, że różnica między przypadkowością a niedeterminizmem nie polega na odwracalności (nie ma też żadnych ograniczeń), ale raczej na tym, jak przypisuje się znaczenie gałęziom zgodnie z rezultatem: idealnie demokratyczny dla przypadkowości lub preferencyjnie wrażliwy na „tak” lub „nie” odpowiada za niedeterminizm.
Niel de Beaudrap,
@NieldeBeaudrap Zakładam, że niedeterministyczne przejścia są relacjami „arbitralnymi” (po jednym dla każdego symbolu z alfabetu wejściowego). Mogę je odwrócić, zamienić stan początkowy i końcowy, i ponownie uzyskać niedeterministyczną maszynę skończoną, która akceptuje odwrócony ciąg wejściowy. To właśnie nazywam „uruchom maszynę do tyłu w czasie”. (Maszyna akceptuje, jeśli istnieje co najmniej jedna ścieżka od stanu początkowego do końcowego w przypadku niedeterministycznym, a warunek ten nie zmienia się podczas cofania czasu.) Spróbuj przekonać się, że działa to przynajmniej dla maszyny o skończonym stanie .
Thomas Klimpel
Odwołujesz się więc do dualnego urządzenia. Dla NFA wydaje się to sensownym pojęciem odwracalności. Oczywiste jest również, że dualność NTM (z jednym stanem akceptacji) jest kolejnym NTM, ale wahałbym się powiedzieć, że jest to ta sama maszyna działająca w odwrotnej kolejności. Czy twoja odpowiedź sprowadza się tylko do: „Niedeterminizm pozwala ci uzyskać zamknięcie w dualnych, losowych (i deterministycznych) maszynach nie”?
Niel de Beaudrap,
@NieldeBeaudrap Moim pomysłem jest bieganie wstecz w czasie, ale wiem, że nie jest to idealnie spełnione (ponieważ warunki dla uogólnionego odwrotności odwrotnej półgrupy nie są spełnione). Ale próbowałem przekazać, że losowe (i deterministyczne) maszyny nie zawsze pozwalają na tego rodzaju odwrócenie.
Thomas Klimpel
Odpowiedź napisałem w blogu na temat Odwracalności relacji binarnych, macierzy podochastycznych i funkcji cząstkowych .
Thomas Klimpel
0

n2n stanów wykładniczych) przez uwzględnienie klas równoważności stanów, bez względu na to, czy algorytm zaimplementowany w maszynie obejmuje randomizację lub prawdopodobieństwa (patrz poniżej).

Ale jeśli algorytm zaimplementowany w maszynie wiąże się z randomizacją lub prawdopodobieństwami (nieodłącznymi w algorytmie), to jest to maszyna losowa (lub probabilistyczna).

Zasadniczo zawsze możliwe jest usunięcie niedeterminizmu z maszyny i skonstruowanie deterministycznego odpowiednika (patrz algorytm powyżej), ale nie można tego zrobić (ogólnie) w celu usunięcia randomizacji (w kontekście powyższego), ponieważ jest to nieodłączny od zaimplementowanego algorytmu .

Zauważ, że w świetle powyższego, zarówno maszyna deterministyczna , jak i maszyna niedeterministyczna mogą być probabilistyczne, jeśli algorytm (zaangażowany) używa w ten sposób randomizacji (lub prawdopodobieństw).

Podsumowując, niedeterminizm w automatach (w tym kontekście) odnosi się do klas podobnych automatów, podczas gdy maszyny losowe lub probabilistyczne odnoszą się do (rzeczywistego zastosowania randomizacji w) rzeczywistych algorytmów zaimplementowanych przez te automaty.

Nikos M.
źródło