量子コンピュータと量子通信 I 演習 3.6 解

Qiita で数式が書けると聞いて書いてみた。でもこの演習問題あんま数式出てこなかった。

演習3.6（確率的停止問題）

確率的 Turing 機械を演習 3.2 と同じ方法で番号付けし、確率的停止関数 $h_p(x)$ を次のように定義する。つまり入力 $x$ があると少なくとも確率 $1/2$ で機械 $x$ が停止するならば $h_p(x)$ は $1$, 入力 $x$ に対して確率 $1/2$ 以下で機械 $x$ が停止するならば $0$ に等しい。すべての $x$ に対して厳密に確率が $1/2$ 以上の正確さで、出力 $h_p(x)$ を与える確率的 Turing 機械は存在しないことを示せ。

解

そのような確率的 Turing 機械があるとしてこれを HALT_P(x) とする。これを使って、別の確率的 Turing 機械 TURING_P(x) を次のように定義する

01 TURING_P(x)
02   y = HALT_P(x)
03   r = RAND()
04   if y = 0 then
05     halt
06   else
07     loop forever
08   end if

ここで、各行の頭の数字は行番号である。 この確率的 Turing 機械に対応する番号を $t$ とし、$h_p(t)$ を考える。

• $h_p(t) = 1$ と仮定する。
  • つまり、機械 t（TURING_P(x)）は入力 t に対して少なくとも 確率 $1/2$ で停止する。
  • 確率的 Turing 機械 HALT_P(x) は、確率 $1/2$ 以上の正確さで 出力 $h_p(x)$ を与える。
  • 今、仮に 確率 $p \ge 1/2$ で HALT_P(t) = 1 とする。
  • 従って、第 04 行の if 文は、確率 $(1-p) \le 1/2$ で then 句へ行き、動作を停止する。
  • つまり、この TURING_P(x) に自身の番号である $t$ を渡すと、$1/2$ 以下の確率で動作を停止する。
  • これは、はじめの仮定 $h_p(t) = 1 $ に矛盾する。
• $h_p(t) = 0$ と仮定する。
  • 同様の推論により、TURING_P(x) は確率 $p \ge 1/2$ で動作を停止することになり、やはり矛盾する。
• 以上により、すべての $x$ に対して厳密に確率が 1/2 以上の正確さで、出力 $h_p(x)$ を与える確率的 Turing 機械は存在しない