数学 · 18 / 25
閉じた体系は買える
完全であること、決定可能であること、使えることは、同じ保証ではない。プレスバーガーから数学の機械化まで、境界と代価はそれぞれ別の帳簿に記される。
一 二つの偶数
1954年の夏、プリンストン高等研究所。そこには真空管式の計算機が一台あった。世界で最初期に造られた計算機の一つだ。記憶容量は全部で1,024ワード。プログラムそのものも、処理する式も、計算の途中で生まれるものも、何もかもをその中に押し込まなければならなかった。
この計算機のために、26歳の論理学者がプログラムを書いた。名はマーティン・デイヴィス。
当時の計算機は、ほとんどが数の計算をしていた。このプログラムが扱うのは、数ではなく文だった。整数について述べた文を一つ渡すと、あらかじめ決められた手順を一歩ずつたどっていく。その土台にある判定アルゴリズムは、記憶容量に制限のない理想的な機械なら、必ずいつか停止して正しい答えを返す。だが現物の機械では、その前にメモリが尽きかねなかった。「人工知能」という言葉は、まだ生まれていない。
このプログラムが挙げた最大の手柄は、二つの偶数を足すとやはり偶数になると証明したことだった。ずっと後になって、デイヴィス自身がそう書いている。
自嘲ではある。けれど、少しも誇張ではない。部屋を一つ占めるほどの機械が、いちばんうまくやったときに証明できたのは、小学生でも知っていることだった。
そこで二つの疑問が浮かぶ。数学の中で、なぜこの小さな領域だけは、安心して機械に判定を任せられるのか。機械が真だと言えば、なぜ必ず真なのか。そして、判定できるのなら、なぜ最高の成果がたったこれだけなのか。後の問いには、この機械そのものがまもなく答えを出す。あの自嘲より、はるかに重い答えを。先の問いの答えは、25年前のワルシャワにある。
1929年9月24日、火曜日、午前10時半。ワルシャワで開かれた第1回スラヴ諸国数学者会議は、二日目を迎えていた。第1分科会の最初の発表枠を割り当てられたのは、修士号もまだ持たない学生だった。ワルシャワ大学で数学を学ぶプレスバーガー、24歳。
その会議の様子を、少し眺めておきたい。開会にあたってフレンケルはカントールを論じ、タルスキは自ら二度講演した。参加者の大半はポーランド人だったが、日本から来た人もいれば、アメリカのテキサスから来た人もいた。論文集にはヨーロッパの五つの言語が認められ、特に多かったのはドイツ語とフランス語だった。会議が終わると、参加者の一部は寝台列車でポズナンへ移動した。そこではクラトフスキが、引き続き位相幾何学を講じた。
プレスバーガーの発表は、のちに論文集に収められた。本文は10ページ、それにページ番号のない補遺が1ページ。題名を日本語にすれば、「加法を唯一の演算とする整数算術の一体系の完全性について」。冒頭には目立たない脚注がある。結果を得たのは1928年5月、問題を出したのはタルスキだ、と。
この問題には背景がある。当時、ヒルベルトとその周辺は途方もなく大きな問いを追っていた。与えられた一階論理の式が普遍妥当かどうかを、一律に判定する機械的な方法はあるか。「決定問題」と呼ばれる問いである。まだ計算機はない。機械的な方法とは、紙の上に書かれた手順のことだった。数学がまるでわからない人でも、ただ手順に従えば正しい答えに着く。それほどまでに隙なく決められた手順だ。ヒルベルトたちが求めていたのは、数学全体を扱える、そういう方法だった。
タルスキは、その大きな問いからごく小さな一角を切り出して、学生に渡した。プレスバーガーの返事はこうだった。この一角になら、ある。整数算術の小さな領域があって、そこで言える文はどれも真偽を決められる。しかも方法は一つでよい。どの文を渡しても、有限回の手順を経て答えが出る。25年後、デイヴィスが真空管に組み込んだのは、まさにこの方法だった。機械は、実物を造れるようになるより先に、紙の上で出来上がっていた。
ここまでの数回で見てきたのは、ほとんど逆の話ばかりだった。集合論から矛盾が生まれ、基礎をめぐる争いは20年続いた。公理をプログラムで列挙できる算術は、十分に強ければ、無矛盾でありながら完全であることはできない、と告げる定理もあった。それなのにここでは、一人の学生が、人で埋まった教室で、そうしたことのまったく起こらない算術を10ページで示している。結果が出たのは1928年、会議での発表は1929年。あの定理が公刊された1931年より、それぞれ3年、2年も早い。
だから問うべきは、算術をどこまで弱くすれば、完全性と、何でも一律に判定する機械の両方が手に入るのか、ということだ。答えは「掛け算を取り去る」よりずっと込み入っていて、ずっと面白い。
二 言葉にできないこと
3円玉と5円玉しかないとして、ある金額をちょうど作れるだろうか。11円なら作れる。7円は作れない。では、金額があるところを超えたら、作れない額はもうなくなるのか。答えは、8円から先なら、どの額も作れる。
このどの問いも、プレスバーガーの言語で表せる。そして、どれにも判定を下せる。
彼が考えたのは、演算として加法だけを持つ整数の算術だった。その言語には足し算の記号があり、0と1があり、等号と大小関係があり、「存在する」「すべての」といった言葉がある。ある数の3倍も、もちろん表せる。同じ数を三つ足せばよいからだ。公理を列挙する際、彼はすでに断っていた。乗法記号はないのだから、そのような表記は、決まった回数だけ加法を繰り返す意味に読まなければならない。いくつかの数を足すと別の数になる。ある数が別の数よりいくつ大きい。7で割ると3余る。いくつもの整数が、こうした条件を同時に満たす。どれも表現でき、どれも判定できる。何かを壊した残骸ではない。小さいながら、一つの世界として欠けるところがない。
ないのは、二つの変数を掛け合わせることだ。だから、この言語ではそもそも言えないことがある。ある数が、別の二つの数の積であるという関係。ある数が平方数であること。素数であること。そして、一方の数が他方を割り切るという関係。ただし、その二つの数はどちらも変数だ。
「言えない」とは、重い言葉である。証明が難しい、という話ではない。それを一律に言い表す文そのものが、この言語には存在しないのだ。ここで定義できる数の集合には、整った形がある。十分先まで進むと、同じ並びが周期的に繰り返される。平方数も素数も、そんな並び方をしない。だからこの世界には、それらを指す名前さえない。「この数は素数か」。数論の最も古い問いの一つが、プレスバーガーの世界では問いにすらならない。
失われたのは表現する力であって、証明する力ではない。その二つは別物だ。
ここには三つの言葉がある。この先、それぞれ別の道を歩むことになる。まず「完全」とは、その言語で述べられるどの文についても、理論が肯定か否定かの決着をつけられることをいう。第17回で見たような、証明もできず、否定も証明できない文は残らない。「決定可能」は、別のことをいう。その言語の文をどれでも渡せる、統一された機械的な方法があり、有限回の手順の後には必ず停止して、正しい答えを返すということだ。
二つの間には、短い橋が架かっている。理論が完全で、その公理を一つずつ機械的に列挙できるとしよう。ならば証明も、一つずつ列挙できる。文を一つ受け取ったら、証明を順に並べていき、その文とその否定のどちらが先に現れるかを見る。理論は完全なのだから、どちらかは必ず現れ、この手続きは必ず止まる。プレスバーガーも原論文の冒頭で、このことを明記していた。完全性の証明が実効的な手続きになっているため、それは同時に、文の真偽を判定する方法にもなる。一つの証明が、機械を一台おまけに連れてくる。
「完全」には、もう一つ注意がいる。理論が何でも知っている、という意味ではない。この言語で言えることなら、すべて決着がつく、という意味だ。言えないことは、問うことさえできない。だから、語れることが少ない体系ほど、完全になりやすい。褒め言葉のように聞こえるが、これは請求書の最初の一行である。
三つ目は「実行可能」だ。方法が存在することと、その方法が人間に許された時間、メモリ、機械で本当に動くことは違う。初めの二つは論理的な性質をいい、三つ目はさらに計算量と現実の資源を問う。1,024ワードの機械が、ほどなくその違いを目の前に突きつける。
三 一語を消す
あの機械の中核をなす方法を、量化子消去という。プレスバーガー算術では通常、まず言語を広げて、固定された数を法とする合同関係や、固定された数による可除性を表す述語を加える。その同値な拡張のもとで、量化子を消去する。
文には、「ある数が存在する」「すべての数について」といった言葉が含まれることがある。量化子消去は、その数がどれなのかを当てにいく作業ではない。文全体を、まったく同じ意味を持ちながら、その数にはもう言及しない文に置き換える作業だ。
ごく小さな例を挙げよう。ある数が与えられたとき、自分自身を足すとその数になる整数は存在するか。この文には「整数は存在するか」という部分がある。それを消すと、残る条件は与えられた数だけに関わるものになる。その条件とは、その数が偶数であることだ。
これだけのことだ。「自分自身を足すとその数になる整数が存在する」が、「その数は偶数である」に置き換わる。後の文には、探していた整数はもう登場しない。しかも、その場で確かめられる。プレスバーガーの論文にも、こうした小さな例がある。「存在する」を含む加法の方程式が、余りと、それ以外の数だけについての条件に書き換えられる。デイヴィスの機械が挙げた最大の手柄も、偶数についてのものだった。真空管の中で進んでいたのは、まさにこのような一段ずつの置き換えだった。
別の世界からも例を取ろう。自分自身を掛けると、与えられた数になる実数は存在するか。消去して残る条件は、与えられた数が0以上であることだ。探していた数は消え、与えられた数だけについての文が残る。
これを繰り返せば、自由変数を一つも持たない文は、最後には真偽を直接確かめられる条件になる。判定はこうして実現する。タルスキの突破口は、この考えを、実数の多項式による等式と不等式の世界にまで押し進めたところにあった。そこには加法も乗法も、大小関係も量化子もある。それでも量化子を消せる。
この一歩で、もう一つの学問が一緒に入ってきた。幾何学だ。タルスキのいう初等幾何学とは、座標を導入すれば実数の代数式へ翻訳できる問題を指す。直交座標系を一つ定め、点を実数の座標で表す。距離、一直線上にあること、垂直、円といった関係は、有限個の多項式の等式や不等式で表せる。そこで対応する幾何学の命題も、この機械の守備範囲に入る。任意の点集合や任意の関数についての一般的な命題まで入るわけではない。範囲を決めるのは、選んだ言語であって、「幾何学」という学問の看板ではない。
考えてみれば、こんなことができる必然性はない。「存在する」と言うとき、無限の範囲を探しているように見える。だが機械は、無限個の数を一つずつ探してはいられない。見つからなければ、永遠に止まれないからだ。量化子を消せるということは、終わらないかもしれない探索を、有限の、直接確かめられる文に置き換えられるということだ。なぜこの小さな領域を機械に任せられるのか。その答えの半分はここにある。この中の「存在する」は、どれも消せる。置き換えが利くかどうかは、その世界の形がどれほど整っているかにかかっている。整っているところでは消せる。整っていないところでは消せない。
得られるのは答えであって、理解ではない。書き換えた結果は途方もなく大きくなるかもしれず、人間が美しいと思う証明の姿をしているとも限らない。それでも、この方法には真偽を答える以上に大きな使い道がある。「存在する」や「すべての」を含む記述が、その世界の中で、結局どのようなものの集まりを定めているのかを教えてくれるのだ。後のモデル理論が量化子消去に見いだした最も重要な価値は、まさにこの構造についての情報だった。
四 境界はどこにあるか
乗法を取り去る代わりに、機械が手に入る。ならば、その先を聞きたくなる。境界は掛け算の記号のところにあるのか。
そうではない。二つの例が、違う方向からその見立てを覆す。一つはスコーレム算術。自然数で乗法だけを残し、加法を取り去っても、やはり決定可能なのだ。もう一つは、さらに強い例になる。タルスキの実数である。加法も乗法もそろい、大小関係まであるのに、この理論も決定可能だ。
足し算だけの側は扱いやすい。掛け算だけの側も扱いやすい。二つが整数の上で一緒になったとき、初めて質が変わる。
理由は記号の一覧にはない。整数の加法と乗法を合わせると、きわめて豊かな符号化ができる。有限の列も、証明も、一歩ずつ進む計算も、すべて整数どうしの関係として書き直せる。第17回で見た符号化に必要だったのは、まさにこの力だ。プレスバーガー算術には、その仕事は引き受けられない。二つの変数の積さえ定義できないからである。第17回の三条件のうち、この算術が届かないのは三つ目だ。無矛盾であることも、実効的に公理化できることも満たしている。だが、表現力が必要な強さに達していない。
タルスキ自身、本の中ではっきり対比させている。通常の整数の加法と乗法の算術に属する文をすべて含められるほど強い理論には、このような一律の判定法は存在しない。
彼はさらに、見事な境界の実験もしていた。あの実数の言語では、「この数は整数である」という性質を一律に定義できない。ところが、変数の動く範囲を直接整数に制限してよいことにすると、たとえば「ある数の3乗と別の数の3乗を足すと、第三の数の3乗になる、という式には整数解があるか」といった問いが入ってくる。整数算術が忍び込み、一律の判定はもう守れなくなる。同じ式でも、変数の範囲を実数から整数へ移しただけで、論理上の運命がすっかり変わってしまう。
難しさと易しさを分けるのは、記号ではない。変数をどこで動かすかだ。
敷居の向こう側がどんな場所なのかは、後に決定的に確かめられる。その立役者の中に、見覚えのある顔がある。ヒルベルトが1900年に示した問題一覧の第10問は、整数係数の多項式方程式を任意に与えたとき、整数解を持つかどうかを判定せよ、というものだった。変数どうしを掛け合わせ、整数の上で考える。まさにその種の問題だ。大学院生の頃から、マーティン・デイヴィスはこの問題を生涯手放さなかった。1954年の夏、プリンストンで敷居のこちら側の機械を真空管に組み込んだとき、彼はすでに何年も、向こう側を探っていた。
向こう側への道は、デイヴィスとパトナム、ジュリア・ロビンソンが十数年かけて切り開き、最後の一片をマティヤセヴィッチが埋めた。本人はその日をはっきり覚えている。1970年1月29日、レニングラードで初めて解答を公開講演した。聴衆の中にはツェイティンがいた。答えは、一般的な方法は存在しない、だった。同じ人が、片足を敷居のこちらに置いて機械を造り、もう片方を向こうに置いて、機械は造れないという証明を支えたのだ。
だから境界は、一本のきれいな線ではない。1936年、チャーチとチューリングは、一般の一階論理に統一的な判定法が存在しないことを証明した。数学全体を覆いたいというヒルベルトの願いは、ここで潰える。それでも境界の手前には、まるで違う方角から来たものたちが住んでいる。線形の算術、実数の代数、代数閉体、さらに後にはオートマトンにつながる数々の構造。決定可能である理由も同じではない。順序によるもの、代数的な閉性によるもの、オートマトンによるもの、量化子消去によるものがある。1950年にはトラフテンブロートが、有限構造だけに限っても一般的な決定問題は解けないと証明した。こうして論理学の歴史に残ったのは、決定可能から決定不能へと引かれた直線ではなく、地図だった。一方では決定可能な領域をどこまで大きくできるかを探し、他方ではどれほど小さな拡張で決定不能になるかを探している。
五 ワルシャワと、世に出なかった本
プレスバーガーは、遠い辺境でたまたま一本の論文を書いた学生ではない。当時のワルシャワは、ヨーロッパでも論理学者が最も集まる場所の一つだった。より広い流れを指す名が、ルヴフ＝ワルシャワ学派である。基礎を築いたのはトファルドフスキ。両大戦間期には、アイドゥキェヴィチ、コタルビンスキ、レシニェフスキ、ウカシェヴィチ、タルスキがいた。学派の盛期は、二つの世界大戦にはさまれた21年間にぴたりと重なる。ポーランドの独立回復から開戦までの間に、論理学がしだいにその最も目立つ分野となった。ワルシャワの論理学者たちに視野を絞れば、中心にはウカシェヴィチ、レシニェフスキ、タルスキがいて、その周りにリンデンバウム、プレスバーガー、そして大勢の学生がいた。
プレスバーガーは、この輪の中で実際の仕事を担っていた。ウカシェヴィチの数理論理学講義を講義録にまとめたのも、口頭の授業を聞いていた彼である。
出版の網も密だった。ポーランドの数学界には『数学の基礎』という専門誌があり、ルヴフとクラクフにも別の二誌があった。しかも、ワルシャワとウィーンは互いに孤立した島ではない。タルスキは1930年にウィーンを訪ね、同じ年にはカルナップがワルシャワへ来た。タルスキは1935年にも、もう一度ウィーンに行っている。第15回、第17回に登場したウィーンの人々と、ここに出てくるワルシャワの人々は、あの時代、同じ網の中にいた。
だが、後世の論文データベースを見ても、タルスキ本人の置かれた境遇はすっぽり抜け落ちてしまう。生まれたときの姓はタイテルバウム。1923年、兄弟とともにタルスキに改姓し、カトリックへ改宗した。本人には信仰はなかった。理由は一つではない。ポーランド人でありたいという思いがあったし、当時のポーランドでは、ユダヤ人が大学の職に就くのは難しいと知ってもいた。1924年にワルシャワで博士号を取得した後も、長く中等学校で数学を教え、ワルシャワ大学で得ていたのは、ささやかな教職だけだった。1939年にはルヴフの教授職に応募したが、かなわなかった。あの時代の世界水準の論理学の成果が、中等学校でも教えていた一人の人間から生まれていた。
実数代数の判定法を見つけたのは、1930年だった。本の末尾にある歴史的注記は、そこからさらにさかのぼる。一部の結果は、1926年から1928年にかけての授業に、すでに登場していたという。あの頃ワルシャワの教室に座っていた学生たちは、その一端を耳にしていた。教室の外の人々が読めるようになるまでには、さらに20年がかかった。
そして、この本自身の旅が始まる。当初は1939年にパリの出版社から刊行されるはずだった。戦争がそれを断ち切った。拾い上げたのは、アメリカの研究機関である。1948年、アメリカ空軍のRAND計画が決定問題に関心を持ち、9年間眠っていた原稿が掘り起こされた。マッキンゼーが整理と改訂に加わり、RANDの番号付き報告書として印刷された。1951年5月には改訂版が出て、後には通常、1951年の刊行物として引用されるようになる。最初のRAND版が出てから7、8年後、同じ研究機関の計算機で、別の種類の定理証明プログラムが走り出す。
タルスキが方法を見つけてから、本が国際的に流通する形で世に出るまで、18年が過ぎた。1939年以後に止まった理由は、はっきりしている。戦争だ。けれども1930年から1939年までの9年間、なぜ刊行されなかったのかについては、今も説明が見当たらない。
このくだりに出てくる年は、どれも確かめられる。一つだけ、確かめられない年がある。
プレスバーガーは1904年12月27日にワルシャワで生まれ、1923年に中等学校を卒業して、ワルシャワ大学へ進んだ。彼自身を主題にした研究は、1991年にジグムントが書いた伝記一本しかない。主な根拠は、ワルシャワ大学に残された学生記録だった。その資料は後に高解像度でスキャンされ、整理、公開された。入学登録の用紙、履修科目、卒業関係の書類。1930年10月に数学の修士号を得たことは、今でも一枚ずつページをめくって確かめられる。
その先で、記録が途切れる。彼はポーランドのユダヤ人で、ナチスのホロコーストによって命を奪われた。通常は1943年頃と推定されている。専門の伝記でも、その年の後ろには疑問符が付く。正確な日付、場所、そして最後に何があったかは、学生時代の資料ほど確かなことがわからない。
ある人が20代で書いた10ページを、機械は代を重ねながら70年以上も実行してきた。けれど、その人がどう死んだのかは、書けない。
六 もう一つの道
1954年の夏、あの機械に戻ろう。
判定法はあった。機械もあった。それでもデイヴィスは、すぐに壁に突き当たる。紙の上では数段階の方法が、機械に載ると、まず式を所定の標準形に直すことを要求する。その書き換えで式が膨らむ。条件どうしの組合せが何層にも積み重なり、もとは短い一行が、何倍もの長さになって出てくる。1,024ワードのメモリは、たちまち足りなくなった。後に彼が、もっと複雑な判定プログラムに期待しなくなったのは、この経験からだった。
判定できることと、その代金を払えることは違う。この機械が初めて、それを目に見える形にした。
2年後、反対側から取り組む人々が現れた。RANDのニューウェルとショー、それにカーネギー工科大学のサイモンが、論理の定理を証明するプログラムを作った。対象は、ホワイトヘッドとラッセルの『プリンキピア・マテマティカ』冒頭の命題群である。結果を保証する手順を一律にたどるのではなく、探す道を選ぶ。目標に近そうな道を先に進み、枝分かれが多すぎればいくらか刈り込む。見つかれば、証明を出す。見つからなければ、見つからなかったとしか言えない。「見つからない」と「存在しない」の間にあるもの。それが、デイヴィスの機械にはあって、このプログラムにはない保証だった。「人工知能」という名が生まれてから、まだ1年もたっていなかった。
片方は答えを保証するが、たちまちメモリを使い果たす。もう片方は、メモリを使い果たさないために、必ず証明を見つけるという保証を手放す。ただし、見つけた証明は、依然として信頼できる推論規則に従っていなければならない。ここで道は二つに分かれた。
その分かれ道に、一人の中国人が立っていた。王浩は1921年に済南で生まれ、昆明の西南連合大学を卒業し、後にアメリカで数理論理学を研究した。1958年の夏、ニューヨーク州ポキプシーにあるIBMの研究所で、当時の大型計算機を使って、いくつかのプログラムを書いた。その一つは、『プリンキピア・マテマティカ』の最初の5章にある200あまりの定理を、一つ残らず証明した。所要時間は全部で約37分。その13分の12は読み込みと印刷に費やされ、証明そのものに使われたのは3分足らずだった。
彼は結果を一本の論文にまとめた。題名は「機械化された数学へ」とでも訳せる。かつてヒルベルトたちが抱いた願いを、言い換えたような響きがある。その論文には、遠慮のない一節がある。ニューウェルたちはヒューリスティックとアルゴリズムを比較しているが、比較相手に選んだのは、ひどく愚鈍なアルゴリズムだというのだ。とりわけ効率の悪いアルゴリズムを持ち出して、ヒューリスティックの優位を論じる。それは公平とは言いがたい、と王浩は書いた。
そこから彼は、もう一つの教訓を引き出した。かなり豊かな領域であっても、実際に証明される定理の大半は、その領域が持つ力のほんの一部しか使っていない。言えることが少ないのが、機械による判定の前提になる。ところが人間が本当に証明したいことも、たいていは初めから、そのわずかな力で足りているのだ。
1983年、王浩は機械による定理証明の最初のマイルストーン賞を受けた。賞を設けたのは国際人工知能合同会議だった。それからさらに20年近くたち、デイヴィスがこの草創期の歴史を書いたとき、題の下にはこう添えられていた。王浩を偲んで。
七 代金は別勘定
分かれた二つの道は、その後それぞれ20年近く続いた。
ヒューリスティックの道ではプログラムが増え、約束も大きくなっていった。1973年、イギリスの科学研究評議会は、応用数学者ライトヒルに人工知能の総合的な評価を依頼した。その報告には、ある言葉が繰り返し現れる。組合せ爆発。小さく、余計なものを取り除いた問題では、プログラムはよく働く。ところが現実の世界の規模に持ち出すと、探索すべき可能性が増えすぎて、とても最後までたどれなくなる。
翌年、もう一方の道から、さらに冷たい知らせが届く。1974年、フィッシャーとラビンが問うたのは、プレスバーガーの方法が速いかどうかではなかった。どんな方法を考えたとしても、根本的にずっと速くする余地はあるのか。答えは、ない。この算術では、誰がどんな一般的な方法を設計しても、厄介な式が必ずある。入力が少し長くなるたびに、必要な手順の数は二乗されていく。二重指数の下界と呼ばれるものだ。1978年にはオッペンが上界を与え、この問題は、上下にそびえる二つの高い壁の間に挟まれた。
その長さの式が、どれもそれほど難しいという意味ではない。どんな一般的な方法にも、そういう最悪の入力があるという意味だ。プログラムの書き方がまずいのでもない。問題そのものが持つ性質なのである。フィッシャーとラビンは、証明の長さについても論じた。適切な条件のもとでは、証明できる文であっても、証明自体が途方もなく長くならざるをえない。こうして、決定できること、証明できること、そして人間が最後まで読める証明を実際に手にできることも、三つの別の事柄になった。
二つの道は、同じ壁の前で再会した。ライトヒルが語ったのは、ある分野が現実世界の規模に広がるとぶつかる壁だった。フィッシャーとラビンが語ったのは、最小限に切り詰め、余計なものを除き、最も確かな保証を得た算術の一角に退いても、この壁はそこにある、ということだった。
実数の側でも、同じ話が繰り返される。タルスキの方法は判定法の存在を証明したが、現実に走らせられるアルゴリズムではなかった。実用に足る最初の完全な方法は、通常、1975年のコリンズの仕事に求められる。多次元の実空間を有限個の部分に分け、入力された多項式の符号が、各部分の中では変わらないようにする。すると、無限個の点についての問いが、有限個の部分ごとに代表を調べる問題へ変わる。この方法は後に数式処理システムの基礎となった。だが、分割される部分の数は、変数の個数に対して二重指数的に増えることがある。1988年、ダヴェンポートとハインツは、それも単にこの方法の欠陥ではないと証明した。実数上の一般的な量化子消去そのものに、この規模の難しさがあるのだ。その後、数十年にわたる改良の主眼は、下界を覆すことではなく、不要な仕事を減らすことにあった。射影を工夫し、目の前の問題に本当に必要な領域だけを分割するのである。
幾何学の側には、別の買い方を選んだ人がいた。1976年から1977年にかけて、呉文俊は北京で、幾何学の定理の証明を計算機に載せ始めた。後年、ある叢書の序文で、タルスキの機械化に関する定理は初等幾何学の広範囲を覆うが、効率が低すぎる、と彼は書いている。呉の方法では、幾何学の問題を多項式の等式の集まりに直して処理する。大小の順序を扱う命題は、ひとまず脇に置く。問える範囲を少し狭めたら、機械が動くようになった。こうして、決して自明ではない幾何学の定理が、いくつも機械によって証明された。
呉はこれを「数学の機械化」と名づけ、着想は中国古代の数学から得たと語った。『九章算術』と、西暦263年に劉徽が著したその注釈は、彼にとって、東洋における数学機械化の算法体系を代表する古典だった。第5回に登場した劉徽が、ここで20世紀の数学者から先達と認められる。同じ序文には、王浩の機械が3分で200あまりの命題を証明したことも記されている。
だから、決定可能であることと、使いものになることの間には隙間がある。数学でいう決定可能性は、統一された方法があり、いつか必ず停止して正解を出せるかを問う。何秒とは約束しない。100年以内とも約束しない。この宇宙で使える資源をすべて注いでも終わるとは、約束しない。工学でいう実用性が問うのは、実際に出会う問題に対して、与えられた機械、時間、メモリのもとで、しばしばすばやく役に立つ結果を返せるか、ということだ。一方の答えが「はい」で、他方が「いいえ」でもおかしくない。実際、そうなることは多い。
逆もまた成り立つ。最悪の場合がひどいからといって、役に立たないわけではない。理論上の最悪計算量は惨憺たるものでも、現実に処理したい問題にはかなり有効な判定プログラムは多い。王浩の教訓が、ここでも顔を出す。実際に出会う問題の大半は、あの最悪の片隅にはいない。
八 三つの欄の帳簿
題に戻ろう。閉じた体系は買えるのか。買える。しかも二度、買えた。二度とも、手に入ったものは違っていた。
プレスバーガーが手にしたのは、完全で、しかも決定可能な整数算術の一部分だった。代わりに、その中では数論の広大な領域を語れなくなった。タルスキが手にしたのは、実数代数と、それに連なる初等幾何学の統一的な判定法だった。彼は何も削っていない。代償は別のところにある。その言語はもともと、「この数は整数である」と言えないのだ。もちろん、どちらも市場で買い物をしたわけではない。具体的な数学的対象を調べてみたら、その対象がたまたまとても整っていた。「買う」と見えるのは後から振り返る私たちの見立てであって、当人たちが代金を払っていたのではない。
この二つの成果が最も長く生き続けたのは、後に発展する二つの分野だった。タルスキの量化子消去はモデル理論の基本技術となり、実数と代数閉体は、その教科書の最も基本的な例になった。一方、プレスバーガー算術はプログラムの検証へ入っていった。プログラムが正しいかどうかは、配列の添字、ループの回数、整数間の線形関係に左右されることが多い。まさにこの算術が得意とする言葉だ。1972年、クーパーはプレスバーガーの方法を、計算機上で実用的な形に作り直した。論文の題は「乗法のない算術における定理の証明」。『マシン・インテリジェンス』という叢書に掲載された。今日、数学者の証明を一行ずつ照合するプログラムの中には、「プレスバーガー算術の決定手続き」と銘打った専用の機能を持つものがある。その中で働いているのが、クーパーの方法だ。
では、この話から何を持ち帰ればよいのか。
自分の言語で言えるすべての文に答えを持つ。体系の力量を示す話に聞こえる。同時にそれは、一枚の一覧表でもある。そこに書かれているのは、その体系には言えないことだ。一つの体系を見定めるなら、まず答えられない問いを数え、それから答えられる問いを数えるとよい。何にでも答えられるのは、たいてい、問うていることが少なすぎるからだ。
1954年のあの機械以来、問いに答えるために造られた機械は、どれも同じ帳簿につけられる。帳簿には欄が三つある。一つは、何を問えるか。一つは、答えに保証があるか。そしてもう一つは、一回答えるために、どれほどの代価を払うか。
プレスバーガーの10ページはこう言っている。問える範囲の欄を十分に狭めれば、保証の欄はすべて埋められる。タルスキの本のあの一節と、1936年のチャーチとチューリングの結果が言っているのは、問える範囲を整数の加法と乗法まで広げたら、保証の欄はもう埋め尽くせない、ということだ。そしてフィッシャーとラビンは言う。問える範囲をプレスバーガーほどに絞り、保証をすべて埋めても、代価の欄には、なお払えない額が載ることがある。
デイヴィスの機械は保証を埋め尽くし、代価にぶつかった。1956年のプログラムは保証に空欄を残して、代価を下げた。王浩は同じ領域で保証の欄を埋め、代価も払える額に収めた。その領域が十分に小さかったからだ。呉文俊は幾何学で問えることの一角を削り、代価を払えるようにした。その後の機械も、三つの欄の間を行き来し続けている。あるものは保証を守りながら、問える範囲を少しずつ外へ広げる。デイヴィスが後にパトナムらと作った方法は、論理的な条件の集まりを同時に満たせるかどうかを専門に判定する。その子孫は、チップやソフトウェアの検証に広く使われるようになった。あるものは、問える範囲を大きく広げ、保証の欄を空けておく。後に人工知能と呼ばれるもののかなりの部分は、そういう勘定になっている。
三つの欄が同時に埋まったページを、書けた人はいない。そのうち、問える範囲と保証を同時に埋め尽くせないことは、定理が告げている。
この回には、戦争のために印刷所の手前で足止めされた本があり、戦争の中で途切れた一人の生涯がある。原稿は後に見つかった。だがプレスバーガーの最期の日々には、疑問符のついた年だけが残った。次回は時計を1933年へ戻し、ある大学へ向かう。
数の計算は、今も先へ進んでいる。けれど、何を数学に数え入れるのか。その勘定には、まだ決着がついたことがない。
史料と、さらに読むために
以下の資料は、本文の歴史的な細部や解釈の分かれる点に対応する。収蔵資料の記録、古代の文学的記述、現代の再構成は、同じ種類の証拠ではない。