Probabilistic polynomial time Turing machine

定義

非決定的チューリングマシンの一つで, 左右の遷移がそれぞれ $\frac{1}{2}$ で決まる TM.

$$M=(Q,\Sigma ,\Gamma ,q_0,A,{\delta }_1,{\delta }_2)$$

状態の集合
入力アルファベット
テープアルファベット( $\Sigma \in \Gamma$ )
初期状態
受理状態の集合
遷移関数:

$${\delta }_1,{\delta }_2:Q\times \Gamma \to Q\times \Gamma \times L,R$$

確率的に遷移するので毎回受理したりしなかったりする.
因みに, 非決定性チューリングマシンで多項式時間で解ける(間違える確率は1/2より小さい)決定問題のクラスを PP という.

Probabilistic polynomial time Turing Machine(PPT)

定義: $(Q,\Sigma ,\Gamma ,\sigma ,\gamma ,q_0,q_{\mathrm{accept}},q_{reject})$
遷移関数 $Q\times \Gamma \to Q\times \Gamma \times \{L,R\}\to [0,1]$

決定的TMと変換可能.

参考文献

• 確率的チューリング機械 - Wikipedia