Mesin Turing deterministik adalah mesin Turing paling dasar, yang menggunakan seperangkat aturan tetap untuk menentukan tindakan di masa depan. Mesin Turing probabilistik adalah mesin Turing deterministik dengan pasokan tambahan bit acak. Kemampuan untuk membuat keputusan probabilistik seringkali membantu algoritma memecahkan masalah dengan lebih efisien. Algoritma yang menggunakan bit acak disebut algoritma acak. Mesin Turing non-deterministik adalah mesin Turing deterministik dengan fitur tambahan non-determinisme, yang memungkinkan mesin Turing memiliki beberapa kemungkinan tindakan di masa mendatang dari kondisi tertentu. Salah satu cara untuk melihat non-determinisme adalah bahwa mesin Turing bercabang menjadi banyak jalur komputasi yang mungkin pada setiap langkah, dan jika itu memecahkan masalah di salah satu cabang ini, dikatakan telah memecahkan masalah. Jelas, model ini tidak dimaksudkan untuk menjadi model yang dapat diwujudkan secara fisik, melainkan hanya sebuah mesin abstrak yang menarik secara teoritis yang memunculkan kelas kompleksitas yang sangat menarik. Sebagai contoh, lihat algoritma non-deterministik.
Apa yang tidak sering membantu algoritma menyelesaikan masalah dengan lebih efisien?
Kemampuan untuk membuat keputusan yang probabilistik
Kemampuan untuk membuat keputusan probabilistik
Apa PRI
yang PRR
tidak NEG
sering ADV
membantu VBT
algoritma NNO
menyelesaikan VBT
masalah NNO
dengan PPO
lebih ADV
efisien ADJ
? PUN