「我流でゲーデル解釈」について V

高校情報科教員が計算可能性と計算量の初歩を知らないことは、高校理科教員がエネルギー保存則を知らないことと同じくらいまずいことだと、個人的には思っています。でも、現実は、そうではないようです。ちなみに、私の勤務先で情報科の免許をとった学生が計算量の概念をもたないことはありえません。必須科目のカリキュラムに含まれていて、担当者はきっちりと教えていますので。

今回は、それに多少は関係あるネタです。

すなわち、正しい論法をアルゴリズム化して、前提となる正しいもの全てをデータベース化すれば、
　　◇　コンピュータで、そこから導ける正しい命題の一覧を作ることができる。
　　◇　ある命題をコンピュータに入力すれば、瞬時に真偽を判定してくれるプログラムを作ることができる。

これが完全性定理ではないことは前回までに述べました。それだけで致命的な誤りですが、それに加えて、別な大きな間違いがあります。一般に、

性質Pをもつものの一覧を作ることができる
与えられたものが性質Pをもつかを判定することができる

の二つは同値ではありません。一般に、1よりも2のほうが強い条件になります。つまり、1は成り立つが2は成り立たないことがあるということです。引用文は、この二つを混同してます。

なぜ、1から2がいえないのか、雑な議論をすると、こんな感じです。性質Pをもつものの一覧があったとします。あたえられたものxと一覧の各項目を先頭から順に比較していきます。たまたま、ものxが性質Pをみたしていれば、xは一覧のどこかに含まれていますので、いつかは一覧の項目としてみつかります。そうすると、xはPをみたすと判定できます。しかし、ものxが性質Pをみたさない場合は、この方法では、いつまでたっても判定できません。どんなにがんばって探しても、探し足りないだけだけである可能性が排除できないからです。第一万項目まで探してなかったとしても、第一万一項目にある可能性は排除できません。第一京項目まで探してなかったとしても、第一京一項目にある可能性は排除できません。第一無量大数項目まで探してみつらなくても、第一無量大数一項目にある可能性は排除できません。したがって、性質Pをもつものの一覧だけで判定することは不可能で、たとえば、性質Pをもたないものの一覧も併用しなくてはならないのです。

厳密な議論は、もちろん、「一覧を作るとは何か」を数学的に定義するところから始めなくてはなりません。それをきちんと理解するには、理学部情報科学科等でだいたい2年次か3年次で習う計算理論の教科書を読む必要があります。しかし、高校情報科教員のもつべき常識としては、ここに書いた程度の雑な議論でも十分に役に立つでしょう。そして、その程度の常識は、現場の教員には持っていていただきたいものです。