Perhitungan dari mesin Turing nondeterministic (NTM) dikenal sebagai pohon konfigurasi, yang berakar pada konfigurasi awal. Setiap transisi dalam program diwakili oleh tautan ayah-anak di pohon ini.
Pohon serupa juga dapat dibangun untuk memvisualisasikan perhitungan mesin probabilistik dan kuantum juga. (Perhatikan bahwa lebih baik untuk beberapa tujuan untuk tidak melihat grafik terkait untuk perhitungan kuantum sebagai pohon, karena dua node yang mewakili konfigurasi identik pada tingkat pohon yang sama dapat "membatalkan" satu sama lain, karena gangguan kuantum, tetapi ini tidak ada hubungannya dengan pertanyaan ini.)
Tentu saja, perhitungan deterministik tidak seperti itu; ada "cabang" tunggal dalam "pohon" yang sesuai untuk setiap menjalankan mesin deterministik.
Dalam ketiga kasus yang disebutkan di atas, apa yang terkadang membuat perhitungan ini "sulit" untuk komputer deterministik sebenarnya bukan karena ada percabangan yang terjadi, melainkan masalah seberapa banyak percabangan yang ada di pohon. Sebagai contoh, mesin Turing nondeterministik waktu polinomial yang dijamin untuk menghasilkan pohon perhitungan yang "lebar" (yaitu jumlah node di tingkat paling ramai) juga dibatasi di atas oleh fungsi polinomial ukuran input dapat disimulasikan oleh polinomial -Tentu deterministik TM. (Perhatikan bahwa kondisi "lebar polinomial" ini setara dengan membatasi NTM untuk membuat tebakan nondeterministik paling banyak secara logaritmik.) Hal yang sama berlaku ketika kita meletakkan batas lebar yang sama pada perhitungan probabilistik dan kuantum.
Saya tahu bahwa masalah ini telah diperiksa secara terperinci untuk perhitungan nondeterministik. Lihat, misalnya, survei " Limited Nondeterminism " oleh Goldsmith, Levy, dan Mundhenk. Pertanyaan saya adalah, apakah fenomena "percabangan terbatas" atau "lebar terbatas" ini telah dipelajari dalam kerangka kerja umum yang mencakup semua model nondeterministik, probabilistik, dan kuantum? Jika demikian, apa nama standar untuk itu? Setiap tautan ke sumber daya akan dihargai.