El que serveix com a base de les màquines de Turing tant probabilístiques com no deterministes Donada la pregunta anterior, escriu un context que conté la resposta. Pot ser de 1 a 20 frases. Context:
Una màquina de Turing determinista és la màquina de Turing més bàsica, que utilitza un conjunt fix de regles per determinar les seves accions futures. Una màquina de Turing probabilística és una màquina de Turing determinista amb un subministrament extra de bits aleatoris. La capacitat de prendre decisions probabilístiques sovint ajuda els algoritmes a resoldre problemes de manera més eficient. Els algoritmes que utilitzen bits aleatoris s'anomenen algoritmes aleatoritzats. Una màquina de Turing no determinista és una màquina de Turing determinista amb una característica addicional de no determinisme, que permet a una màquina de Turing tenir múltiples accions futures possibles des d'un estat donat. Una manera de veure el no-determinisme és que la màquina de Turing es ramifica en molts camins computacionals possibles en cada pas, i si resol el problema en qualsevol d'aquestes branques, es diu que ha resolt el problema. Clarament, aquest model no està destinat a ser un model físicament realizable, és només una màquina abstracta teòricament interessant que dóna lloc a classes de complexitat particularment interessants. Per a exemples, vegeu Algoritme no determinista.