確率的チューリング機械
 |
確率的チューリング機械（かくりつてきチューリングきかい、英: Probabilistic Turing machine）は、計算可能性理論において、各時点で何らかの確率分布に従って状態遷移をランダムに選択する非決定性チューリング機械の一種である。
各遷移の確率がいずれも等しければ、決定性チューリング機械にその文字セット（一般に '1' と '0'）についてそれぞれの文字を等確率で書く "write" 命令を持たせたものと定義できる。また、決定性チューリング機械に追加のテープとしてランダムなビット列が延々と書かれているものを追加したものと考えることもできる。
結果として、確率的チューリング機械は確率論的な結果を生み出す。同じ入力と命令状態であっても、実行するたびに結果が変わり、場合によっては停止しないこともある。つまり、確率的チューリング機械は、同じ入力であっても実行する毎にその入力を受理したりしなかったりする。
従って、確率的チューリング機械での文字列の受理/不受理は、通常とは異なった形で定義される。この定義の違いによって、様々な多項式時間の確率的な複雑性クラスが生じる。例えば、RP、Co-RP、BPP、ZPP などである。制約を多項式時間ではなく対数領域とした場合は、LP、Co-RL、BPL、ZPL がある。また、両方を制約を課した場合は、RLP、Co-RPL、BPLP、ZPLP がある。
確率的計算は対話型証明系の多くのクラスの定義においても重要である。この場合、検査機構（verifier）は全能の証明機構（prover）にだまされないためにランダム性を必要とする。例えば、IPクラスは PSPACE に等しいが、検査機構でのランダム性を排除すると NP と等しくなってしまう。PSPACE と NP の関係は正確には未だ確定していないが、おそらく NP の方が小さいと考えられている。
計算複雑性理論の課題の1つとして、「ランダム性は計算能力を向上させるか?」という問題がある。つまり、確率的チューリング機械で多項式時間で解ける問題があるとき、それが決定性チューリング機械では多項式時間で解けないと言えるだろうか? それとも、決定性チューリング機械で確率的チューリング機械をシミュレートして、高々多項式程度の低速化で問題を解けるだろうか? 現在、多くの研究者は後者（P = BPP）が正しいと考えている。多項式時間ではなく対数領域についての同様の問題（L = BPLP か?）は、さらに広く信じられている。一方、ランダム性によって対話型証明系の能力が与えられ、難しい問題を解く単純なアルゴリズムがランダム性の導入によって発見されているのも事実である。
本質的に確率的な計算のモデルとして、量子コンピュータがある。