概要
先日、無限alertが組み込まれたWebページへのリンクを掲示板に投稿したとして、とある女子中学生の方が兵庫県警に補導されました1。このことへの抗議を目的として、「みんなで逮捕されようプロジェクト」が登場しました。そのリポジトリに投稿された「停止性問題を解いてくれた日本の警察に感謝します」という趣旨の風刺issueが面白かったのでご紹介します。
停止性問題とは
停止性問題の概要
計算可能性理論における停止性問題とは、「あるチューリングマシンと入力が与えられたとき、その入力を与えられたチューリングマシンは停止するかどうかを判定せよ」という問題です。
まず、「プログラム $A$ にデータ $x$ を入力して実行すること」を $A(x)$ と書き、「$A(x)$ が $y$ を出力すること」を $y=A(x)$ と書くこととします。コンピュータ上では、プログラムもデータと同じ形式で符号化して表すことが出来ます。簡単に説明するために、プログラム $A$ を符号化して表現したものも $A$ と書けることとします。この時、2つのプログラム $A,B$ に対して、「プログラム $A$ にプログラム $B$ を入力して実行すること」を $A(B)$ と書くことが出来ます。
この場合、停止性問題は次のように言い換えることが出来ます。
「プログラム $A$ とデータ $x$ が与えられたとき、$A(x)$ が停止するかどうかを判定せよ」
停止性問題の決定不能性
「停止性問題の決定不能性定理」とは、「停止性問題を常に正しく解くプログラムは存在しない」という定理です。つまり、以下の性質を満たすプログラム $H$ は存在しないということです。
任意のプログラム $A$ と任意のデータ $x$ に対して、
- $A(x)$ の実行が停止するとき、$H(A,x)$ は ${\rm Yes}$ を出力する。
- $A(x)$ の実行が停止しないとき、$H(A,x)$は ${\rm No}$ を出力する。
$$
H(A,x) = \left\{ \begin{array}{ll}
{\rm {\rm Yes}} & (A(x)\ が停止する) \
{\rm No} & (A(x)\ が停止しない)
\end{array} \right.
$$
停止性問題の決定不能性は、1936年にアラン・チューリングによって証明されています。
停止問題の決定不能性の証明
$H$ が存在すると仮定して矛盾を導く、背理法を使った証明となります。
まず、以下の性質を満たすプログラム $M$ を定義します。
- $H(A, A)={\rm Yes}$ のとき、$M(A)$ は無限ループとなり停止しない。
- $H(A, A)={\rm No}$ のとき、$M(A)$ は $0$ を出力して停止する。
$M$ は、$H$ と無限ループを組み合わせて以下のように定義することが出来ます。
// JavaScript風の疑似コードで記述したプログラム M
function M(A) {
if (H(A, A) == Yes) {
while(true) {
// 無限ループ
}
} else {
return 0
}
}
// 念のため、プログラム H の定義も
function H(A, x) {
if (A(x) が停止する) {
return Yes
} else {
return No
}
}
この時、$M$ の入力に $M$ 自身を渡したとき、すなわち $M(M)$ が停止するかどうかを考えてみます。
まず、$M(M)$ が停止すると仮定します。上のコード例の3行目をみると、$M(M)$ が無限ループせずに停止したということは、$H(M, M) = {\rm No}$ だったはずです。しかし、$H$ の定義より、$H(M, M) = {\rm No}$ となるのは $M(M)$ が停止しない時のみなので、これは矛盾となります。
次に、$M(M)$ が停止しないと仮定します。上のコード例の3行目をみると、$M(M)$ が停止せず無限ループするということは、$H(M, M) = {\rm Yes}$ だったはずです。しかし、$H$ の定義より、$H(M, M) = {\rm Yes}$ となるのは $M(M)$ が停止する時のみなので、これも矛盾となります。
$H$が存在するなら $M$ は定義できるはずだがその $M$ の定義に矛盾が生じる、ということになるため $H$ は存在しないということが証明されました。
兵庫県警を使った解法
しかし、兵庫県警を使うことで、停止性問題を解くことが出来ます。以下はそのissueの私訳です。翻訳が正しいことは保証できないので、英語の読める方は原文を読んでください（その方が面白いと思います）。
私訳
TL;Dr: 日本の警察が停止性問題を解きました。
背景
定義：停止性問題とは、任意のチューリングマシンMと入力sが与えられたとき、M(s)が停止するかどうかを判定するものです。
言い換えると、停止性問題は、与えられたプログラムと入力について、プログラムが終了するか判定するものです。
1936年、アラン・チューリングは、そのような問題を解くプログラムを記述することはできないことを証明しました。しかし2019年となった今、日本の警察の力を借りることで、停止性問題をエレガントに解くことが可能となりました。
証明
チューリングマシンMと入力sが与えられるとき、以下の手順を考えます：
- チューリングマシン
MをJavaScriptで実装します。JavaScriptはチューリング完全であるため、簡単にできます。 - そのコード中の全ての文の後に、
alert('!');を追加します。 - JavaScriptコードをWebページに埋め込み、リンクを取得します。
- リンクを日本の掲示板と警察に投稿します。
- 家で座って待ちます。
- もし逮捕されたら
M(s)は停止せず、逮捕されなければ停止します。
もしM(s)が停止するなら、無限alertになるリンクを投稿していないのですから、日本の警察に逮捕されるわけがありません。反対に、もしM(s)が停止しないなら、日本の警察にガサ入れされ、M(s)が無限ループになることを知ることが出来ます。したがって、日本の警察によって停止性問題を解くことができます。
イェーイ！俺たちは不可能を可能にしたぜ！
※公訴時効が適用されます。
Wikipediaによると、日本の時効期間は最大30年です（一部誤解あり？後述）。そのため、結果を知るためには30年も家で座って待っている必要があります。しかし幸運なことに、私たちは複数の問題を同時に解くことが出来ます。
今この時、このような計算可能性理論のブレイクスルーを目の当たりにすることが出来て感激しています。日本の警察の素晴らしい業績をたたえ、次のチューリング賞を授与すべきだと思います。
補足
無限alertの罪状は刑法第168条の2「不正指令電磁的記録に関する罪」らしく、3年以下の懲役または50万円以下の罰金が科せられます2。この場合、時効期間は3年となる3ため、家で座って待つ時間は最大3年で済みます。
念のため
これはもちろんジョークであり、
「あんな些細なスクリプトを共有しただけで中学生を補導するんだったら、当然他の不正プログラム共有者も1人残らず逮捕するんだろうな？あと、不正プログラムかどうかの判定は常に正しくできるんだろうな？」
という主張に基づいた皮肉であると思われます。「無限ループするプログラムを共有した者を1人残らず逮捕し、そうでない者は1人も逮捕しない捜査機関」が存在するという前提での思考実験ということです。現実には、日本で起きた全ての犯罪を立件することはできないでしょうし、有限回数のalertでも回数が極端に多ければ同様の扱いを受けると思います。