ちょっと前に、停止性問題を考えて遊んでいた。そのときはみろりHPが工事中で、記事が書けなかったんで遅ればせながら書く。

停止性問題ってなに

「あるプログラム X が停止するかどうかを判定するプログラムは作ることができるか?」っていう問題。

  • 停止するっていうのは正常終了のこと。
  • 停止しないっていうのは無限ループに入っちゃうこと。

答えは「できない」なんだけど、停止性問題というトピックの肝はその証明方法だ。

ぼくなりの証明

こんな感じで考える。

  • 判定対象のプログラムを X とする。(設問どおり)
  • X を判定するプログラムを A とする。
    • A が X を「どれどれ停止するかな?」と見ることを A(X) と表現する。
  • A というプログラムは以下の仕様をもっている。
    • X が停止するなら無限ループしてしまう。
    • X が無限ループするなら停止する。
    • ようは自分が読んだプログラムと逆の動きをするわけね。
X A(X)
停止する 無限ループする
無限ループする 停止する

A は A(X) 自体を見ることもできるから A(A(X)) という書き方もできるわけ。そうなると以下のようなことにもなる。

プログラム 結果
X ループ
A(X) 停止
A(A(X)) ループ
A(A(A(X))) 停止
A(A(A(A(X)))) ループ
以下無限に続く ...

A というプログラムの結果は A が読み込むプログラムの種類だけ存在する。そしてその種類をすべて挙げることは不可能だ。 すべて挙げることができないということは、「すべてのプログラムが停止するかどうかを判定するプログラムがあるか」の答えは「できない」になる。

ぼくは納得だ。

ネットでよくみる証明

前提は同じ。そして仮定( A(X) が停止すると仮定する)も同じ。

  • A はどんなプログラムでも停止するか判定できるプログラムであるとする。
  • A(X) は停止すると仮定。
  • X には A(X) 自身も含まれるから A(X) には A(A(X)) も含まれる。
  • A(X) は停止するので A(A(X)) も停止することになる。
  • A(X) は停止すると仮定したのに実際は A(A(X)) はループする。それは矛盾である。
  • 前提である「どんなプログラムでも停止するか判定できるプログラムはある」は間違っていることになる。

ネットでよくみる証明がぼくに伝わらない

A(X) は停止すると仮定。

「どんな X を与えても A(X) が停止する」ことはありえないからこの仮定は無意味だと思っちゃう。だって「停止する X」を与えたらループするじゃん。オメーちゃんと A の仕様読んだか?

まあでもきっと、そういう仮定をしていいのが代数学なんじゃないかなーと推測している。もうちょっと代数学に慣れていれば納得できたのかも。ただ今の時点ではそれだと納得できなかったんで、自分なりの方向で考えざるをえなかったってわけ。

あと友達に「X ってのはこの世に存在するすべてのプログラムだと思っていいんだよね?」と聞くと、「いやそんな風に考える必要はないんだけど……」みたいに首をひねられた。彼らにとっては「みどりん何言ってんだ?」という思いだっただろう、すまねえ、すまねえ……。

停止性問題がうまれた背景

このトピックが生まれた背景を併記しておこう。

それは20世紀前半のこと。数学は不完全であるということが、論理学の手法によって証明されたころのお話。「じゃあ代数学の手法でも証明できるかな?」と考えた人がいた。それがチューリングさんって人だ。数学が不完全であるという説を、いろんな方向からのアプローチによって強化してみようとしたわけだ。

チューリングさんが考えた方法は以下のようなもの。

  • どんな数学の問題でも解くことができるマシンがあるとする。
  • そのマシンが解けない問題を見つけだす。
  • 完璧なマシンが解けない問題ある = この世には解けない問題が存在する。
  • ということは数学は不完全である。

その「解けない問題」として取り上げられているのが停止性問題なんだ。

おしまい

とにかく図をかいて考える奴。

以下の記事からリンクされています