Apa yang berfungsi sebagai dasar dari mesin Turing probabilistik dan non-deterministik Mengingat pertanyaan sebelumnya, tulis konteks yang berisi jawabannya. Bisa 1 - 20 kalimat. Konteks:
Mesin Turing deterministik adalah mesin Turing yang paling dasar, yang menggunakan seperangkat aturan tetap untuk menentukan tindakan masa depannya. Mesin Turing probabilistik adalah mesin Turing deterministik dengan pasokan tambahan bit acak. Kemampuan untuk membuat keputusan probabilistik sering 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 dari non-determinisme, yang memungkinkan mesin Turing untuk memiliki beberapa kemungkinan tindakan masa depan dari keadaan tertentu. Salah satu cara untuk melihat non-determinisme adalah bahwa mesin Turing bercabang menjadi banyak kemungkinan jalur komputasi pada setiap langkah, dan jika memecahkan masalah di salah satu cabang ini, dikatakan telah memecahkan masalah. Jelas, model ini tidak dimaksudkan untuk menjadi model yang dapat direalisasikan secara fisik, itu hanya mesin abstrak yang menarik secara teoritis yang menimbulkan kelas kompleksitas yang sangat menarik. Untuk contoh, lihat algoritma non-deterministik.