アラン・チューリングとネガティブ思考の力

この物語 のオリジナル版はQuanta Magazineに掲載されました。

アルゴリズムは至る所に浸透しています。通勤を最適化し、支払いを処理し、インターネットトラフィックの流れを調整します。正確な数学的表現で表現できるあらゆる問題には、少なくとも原理的にはそれを解決できるアルゴリズムが存在するようです。

しかし、そうではありません。一見単純な問題でも、アルゴリズムでは決して解けないことがあります。コンピュータ科学者のパイオニアであるアラン・チューリングは、約1世紀前、現代のコンピュータサイエンスの礎となった計算の数学的モデルを定式化した論文の中で、そのような「計算不可能な」問題の存在を証明しました。

チューリングはこの画期的な結果を、直感に反する戦略を使って証明しました。つまり、解決しようとするあらゆる試みを単純に拒否する問題を定義したのです。

「何をやっているのかと聞かれたら、『いいえ、違うことをやります』と答えます」と、マサチューセッツ工科大学で理論計算機科学を研究する大学院生、ラフル・イランゴ氏は言う。

チューリングの戦略は、輝かしい歴史を持つ対角化と呼ばれる数学的手法に基づいていました。ここでは、彼の証明の背後にある論理を簡潔に説明します。

弦理論

対角化は、それぞれが 0 または 1 になるビットの文字列を含む日常的な問題を解決するための巧妙なトリックから生まれました。すべて同じ長さのそのような文字列のリストが与えられた場合、リストにない新しい文字列を生成できますか?

最も単純な戦略は、可能性のある文字列を一つずつ順番に検討していくことです。例えば、それぞれ5ビットの長さの文字列が5つあるとします。まず、リストをスキャンして00000を探します。もし00000が見つからなければそこで終わり、もし見つかれば00001に進み、この処理を繰り返します。これは非常に単純な方法ですが、長い文字列のリストが長くなると処理速度が遅くなります。

対角化は、欠落している文字列を少しずつ構築していく別のアプローチです。リストの最初の文字列の最初のビットを反転します。これが新しい文字列の最初のビットになります。次に、2番目の文字列の2番目のビットを反転し、それを新しい文字列の2番目のビットとして使用します。これをリストの最後まで繰り返します。反転するビットによって、新しい文字列は元のリストのすべての文字列と少なくとも1箇所は異なるようになります。（また、文字列のリスト全体に対角線を描くため、この手法の名前の由来となっています。）

対角化はリストの各文字列から1ビットを調べるだけで済むため、他の手法よりもはるかに高速です。しかし、その真の威力は無限大をいかにうまく扱えるかにあります。

「文字列は無限にでき、リストも無限にできる。それでもまだ機能する」とMITの理論計算機科学者ライアン・ウィリアムズ氏は語った。

この力を最初に活用したのは、数学の集合論という分野を創始したゲオルク・カントールでした。1873年、カントールは対角化を用いて、ある無限大が他の無限大よりも大きいことを証明しました。60年後、チューリングはカントールの対角化を計算理論に応用し、明らかに逆説的な色合いを与えました。

制限ゲーム

チューリングは、アルゴリズムでは解けない数学的問題、つまり入力と出力は明確に定義されているものの、入力から出力に至る確実な手順が存在しない問題の存在を証明しようとした。彼は、入力が任意の0と1の文字列で、出力が0か1のいずれかであるような決定問題に特化することで、この漠然とした課題をより扱いやすくした。

ある数が素数（1とその数自身でしか割り切れない数）であるかどうかを判定することは、決定問題の一例です。ある数を表す入力文字列が与えられた場合、正しい出力は、その数が素数であれば1、そうでなければ0です。もう一つの例は、コンピュータプログラムの構文エラー（文法上の誤りに相当）をチェックすることです。この場合、入力文字列は様々なプログラムのコードを表します（すべてのプログラムはこのように表現できます。なぜなら、コンピュータ上ではこのように保存され実行されるからです）。そして、目標は、コードに構文エラーがある場合は1を、ない場合は0を出力することです。

アルゴリズムは、あらゆる入力に対して正しい出力を生成する場合にのみ、問題を解決します。一度でも失敗すると、その問題に対する汎用アルゴリズムとは言えません。通常、まず解決したい問題を特定し、それからそれを解くアルゴリズムを探します。チューリングは、解決不可能な問題を探る中で、この論理を覆しました。彼は、あらゆる可能なアルゴリズムの無限リストを想像し、対角化を用いて、リスト上のすべてのアルゴリズムを阻止する難解な問題を構築したのです。

20問の不正なゲームを想像してみてください。回答者は特定の物を念頭に置いて始めるのではなく、それぞれの質問に「ノー」と言う言い訳を考え出します。ゲームが終わる頃には、その物に欠けている性質だけで、その物の特徴が説明されているのです。

チューリングの対角化証明はこのゲームの一種で、考えられるアルゴリズムの無限リストに対して「このアルゴリズムは計算不可能であると証明したい問題を解決できるか？」という質問を繰り返します。

「それは一種の『無限の質問』です」とウィリアムズは言った。

ゲームに勝つためには、チューリングはどのアルゴリズムに対しても答えが「ノー」となる問題を作る必要がありました。つまり、最初のアルゴリズムが誤った答えを出力するような特定の入力、2番目のアルゴリズムが失敗するような別の入力などを特定する必要がありました。彼はこれらの特別な入力を見つけるために、クルト・ゲーデルが最近「この命題は証明不可能である」といった自己言及的な主張が数学の基礎に問題をもたらすことを証明するために用いたトリックに似たトリックを用いました。

鍵となる洞察は、あらゆるアルゴリズム（あるいはプログラム）は0と1の文字列として表現できるという点です。つまり、エラーチェックプログラムの例のように、あるアルゴリズムは別のアルゴリズムのコードを入力として受け取ることができます。原理的には、あるアルゴリズムは自身のコードを入力として受け取ることさえ可能です。

この洞察により、チューリングの証明にあるような計算不可能な問題を定義できます。「アルゴリズムのコードを表す入力文字列が与えられたとき、そのアルゴリズム自身のコードを入力として0を出力する場合は1を出力し、そうでない場合は0を出力する。」この問題を解こうとするすべてのアルゴリズムは、少なくとも1つの入力、つまり自身のコードに対応する入力に対して誤った出力を生成します。つまり、この厄介な問題はいかなるアルゴリズムでも解くことができないということです。

否定ではできないこと

コンピュータ科学者たちは対角化をまだ終えていなかった。1965年、ジュリス・ハートマニスとリチャード・スターンズはチューリングの議論を応用し、すべての計算可能な問題が同じように作られているわけではないことを証明した。つまり、ある問題は他の問題よりも本質的に難しいのだ。この結果から、計算問題の難しさを研究する計算複雑性理論という分野が始まった。

しかし、複雑性理論はチューリングの逆法の限界も明らかにしました。1975年、セオドア・ベイカー、ジョン・ギル、ロバート・ソロベイは、複雑性理論における多くの未解決問題は対角化だけでは決して解決できないことを証明しました。中でも最も重要なのは、有名なP対NP問題です。これは、容易に検証可能な解を持つすべての問題が、適切な巧妙なアルゴリズムを用いれば容易に解けるかどうかを問うものです。

対角化の盲点は、それを非常に強力にする高度な抽象化の直接的な結果です。チューリングの証明は、実際に発生する可能性のある計算不可能な問題を一切扱っていません。その代わりに、そのような問題を臨機応変に作り上げたのです。他の対角化証明も同様に現実世界から乖離しているため、現実世界の詳細が重要な問題を解くことができません。

「彼らは遠隔で計算処理をします」とウィリアムズ氏は言う。「ウイルスを扱う人がグローブボックスを通してウイルスにアクセスするようなイメージです」

対角化の失敗は、P対NP問題の解決が長い道のりとなることを示唆する初期の兆候でした。しかし、その限界にもかかわらず、対角化は複雑性理論家にとって依然として重要なツールの一つです。2011年、ウィリアムズは対角化を他の多くの手法と組み合わせて、特定の制限された計算モデルでは極めて困難な問題を解くことができないことを証明しました。これは25年間も研究者を悩ませてきた結果です。P対NP問題の解決には程遠いものでしたが、それでも大きな進歩でした。

何かが不可能であることを証明したい場合、ただ「ノー」と言うことの力を過小評価しないでください。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。