総集編 No.6

鼎談の表紙へ， 鼎談のあらすじへ， キーフレーズから見た鼎談へ，

６．１．作図の例をもっと詳しくみてみると

たとえば， 世の中には，どんなものでも数式で書けると思い込んでいる人がいます． でも，それは幻想ですよね． そういう幻想を抱いている人は， 数式で書けてこそ，数学の定理だと思い込んでいたりもします．

それに， 仮に数式で書き下せるにしても， 本当に数式で書くことに意味があるのかと問いたくなるような公式もありますよ．

その意味では， 数式（渡辺さんが以前いっていた数式とは意味が違います）で書き下すよりも， 操作とかアルゴリズムとかいったもので表現したほうが本当が見えてくる現象や構造がある． そういう現象や構造を対象とする研究が， コンピュータ・サイエンスから生まれる基礎科学なのではないでしょうか？

私も「17 回コンパスを使う」話を引き合いに出すのは，よいと思いますよ．

でも，どうして計算とか操作とかに，注目しなければならないのか． そこを押さえておかないと思うわけです． 「コンパス」の話はそういう観点の必要性を踏まえた上で， 論じた方がよいのではないでしょうか？ それをしないと，作図の問題が単なる組合せの問題になってしまう気がするのですが．

もっとも， 手順の多さや，場合分けの複雑さとか， そういう計算の困難さに注目して議論をするのなら， 私の言い分は後回しにしてもいいですよ．

はい！そうしましょう．

根上さんの話を聞いていると， 何となく「困難性」の議論ではなく，「不可能性」の議論に持っていきたいような雰囲気がしますね． でも，コンピュータ・サイエンスの真の特色は， 不可能性の議論から困難性の議論に移ってきたところから出てきたように思うのです． つまり，ゲーデルやチューリングを卒業したところで， コンピュータ・サイエンスの特徴が出てきているように思うのです．

ただ，だからと言って，計算困難性の話だけが， コンピュータ・サイエンスと言っているわけではありません． あくまで，これはコンピュータ・サイエンスの一分野に過ぎません． たまたま私自身がこのテーマにたずさわってきたために， それを例としているだけです．

ここで少し話しを整理してみますね．

コンピュータ・サイエンス（ＣＳ）って何なの？という話から始った． その問いに対する究極の答えとして，「計算」を対象とした学問がＣＳである，を渡辺が提唱した． ここで，「計算」はそんなに単純なものではない． むしろ，おそろしく難しい対象だ，ということを説明したくて， 渡辺が例として計算困難性の証明の難しさの議論を持ち出した． さらに，なぜ計算困難性の証明が難しいのか？の直観的な説明を理解を得てもらおうとして， 構造の有無の話になっていった．

混乱を避けるために，もう１つ整理をしてください． 「困難性」といったとき， 計算自体が困難なのか，その計算困難性の証明が困難だというのかのどちらを意味していますか？

「困難」とは，計算の手間がかかるという意味です． 一方，証明が困難な場合には，「難しい」という言葉を使ってきたと思います．

それと，渡辺さんが引き合いに出している正多角形の作図の問題のことをもう少し説明してください． ただ「困難だ」の一言でかたずけてしまうのは，まずいです． いったいどういう困難さなのかを問うことに意味があるのではないですか．

単に数学的な発想だけで捉えてしまうと， コンパスを n 回使って作図できる点全体の中に， 360度の m 分の 1 の位置を与える点が含まれるかどうかという問題を考えているように思えます． となると，n と m の値が変わっても問題の質は同じなのではないでしょうか？

コンピュータ・サイエンティストが見ると， こういうふうに困難さが違ってみえるんだよ，という説明がほしいですね． それがわかってくると， すべてを数学の中に取り込んでしまおうといる私の野望が打ち砕かれることになります．

すみません．作図の話はあくまで比喩です． 根上さんが指摘されたように，証明の難しさを示す例としては，不向きかもしれませんでした． でも折角持ち出したのだから，それを例に話を続けましょう．

ここで作図の話が計算の困難さにどう対応するかを整理しておきます． 計算の困難さにおける「手間」とは， たとえば， 作図でコンパスを何回，定規を何回使うか，ということに対応します． つまり，使うことのできる基本演算を何回使うか， ということが「手間」になります． また，作図の「やり方」がアルゴリズムです． 同じ角の二等分でも，いろいろな方法（アルゴリズム）がありますよね．

さて，作図問題の「困難さ」を，最適な「やり方」の元での「手間」としましょう． つまり，最低限どの程度の手間が必要なのかを議論するのが，困難さの議論です． その場合，すべての操作の数を考えることもありますが， たとえば，コンパスを使う回数だけに注目して「手間」を評価することもあります． 「正 n 角形を作図する問題におけるコンパスの使用回数」とは， そういった困難さの議論の一例なわけです．

さて，正 n 角形を作図する際に最低限必要なコンパスの使用回数を議論するにあたり， 二つのことを十分に理解する必要があります．

• 目標に対する理解： たとえば，正 12 角形の作図の場合， 「正 12 角形を作るとはどんなことか？」ということに対する理解です．
• 手法に対する理解： m 回しかコンパスを使わないということはどういうことか？ということに対する理解です．

実際，作図の不可能性が証明されたのは， 「コンパスと定規だけで作図するとはどういうことか？」に対する きれいな特徴付けが得られたからです． 同様に， 「m 回しかコンパスを使わないで作図できること」 に対するうまい特徴付けがあるかもしれません． そうすると「困難性」の議論は非常にやりやすくなります．

しかし，もしも，仮にもしも 「17 回しかコンパスを使わないでできること」と 「18 回しかコンパスを使わないでできること」の特徴付けが， まったく異なっていたらどうでしょう． つまり，「m 回しかコンパスを使わないでできること」の特徴が， m ごとにまったく違っていて， 同じような枠組みでは議論できなかったらどうでしょう． 「困難性」の議論は一気に難しくなるはずです．

ここではそう仮定してみましょう， といった比喩を持ち出したということなのです．

６．２．「困難性」は単なる手数の多少だけを問題なのか？

困難性が手数に比例したようなものだということはわかりました． でも本当に， 単に手数が多いとか少ないとかだけを問題しているのですか？

計算の困難性というのは， 「この計算は 10 手でできるけれど， こっちの計算は 100 手かかるので，こっちの方が難しい」 というような単純なことではないですようね． 少なくとも， コンピュータ・サイエンスのことを知らない人は， 計算の手数とか手間というと， 値の単純比較以上の観点しか持っていないと思います．

それだと， コンピュータ・サイエンスって， なんだかつまらないことを研究しているんだなあと思う人がいても不思議ではありませんよ．

そんなふうに思われてしまったら， 諸科学の根底を支える基礎科学としては意味がないですよね．

「確かに，難しいことは，難しいんだけれど，実は，こういうわけで難しかったんだよ」， 「なるほどね」という会話になれば，いいのですが．

つまり， 計算の困難性を， 単なる手数の問題にとどめないで， 計算の質とか構造とかの違いから見えてくるものと捉えられないのでしょうか？ きっと，そういう計算の質とか構造という観点の提供やその解析方法の提供が， 基礎科学としてのコンピュータ・サイエンスに期待されていると，私は思います．

さて，話を肝心なところに移しましょう．根上さんは

困難性とは 10 手でできる，100 手かかる，の違いのような単純なことではないですよね．

と言われましたが， まさに，その通り単純なことなのです！ たかが手数の評価で何が重要なのか？と思われるかもしれません． 深遠で崇高な基礎理論の仲間に入れる価値があるのか？と．

でも，昔の議論 [0002-0004] を思い出してください． 計算の真の価値を示すことの重要性については皆さん口にされましたよね． それを突き詰めていくと，真の価値を示すには，手数の評価が重要になるのです．

うっかり寝過ごしてしまいました．すいません．

根上さんの発言には私もショックです． 私も「たかが手数の評価が非常に重要なのだ」と思っています． 根上さん曰く 「手数の議論なんて， なんだかつまらないことを研究しているんだなぁ」と思う人は， そんなに沢山存在するのでしょうか？

いや，そうかもしれない． 「そう思う人」が存在する理由のひとつが， 「手数が多いとか，少ないとかの問題」が難しくないものに見えるからなのでしょうね．

渡辺さんの主張しているのは， 「手数が多いとか，少ないとかの問題」は難しい，ということですよね． たとえば， 「手数が少なくできない」（すなわち「計算が困難である」） という事を示すのは， 作図の例でもわかるように，難しい事でなのですね．

たとえば， テクノロジーが進歩して，今よりも 10 倍早いコンピュータが登場してしまえば， 10 手と 100 手の差なんて意味がないでしょう． コンピュータ・サイエンスでは， そういうテクノロジーの進歩によって吸収もしくは消滅してしてしまう研究しかしないのだとすると， そういうのって基礎科学なのでしょうか？（私がそう思っているわけではないですよ．）

計算量のオーダーやらの概念を知らない人（数セミの読者には多いのでは） とかがここまでの議論を見ていると，そういう誤解をしかねないと思うのですが．

渡辺さんの発言の字面だけを追うと証明の難しさに関して， 「特徴づけに差がある」と述べているだけで， その差とは何ナノかがわかりません． 文脈からだけだと， やっぱり「手数に差がある」という以上の意味が出てこないような気がするのですが．

もう少し深く私の疑問に答えてほしいのだけれどな．

==> １０月の鼎談へと続く

鼎談の表紙へ， 鼎談のあらすじへ， キーフレーズから見た鼎談へ，