記事の内容

この記事では、計算理論の基本的な成果に触れたい。

それは、絶対に書くことができないプログラムの存在だ。

この事実は、現実的に重要である「完璧なバグ検出プログラム」の存在にも関係する。

具体例と証明の考え方をまとめたい。具体例にはPythonのコードを使用する。

決して書くことができないプログラム

かなり不自然な定義だが、以下のようなコードを考えよう。
「Pythonのコード」を入力として受け取るという関数だ。

def notYesOnSelf(P):
    if P(P) == 'yes':
        return 'no'
    else:
        return 'yes'

面白いところはここからだ。
この関数に自分自身を引数として与えたらどうなるのか？

そうすると矛盾が生じる。よって、この関数、つまり、notYesOnSelf()は存在しないことが導かれる。

なぜこのような奇妙な関数を考えたのか。
それは、notYesOnSelf()は存在しないことが分かると、以下に示すyesOnString(),yesOnSelf()も存在しないことが示せるからだ。入力であるPはPythonのコードを、Iは文字列を表す。

def yesOnString(P, I):
    if P(I) == 'yes':
        return 'yes'
    else:
        return 'no'

def yesOnSelf(P):
    if P(P) == 'yes':
        return 'yes'
    else:
        return 'no'

なぜならば、yesOnString(),yesOnSelf()が存在すると仮定すると、notYesOnString()を作れてしまう。背理法の考え方だ。

yesOnString()からyesOnSelf()を作る。

def yesOnSelf(progString):
    return yesOnString(progString, progString)

yesOnSelf()からnotYesOnString()を作る。notYesOnString()が作れてしまってはダメ。

def notYesOnString(progString):
    val = yesOnSelf(progString)
    if val == 'yes':
        return 'no'
    else:
        return 'yes'

存在しないことがわかったyesOnString()は重要な意味を持つ。

ことを意味するからだ。

これは、喉から手が出るほどほしい、「バグ検出」プログラムの存在につながる。しかし、次に説明するように、否定的な結果が証明されている。

def crashOnString(P,I):
    if P(I)が例外を投げるとき:
        return 'yes'
    else:
        return 'no'

このcrashOnString()が存在すると仮定すると、先ほどのnotYesOnSelf()を導く議論と同じように矛盾を起こすプログラムを構成できてしまう。よって、crashOnString()は存在しない。

※この例では、わかりやすいように、例外を投げるようなケースだけをバグとして扱っている。しかし、そのほかのすべてのバグを見つけることはできないことも証明できる。

任意のプログラムの完全なバグ検出ができないことは証明されている。しかし、特定のプログラムに対して、ある種類のバグの検出はさまざまなアプローチが研究されている。個別の工夫の価値はあるということだ。

計算理論の基本的な話なので、検索すればすぐに情報を集められると思う。

Pythonコードによる具体例は次の本を参考にした。おすすめ。
『計算できるもの、計算できないもの　実践的アプローチによる計算理論入門』