在計算複雜性理論內，機率圖靈機是一個非決定型圖靈機，在每個轉折點根據某種概率分佈隨機 ... 量子計算機則是另一種先天就具有著機率性質的計算模式。

機率圖靈機維基百科，自由的百科全書跳至導覽跳至搜尋在計算複雜性理論內，機率圖靈機是一個非決定型圖靈機，在每個轉折點根據某種概率分布隨機選擇某種可行的轉變(transition)。

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

)另一個常用的定義是多了一條隨機紙帶，上面布滿了許多隨機位元值的確定型圖靈機。

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

因此如何去理解被一個機率圖靈機接受字串的方式可以用許多不同的方式定義。

同時也有許多種因為我們對accept方式的不同，而產生了許多的多項式時間隨機複雜度類，包含了RP，Co-RP，BPPandZPP。

如果我們把多項式時間的限制改成對數空間的限制，我們則有了跟上面雷同的RL，Co-RL，BPL，和ZPL。

如果我們同時限制兩者，則有了RLP，Co-RLP，BPLP，和ZPLP。

隨機計算對於定義大多數的交互式證明系統也是極為重要的，因為驗證者機器需要隨機性來避免被全能的證明者預測或者欺騙。

例如說，IP這個類別等同PSPACE，但是如果把驗證者的隨機性移除，我們就只有NP，一個一般而言相信(但尚未證明)是比起IP要小的複雜度類。

複雜度理論的其中一個重點問題是：是否隨機性增加了演算法的能力？換句話說，是否有問題在多項式時間內可以以概率圖靈機解決但是不能以決定型圖靈機解決？或者是決定型圖靈機可以在至多只有多項式時間的變慢之下，完全的模仿隨機圖靈機的動作？現今的研究者大部分相信後者，這同時可以推出P=BPP。

相同問題的對數空間(logspace)版本(是否L=BPLP?)則比起多項式時間版本更被廣泛相信為真。

另外，隨機性給予交互式證明系統的力量，以及對困難問題所能建立更簡單的演算法的特質，例如多項式時間內的質數測試(primalitytesting)和對數空間的圖相連測試(graphconnectednesstesting)，又隱含著隨機性是有可能增加計算能力的。

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

參見[編輯]隨機演算法外部連結[編輯]NISTwebsiteonprobabilisticTuringmachines閱論編重要的複雜度類（完整列表）易解複雜度類對數空間相關DLOGTIMEAC0（英語：AC0）ACC0（英語：ACC0）TC0（英語：TC0）L·FL·SL·NLNCSCPolyL多項式空間相關P（P-完全）FP（英語：FP(complexity)）ZPPRPBPPBQP（QMA（英語：QMA）PostBQP（英語：PostBQP）EQP（英語：EQP））懷疑難解複雜度類UPNP（NP完全NP困難反NP反NP完全（英語：co-NP-complete））FNP（英語：FNP(complexity)）（TFNP（英語：TFNP(complexity)））PHPP#P（#P-完全（英語：Sharp-P-complete））PSPACE（PSPACE完全（英語：PSPACE-complete））難解複雜度類EXPTIMENEXPTIMEEXPSPACEELEMENTARYPRRREALL複雜度類的譜系多項式譜系指數譜系Grzegorczyk譜系（英語：Grzegorczykhierarchy）算術譜系相關複雜度族DTIMENTIMEDSPACE（英語：DSPACE）NSPACE可能性核對證明（英語：Probabilisticallycheckableproof）交互式證明系統量子複雜性理論取自「https://zh.wikipedia.org/w/index.php?title=機率圖靈機&oldid=37952624」分類：計算機科學中未解決的問題計算模型概率複雜度理論圖靈機導覽選單個人工具沒有登入討論貢獻建立帳號登入命名空間條目討論臺灣正體不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體查看閱讀編輯檢視歷史更多搜尋導航首頁分類索引特色內容新聞動態近期變更隨機條目資