確率的チューリングマシン

理論計算機科学において、確率的チューリングマシンは、ある確率分布に従って各ポイントで利用可能な遷移を選択する非決定的チューリングマシンです。結果として、確率的チューリングマシンは、決定的チューリングマシンとは異なり、確率的な結果を持つ可能性があります。つまり、特定の入力と命令の状態マシンでは、実行時間が異なったり、まったく停止しなかったりすることがあります。さらに、ある実行では入力を受け入れても、別の実行では同じ入力を拒否することもあります。

遷移の確率が等しい場合、確率的チューリング マシンは、書き込みの値がチューリング マシンのアルファベット内で均一に分布する (一般に、テープに「1」または「0」を書き込む確率が等しい)追加の「書き込み」命令を持つ決定的チューリング マシンとして定義できます。もう 1 つの一般的な表現は、単に「ランダム テープ」と呼ばれるランダム ビットで満たされたテープを追加した 決定的チューリング マシンです。

量子コンピュータ（または量子チューリングマシン）は、本質的に確率的な計算の別のモデルです。

確率的チューリングマシンは、非決定的チューリングマシンの一種で、各非決定的ステップは「コイントス」であり、つまり、各ステップで2つの可能な次の動きがあり、チューリングマシンは確率的にどの動きを取るかを選択します。^[1]

確率的チューリングマシンは、7組の組として正式に定義することができ、ここで ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})}$

• ${\displaystyle Q}$有限の状態集合である
• ${\displaystyle \Sigma }$入力アルファベットは
• ${\displaystyle \ガンマ}$テープアルファベットには空白記号#が含まれる。
• ${\displaystyle q_{0}\in Q}$初期状態
• ${\displaystyle A\subseteq Q}$受け入れ（最終）状態の集合である
• ${\displaystyle \delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$は最初の確率的遷移関数です。はチューリング マシンのテープ上で 1 セル左への移動であり、は 1 セル右への移動です。${\displaystyle L}$${\displaystyle R}$
• ${\displaystyle \delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$は2番目の確率遷移関数です。

各ステップで、チューリングマシンは遷移関数または遷移関数のいずれかを確率的に適用します。^[2]この選択は、以前のすべての選択とは独立して行われます。このように、計算の各ステップで遷移関数を選択するプロセスは、コイントスに似ています。 ${\displaystyle \delta _{1}}$${\displaystyle \delta _{2}}$

各ステップでの遷移関数の確率的選択により、チューリング マシンにエラーが発生します。つまり、チューリング マシンが受け入れるはずの文字列が拒否される場合もありますし、チューリング マシンが拒否するはずの文字列が受け入れられる場合もあります。これに対応するために、次の条件を満たす場合、言語は確率的チューリング マシンによってエラー確率で認識されると言われています。 ${\displaystyle L}$${\displaystyle \epsilon }$${\displaystyle M}$

1. 文字列は、${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon }$
2. 文字列が含まれない場合は、${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }$

確率的コイントスを利用することで生じるエラーの結果として、確率的チューリングマシンによる文字列の受け入れの概念は、さまざまな方法で定義できます。いくつかの重要な複雑性クラスを含むそのような概念の 1 つは、エラー確率 1/3 を許容することです。たとえば、複雑性クラスBPP は、エラー確率 1/3 で確率的チューリングマシンによって多項式時間で認識される言語のクラスとして定義されます。この受け入れの概念を使用して定義される別のクラスはBPLで、これはBPPと同じですが、言語は対数 空間で解決可能でなければならないという追加の制限が課されます。

受容の他の定義から生じる複雑性クラスには、 RP、co-RP、ZPPなどがあります。マシンが多項式時間ではなく対数空間に制限されている場合、類似のRL、co-RL、ZPL複雑性クラスが得られます。両方の制限を強制すると、RLP、co-RLP、BPLP、ZPLPが生成されます。

確率的計算は、インタラクティブ証明システムのほとんどのクラスの定義にも重要です。インタラクティブ証明システムでは、検証マシンは、万能の証明マシンによって予測されたり騙されたりしないようにランダム性に依存します。たとえば、クラスIP はPSPACEに等しいですが、検証マシンからランダム性を取り除くと、 NPだけが残ります。これは知られていませんが、かなり小さいクラスであると広く信じられています。

計算量理論の中心的な疑問の 1 つは、ランダム性がパワーを高めるかどうか、つまり、確率的チューリング マシンでは多項式時間で解けるが、決定的チューリング マシンでは解けない問題が存在するかどうかです。あるいは、決定的チューリング マシンは、最大でも多項式時間の遅延ですべての確率的チューリング マシンを効率的にシミュレートできますか。決定的チューリング マシンは確率的チューリング マシンの特殊なケースにすぎないため、P ⊆ BPPであることがわかっています。ただし、 BPP ⊆ P であるかどうかは不明です (ただし、広く疑われています)。つまり、BPP = Pです。多項式時間ではなく対数空間の場合の同じ疑問 ( L = BPLPか?) は、さらに広く真実であると信じられています。一方、対話型証明システムにランダム性が与えるパワー、および多項式時間の素数判定や対数空間グラフの連結性判定などの難しい問題に対してランダム性が作成する単純なアルゴリズムは、ランダム性がパワーを高める可能性があることを示唆しています。

• ランダム化アルゴリズム

• Arora, Sanjeev ; Barak, Boaz (2016)。計算複雑性：現代的アプローチ。ケンブリッジ大学出版局。pp. 123–142。ISBN 978-0-521-42426-4。
• シプサー、マイケル(2006)。計算理論入門(第 2 版)。米国: Thomson Course Technology。pp. 368–380。ISBN 978-0-534-95097-2。

• 確率的チューリングマシンに関する NIST の Web サイト