Determinismus a nedeterminismus

Při strojovém řešení problémů klasickým imperativním programováním je nutné, aby byl řešený problém algoritmizovatelný, čili řešitelný deterministicky. V každém kroku řešení problému je předem dané, jaké kroky budou následovat. Jedná se o tzv. reproduktivní řešící postupy. Oproti tomu v případě nedeterministických, produktivních řešících postupů problémů není zřejmé, jaký krok bude následovat v daném kroku. Výběr dalšího kroku řešení je závislý na výsledku testování podmínky, o které nelze s určitostí říct, zda je či není splněná. Ze samotné formulace problému ani z průběhu jeho řešení není zřejmý další krok řešení. V Jednotlivých krocích řešení můžeme volit z množiny kroků, které budou následovat. Volba následného kroku je tak závislá na hádání, odhadování, volbě či jiném nedeterministickém výběru jednoho z alternativních možností řešení. Čtenář si jistě vzpomene na definici nedeterministického Turingova stroje a jistě si i pamatuje, že nedeterministický TS přijímá slovo, pokud existuje alespoň jedna posloupnost konfigurací končící v koncovém / akceptačním stavu. Formulace „alespoň jedna posloupnost“ říká, že při řešení můžeme dojít do slepé cesty, můžeme se dostat na konfliktu, může existovat jiný, lepší, kratší postup řešení. Volba následujícího kroku tedy není závazná. Můžeme po revizi řešení od současného řešení odstoupit od současného řešení a pokračovat v jiné vhodnější variantě. 

Pro příklad se podívejme na definici TS.

Turingův stroj (TS) je teoretický stroj, který se skládá: • z řídicí jednotky, která se vždy nachází v jednom z konečného množství stavů • ze zleva omezené nekonečné pásky rozdělené na políčka. V každém políčku je zapsán jeden symbol. • z čtecí/zapisovací hlavy, která je vždy umístěna nad jedním políčkem pásky, viz obr.2.1.

 Program Turingova stroje lze chápat jako množinu elementárních instrukcí ve tvaru: „Pokud je řídicí jednotka ve stavu q a čtecí/zapisovací hlava čte symbol a, tak změň stav řídicí jednotky na q 0 , na pásku zapiš a 0 a posuň čtecí/zapisovací hlavu o jedno políčko směrem d.“ Takovou instrukci nazývat přechod. Celý program, tedy množinu takovýchto instrukcí, pak nazýváme přechodovou funkcí Turingova stroje.