Una macchina deterministica Turing è la più semplice, che utilizza un insieme fisso di regole per determinare le sue azioni future. Una macchina probabilistica Turing è una macchina deterministica Turing con una fornitura supplementare di punte casuali. La capacità di prendere decisioni probabilistiche spesso aiuta gli algoritmi a risolvere i problemi in modo più efficiente. Gli algoritmi che utilizzano bit casuali sono chiamati algoritmi randomizzati. Una macchina Turing non deterministica è una macchina Turing deterministica con una caratteristica aggiuntiva di indeterminatezza, che permette ad una macchina Turing di avere molteplici possibili azioni future da un dato stato. Un modo per vedere il non-determinazione è che la macchina Turing si dirama in molti percorsi computazionali possibili ad ogni passo, e se risolve il problema in uno qualsiasi di questi rami, si dice che ha risolto il problema. Chiaramente, questo modello non vuole essere un modello fisicamente realizzabile, ma solo una macchina teoricamente interessante che dà origine a classi di complessità particolarmente interessanti. Per esempi, vedere algoritmo non deterministico.
Qual è il termine dato agli algoritmi che utilizzano bit casuali?
algoritmi randomizzati algoritmi randomizzati algoritmi randomizzati