Zer da probabilitatezko eta ez-deterministikoko Turing-makinen oinarria Aurreko galdera kontuan hartuta, idatzi erantzuna duen testuingurua. 1etik 20 esaldietara. Kontestu bat
Turing-makina deterministikoa Turing-makinarik oinarrizkoena da, bere etorkizuneko ekintzak zehazteko arau multzo finko bat erabiltzen duena. Turing-makina probabilistiko bat Turing-makina deterministiko bat da, bit aleatorioren hornidura gehigarria duena. Erabaki probabilistikoak hartzeko gaitasunak askotan laguntzen die algoritmoei arazoak modu eraginkorragoan ebazten. Ausazko bitak erabiltzen dituzten algoritmoei algoritmo ausazkoak deitzen zaie. Turing-makina ez-deterministikoa ez-determinismoaren ezaugarri gehigarria duen Turing-makina deterministikoa da, eta horrek ahalbidetzen dio Turing-makinari etorkizuneko ekintza posible ugari izatea egoera jakin batetik. Ez-determinismoa ikusteko modu bat da Turing makinak urrats bakoitzean kalkulu bide posible askotan adarkatzen dela, eta adar horietako edozeinetan arazoa konpontzen badu, arazoa konpondu duela esaten da. Argi dago, eredu honek ez du eredu fisiko gauzagarri bat izan nahi, teorikoki interesgarria den makina abstraktu bat baino ez da, konplexutasun klase bereziki interesgarriak sortzen dituena. Adibideetarako, ikusi algoritmo ez-deterministikoa.