Ce servește ca bază atât a mașinilor de Turing probabilistice, cât și a celor nedeterministe Având în vedere întrebarea anterioară, scrie un context care conține răspunsul. Poate fi de la 1 la 20 de propoziţii. Contextul:
O mașină de Turing deterministă este cea mai simplă mașină de Turing, care folosește un set fix de reguli pentru a-și determina acțiunile viitoare. O mașină de Turing probabilistă este o mașină de Turing deterministă cu o cantitate suplimentară de biți aleatori. Capacitatea de a lua decizii probabilistice ajută adesea algoritmii să rezolve problemele mai eficient. Algoritmii care folosesc biți aleatorii sunt numiți algoritmi aleatorii. O mașină de Turing nedeterministă este o mașină de Turing deterministă cu o caracteristică suplimentară de nedeterminism, care permite unei mașini de Turing să aibă mai multe acțiuni viitoare posibile dintr-o anumită stare. Un mod de a vedea non-determinismul este că mașina Turing se ramifică în multe căi computaționale posibile la fiecare pas, și dacă rezolvă problema în oricare dintre aceste ramuri, se spune că a rezolvat problema. În mod clar, acest model nu este menit să fie un model realizabil fizic, este doar o mașină abstractă teoretic interesantă care dă naștere unor clase de complexitate deosebit de interesante. Pentru exemple, a se vedea algoritmul nedeterminist.