Niedeterministyczny
Niedeterministyczny (ang. nondeterministic) to przymiotnik opisujący systemy, procesy lub algorytmy, w których wynik nie jest w pełni określony przez ich aktualny stan i reguły działania. W odróżnieniu od deterministycznych modeli, w których przy danym stanie i danych wejściowych zawsze następuje ten sam kolejny stan, modele niedeterministyczne dopuszczają co najmniej dwie różne możliwe ścieżki rozwoju.
Definicja
W kontekście teorii automatów i teorii obliczalności maszyna Turinga jest niedeterministyczna, gdy w pewnym stanie i przy danym symbolu na taśmie istnieje więcej niż jedna dopuszczalna reguła przejścia. W praktyce oznacza to, że maszyna może „wybrać” jedną z wielu możliwych operacji, a wszystkie możliwe rozwinięcia są brane pod uwagę przy analizie jej zachowania.
Zastosowania w informatyce
- Algorytmy niedeterministyczne – np. algorytm przeszukiwania w grafie z wieloma równoległymi ścieżkami.
- Komputacja kwantowa – często modelowana jako niedeterministyczny proces, w którym superpozycja stanów pozwala na jednoczesne rozważanie wielu wyników.
- Problemy klasy NP – definicja klasy NP opiera się na istnieniu niedeterministycznego maszyny Turinga, która w czasie wielomianowym potrafi „odgadnąć” rozwiązanie.
- Logika modalna i temporalna, w której zdania mogą mieć wiele możliwych prawdziwości w zależności od wybranej ścieżki w modelu Kripkego.
Różnice między deterministycznym a niedeterministycznym
| Cecha | Deterministyczny | Niedeterministyczny |
|---|---|---|
| Jednoznaczność przejścia | Jedna reguła dla każdego stanu i symbolu | Możliwość wielu reguł → wybór jednej z nich |
| Analiza zachowania | Jedna jedyna ścieżka wykonania | Wszystkie możliwe ścieżki brane pod uwagę |
| Trudność symulacji | Prosta symulacja na klasycznym komputerze | Wymaga przeszukiwania drzewa stanów (exponential blow‑up) |
Przykłady konkretnych modeli
Do najważniejszych modeli wykorzystujących niedeterminizm należą:
- Niedeterministyczny automat skończenie stanowy (NFA) – używany m.in. w analizie składni języków formalnych.
- Niedeterministyczna maszyna Turinga (NTM) – teoretyczna podstawa klasy NP.
- Sieci neuronowe z losowymi początkowymi wagami – ich trening może mieć elementy niedeterministyczne.
Historia
Pierwsze formalne rozważania nad niedeterministycznym zachowaniem pojawiły się w latach 1940 – 1950 w pracach Alana Turinga i Emila Posta. Koncepcja została później rozwinięta w latach 1960 w ramach badań nad klasą NP i złożonością obliczeniową.
Znaczenie w praktyce
Mimo że w rzeczywistych systemach komputerowych nie istnieje prawdziwy niedeterminizm – komputer zawsze wybiera jedną operację – modele niedeterministyczne są niezwykle przydatne przy:
- Projektowaniu algorytmów optymalizacyjnych, gdzie rozważa się wiele dróg rozwiązania jednocześnie.
- Analizie bezpieczeństwa, np. przy modelowaniu ataków “co‑by‑było”.
- Symulacjach probabilistycznych, które można traktować jako szczególny przypadek niedeterminizmu.
Powiązane pojęcia
Więcej informacji na temat powiązanych zagadnień można znaleźć w następujących artykułach: