AIっていうか、コンピューターは万能じゃない。
ChatGPTのあまりの有能ぶりに、なんかもう来るとこまで来ちゃったな…みたいな感じもあります。
でもAIがすべての知的作業をこなせるわけじゃない、と釘を刺す専門家もいます。
マサチューセッツ大学ローウェル校のコンピューター科学の教授、Jie Wang氏もそのひとり。なぜAIにできない問題があるのかを以下のように解説してくれました。
以下は、Creative Commonsライセンスの下で米Gizmodoに再掲されたものの翻訳です。
今日のコンピューターは、人工知能（AI）技術によって人間かと見まがうような会話ができ、作曲し、絵を描き、チェスや碁をプレイし、病気の診断までできます。
こうした成功は、コンピューターの能力に限界がないことを意味すると思われるかもしれません。でもそれが事実かを知るには、コンピューターの力とは何かを理解することが重要です。
コンピューターの力には、ふたつの側面があります。
ハードウェアが毎秒何回演算できるかということと、ハードウェア上で動くアルゴリズムの効率性です。
ハードウェアの速度は物理法則に規定されています。アルゴリズム、つまり命令のセットは、人間が書き、ハードウェアが実行できる計算シーケンスへと翻訳されています。
コンピューターの速度が物理的限界まで到達したとしても、計算にはまだアルゴリズムというハードルが残っています。
こうしたハードルには、コンピューターには解けない問題や、理論上は解けても現実的には今ある最高のコンピューターの能力を超えてしまう問題があります。
数学者やコンピューター科学者は、想像上の機械で問題を試すことで、その問題が解けるかどうかを判断しようとします。
想像上の計算機械
現代のアルゴリズムの概念はチューリングマシンと呼ばれ、1936年にイギリスの数学者、アラン・チューリングによって考案されました。
それは、紙と鉛筆で算術計算が行なわれる様子を模倣する想像上の機械です。チューリングマシンは、今あるすべてのコンピューターの原型となっています。
手書きだったら紙がたくさん必要になるような計算を担うため、チューリングマシンでの想像上の紙は無限だと想定されました。
それは、マス目が無限に連なった｢リボン｣または｢テープ｣で、マス目の中には空白か、記号ひとつが書かれています。
チューリングマシンをコントロールするのは有限のルール群で、テープの最初にある記号のシーケンスから処理を始めます。
マシンが実行できる処理は、隣のマス目に移動すること、記号を消去すること、空白に記号を書き込むことです。マシンはこの処理のシーケンスを実行することで計算していきます。
マシンが終了、または｢停止｣したら、テープ上に残る記号が出力、または結果となります。
チューリングマシンって何？
コンピューティングとは、イエスかノーの判断を求める場合が多くあります。
たとえ話でいうと、医学検査（というタイプの問題）では、患者から採った検体（問題のインスタンス）に、何らかの病気を示すもの（イエスかノーの答え）があるかどうかをチェックします。その事例が、チューリングマシンでは数字の形で表されていて、それが最初にある記号のシーケンスです。
ある問題が｢解決可能｣と考えられるのは、その問題のすべての事例について、結果がイエスかノーかにかかわらず｢停止｣できるよう、チューリングマシンを設計できる場合です。
またその場合、チューリングマシンが、事例による答えを正確に判断できる必要があります。
解けない問題もある
多くの問題はチューリングマシンで解くことができる、つまりコンピューターで解決できるのですが、そうじゃないものもあります。
たとえば中国系アメリカ人の数学者、ハオ・ワンが1961年に提起したタイル問題のひとつ、ドミノ問題は、コンピューターには解けません。
ドミノ問題では、グリッドにドミノの集合を敷き詰めるというタスクを考えます。
そのとき、多くのドミノゲームにならって、隣接するドミノの目を同じ数にする（訳注：ひとつのドミノには正方形がふたつあり、正方形にはサイコロのような1〜6までの目がある）ルールとします。
すると、最初にドミノの集合を与えられたとして、それがグリッドを完全に覆えるかどうかを判定できるようなアルゴリズムはない、とわかったのです。
合理的な時間で計算できるか
合理的な長さの時間で停止するアルゴリズムでも、解ける問題はたくさんあります。こうした｢多項式時間アルゴリズム｣は効率がよい＝コンピューターで解くのが実用的、とされています。
解決可能な問題ではあっても、多項式時間アルゴリズムが判明していないものが何千とあります。効率のよいアルゴリズムを求めて多くの努力がなされていますが、それでもわからないんです。
そんな問題のひとつに、｢巡回セールスマン問題｣があります。
巡回セールスマン問題では、点の集合があり、その一部が直接つながっている場合（これをグラフと言う）を想定します。その上で、どこかの点から出発して、すべての点を1回ずつ通過し、出発点に戻る経路があるかどうかを考えます。セールスマンが、ある地域のすべての家を一度ずつ経由して、出発点に戻ってくるのを想像してみてください。
巡回セールスマン問題は、行き先が数カ所以上になるとあっという間に手に負えなくなります。
こうした問題は｢NP完全問題｣と呼ばれ、1970年代初期にふたりのコンピューター科学者が別々に提起しその存在を示しました。
ひとりは米国系カナダ人のスティーブン・クック、もうひとりはウクライナ系米国人のレオニード・レビンです。
クックの研究のほうが先に発表されており、彼はこれによって1982年にコンピューター科学最高の栄誉であるチューリング賞を受賞しています。
正確に知ることのコスト
NP完全問題のよく知られたアルゴリズムは、要は可能な答えすべてを総当りで探していくものです。
数百カ所の点を持つ巡回セールスマン問題ともなれば、スーパーコンピューターでも計算に数年かかります。こうしたアルゴリズムは非効率、つまり数学的な近道がないということです。
実世界でこうした問題に対処する実用的なアルゴリズムは、概算を示すだけですが、その概算も改善はしています。
NP完全問題を解けるような、多項式時間アルゴリズムがあるかどうかは、21世紀初頭にクレイ数学研究所が｢ミレニアム懸賞問題｣として出題した7問のひとつになっています。
懸賞金は、問題ごとに100万ドル（約1億3000万円）です。
チューリングを超えて
チューリングのフレームワークを超えるようなコンピュテーションの形はありうるのでしょうか？
米国の物理学者でノーベル賞受賞者であるリチャード・ファインマンは 1982年、量子構造に基づくコンピュテーションというアイデアを提案しています。
量子コンピューターとは？
1995年、米国の応用数学者ピーター・ショアは、多項式時間内に整数を因数分解する量子アルゴリズムを提案しました。
数学者たちは、これはチューリングのフレームワークの多項式時間アルゴリズムでは解けないと考えています。
整数の因数分解とは、ある整数に関して、それを割り切れるような1より大きい整数を考えるということです。
たとえば整数688,826,081はより小さい整数25,253で割り切れます。688,826,081 = 25,253 x 27,277だからです。
RSAアルゴリズムは、ネットワークコミュニケーションの安全性を高めるために広く使われていますが、これは｢大きな整数の因数分解は計算上難しい｣という前提で成り立っています。
つまりショアの結論は、量子コンピューティングが実現すれば、サイバーセキュリティのあり方を変えてしまうことを示唆します。
完全な量子コンピューターができれば、整数の因数分解やその他の問題も解決できるのでしょうか？ その可能性はあると考える科学者もいます。
いくつかの研究者集団がそんな量子コンピューター開発を目指しており、小規模なものをすでに作ったグループもあります。
それでも、かつて発明された新技術がすべてそうであったように、量子コンピューティングに関してもほぼ確実に何らかの問題が浮かび上がり、それが次なる限界となってくることでしょう。
