機率圖靈機 在計算複雜性理論內機率圖靈機probabilistic Turing machine是一個非決定型圖靈機在每個轉折點根據某種概率分佈隨機選擇某種可行的轉變transition 在轉變是均勻分佈機率的例子裡面我們可以定義為決定型圖靈機多了一個新增的寫入指令這一個寫入指令的值是所有圖靈機能用符號的均勻分佈機率選擇出的符號概括地說這個寫入指令以相同的機率在紙帶上面寫入或者另一個常用的定義是多了一條隨機紙帶上面佈滿了許多隨機位元值的確定型圖靈機 所以機率圖靈機可以有隨機的結果與決定型圖靈機不同給定一個輸入和一個狀態機機器運作的時間長度會不同或者甚至不會停止甚至這機器可能在這一次操作下回傳為接受下一次相同的輸入值卻回傳為拒絕 因此如何去理解被一個機率圖靈機接受字串的方式可以用許多不同的方式定義同時也有許多種因為我們對accept方式的不同而產生了許多的多項式時間隨機複雜度類包含了RPCoRPBPP和ZPP如果我們把多項式時間的限制改成對數空間的限制我們則有了跟上面雷同的RLCoRLBPL和ZPL如果我們同時限制兩者則有了RLPCoRLPBPLP和ZPLP 隨機計算對於定義大多數的交互式證明系統也是極為重要的因為驗證者機器需要隨機性來避免被全能的證明者預測或者欺騙例如說IP這個類別等同 PSPACE但是如果把驗證者的隨機性移除我們就只有NP一個一般而言相信但尚未證明是比起IP要小的複雜度類 複雜度理論的其中一個重點問題是是否隨機性增加了演算法的能力換句話說是否有問題在多項式時間內可以以概率圖靈機解決但是不能以決定型圖靈機解決或者是決定型圖靈機可以在至多只有多項式時間的變慢之下完全的模仿隨機圖靈機的動作現今的研究者大部分相信後者這同時可以推出P  BPP相同問題的對數空間log space版本是否L  BPLP則比起多項式時間版本更被廣泛相信為真另外隨機性給予交互式證明系統的力量以及對困難問題所能建立更簡單的演算法的特質例如多項式時間內的質數測試primality testing和對數空間的圖相連測試graph connectedness testing又隱含著隨機性是有可能增加計算能力的 量子計算機則是另一種先天就具有著機率性質的計算模式