機率圖靈機

在計算複雜性理論內，機率圖靈機是一個非決定型圖靈機，在每個轉折點根據某種概率分佈隨機選擇某種可行的轉變(transition)。

在轉變是均勻分佈機率的例子裡面，我們可以定義為決定型圖靈機多了一個新增的"寫入"指令，這一個寫入指令的值是所有圖靈機能用符號的均勻分佈機率選擇出的符號 (概括地說，這個寫入指令以相同的機率在紙帶上面寫入'1'或者'0'。) 另一個常用的定義是多了一條隨機紙帶，上面佈滿了許多隨機位元值的確定型圖靈機。

所以，機率圖靈機可以有隨機的結果(與決定型圖靈機不同)；給定一個輸入和一個狀態機，機器運作的時間長度會不同，或者甚至不會停止；甚至，這機器可能在這一次操作下回傳為接受，下一次相同的輸入值卻回傳為拒絕。

因此如何去理解被一個機率圖靈機接受字串的方式可以用許多不同的方式定義。同時也有許多種因為我們對accept方式的不同，而產生了許多的多項式時間隨機複雜度類，包含了 RP，Co-RP，BPP and ZPP。如果我們把多項式時間的限制改成對數空間的限制，我們則有了跟上面雷同的RL，Co-RL，BPL，和ZPL。如果我們同時限制兩者，則有了RLP，Co-RLP，BPLP，和ZPLP。

隨機計算對於定義大多數的交互式證明系統也是極為重要的，因為驗證者機器需要隨機性來避免被全能的證明者預測或者欺騙。例如說，IP這個類別等同 PSPACE，但是如果把驗證者的隨機性移除，我們就只有NP，一個一般而言相信(但尚未證明)是比起IP要小的複雜度類。

複雜度理論的其中一個重點問題是：是否隨機性增加了演算法的能力？換句話說，是否有問題在多項式時間內可以以概率圖靈機解決但是不能以決定型圖靈機解決？或者是決定型圖靈機可以在至多只有多項式時間的變慢之下，完全的模仿隨機圖靈機的動作？現今的研究者大部分相信後者，這同時可以推出 P = BPP。相同問題的對數空間(log space)版本(是否L = BPLP?)則比起多項式時間版本更被廣泛相信為真。另外，隨機性給予交互式證明系統的力量，以及對困難問題所能建立更簡單的演算法的特質，例如多項式時間內的質數測試(primality testing)和對數空間的圖相連測試(graph connectedness testing)，又隱含著隨機性是有可能增加計算能力的。

量子計算機則是另一種先天就具有著機率性質的計算模式。