チューリングの考えるキカイ 【書評・まとめ】 コンピュータにできることとできないこと

記事の内容

・チューリングのどんなアイデアが、コンピュータサイエンスの基礎になっているのか

・AIには何ができて何ができないのか

・「計算する」とはどういうことか

・万能チューリング機械でも、「計算できない問題」とは何か

コンピュータの発展は、現在の社会を支えている。

そのコンピュータの理論の背景にて、重要なアイデアを生み出したのがチューリングだ。

この記事では、彼の基礎的なアイデアを紹介したい。コンピュータに何ができて何ができないかを知ることは、AIに何ができて何ができないかを知るためにも重要だ。

チューリングの考えるキカイ　人工知能の父に学ぶコンピュータサイエンスの基礎

チューリングの考えるキカイ ~人工知能の父に学ぶコンピュータ・サイエンスの基礎

こちらの本から、いくつかのテーマをまとめたい。

機械の定義とは？

機械の定義・・・「質問したら答えを返すもの」

『計算機械と知性』と題された1950年の論文。この論文は次の文で始まる。

「機械は考えることができるか」という問題を考察してみよう。そのためには「機械」と「考える」という言語の意味を定義することから始めるべきだろう。

知性を構成するために、その働きの一部である「考える」に注目するのだ。そのためには、一つ一つの概念を厳密に定義する必要がある。「考える」という概念を定義するために、計算という概念を定義する。それでは、「計算する」ってなんだろう？

次の記事では、映画そのものと、その背景について解説している。

interaction.hatenadiary.jp

知能とは何か？

知能とはなんなのか、いろいろな観点がある。

ここでは、「問題が与えられた時、その問題をどのように解決しているか」ということに焦点をしぼる。

そして、問題を解く手順がアルゴリズム。アルゴリズムに関する理論を、計算の理論という。

チューリング機械

計算の本質をあぶり出したイメージ上の機械。

「アルゴリズムとは何か」「計算とは何か」という本質に迫る。

現在のコンピュータでできることは、すべてチューリング機械で再現できる。

チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。

計算理論 - Wikipedia

コンピュータにできることとは、有限のステップの計算だ、と言える。だから、計算の手順としてのアルゴリズムで表現できる問題を解くことができる。

ここでいう、「計算」ということの数学的な定義までは、この記事では深められない。

続いて、コンピュータにできないことを見ていこう。

ヒルベルト・プログラムと決定問題

・ヒルベルトプログラム

数学自身を対象にした理論を数学で作ろう。その数学が絶対に間違わないということを数学的に証明しよう。

・決定問題

「与えられた命題が定理かどうかを決定する有限的な手続きを見つけよ」

有限的な手続き、つまり、アルゴリズムがあるのだろうか？

アルゴリズムが存在しない！？

・ヒルベルトの第10問題

ディオファントス方程式を解くアルゴリズムが、存在しないということが証明されてしまった！！

数学界においては衝撃的。

数学史においても重要で、一般の数学の問題で、計算不能が見つかってしまった。

この計算不能という概念を、チューリングが1936年に、整理していた。

計算不能とは？

アルゴリズムが存在しない　＝　チューリング機械で計算できないこと

チューリング機械の停止問題

与えられた機械が正しい機械かダメな機械か判定せよ

答え

そのような仕分け機械を作ることはできない

これから発展して、チューリング機械の停止問題になる。

・停止性問題

「チューリング機械Mは、入力xの元で停止するか」を常に判定できる機械は存在するか？

重大な結論！！

仕分け機械問題も、チューリングの停止問題も計算不能。

「与えられたプログラムが停止する」ということを判断し停止するプログラムは書けない。どんなアルゴリズムでも実行できる万能チューリング機械でも、計算できない問題があるのだ。

そして、これらは本質的には、ヒルベルトの第10問題と同じ。

数学、計算、機械がつながっていく。「計算できない問題がある」という発見は、その後のコンピュータサイエンスの基礎として、発展の元になっていく。

停止性問題の証明方法、例えばなしは次のサイトが分かりやすい。

d.hatena.ne.jp

また、こちらのツイートもわかりやすいと思う。イラストがいい！！

停止問題の証明を4コマにしてみた。 pic.twitter.com/cD4JYAluZq

— ゆうな (@kawauSOgood) 2019年5月3日

また、この証明には対角線論法が使われる。これは、自己言及的な状況を作り出す。この自己言及構造として、本質が似ている定理が、ゲーデルの不完全性定理だ。

次の記事にまとめている。

interaction.hatenadiary.jp

チューリングが示したこと

・計算できない問題の存在

・機械の限界

・アルゴリズムの限界

AIには何ができて、何ができないか

コンピュータの理論や、AIの基礎の根底には、チューリング機械の数学的モデルがある。

「機械で計算できる問題かどうか」問題そのものを考えると、「問題を解くアルゴリズム自体がない」という領域もあることがわかる。

現在のIT社会、AIの可能性を考えていくためにも、とても重要な基礎だと思う。なぜならば、現在のコンピュータや、今後登場するであろうどんなコンピュータも、チューリング機械の能力は超えないのだ。

だから、もちろん、「AIには何ができて何ができないのか」これを考えるための基礎になる。

この重要さが伝わったならうれしい。