2 アルゴリズムとテューリング機械
第2章では、以後の議論で重要になるいくつかの概念について説明がなされている。「決定問題」、「テューリング機械」、「計算可能」などの概念がそれである。
「決定問題」は、ドイツの大数学者ダヴィット・ヒルベルトが提起した数学上の問題で、 「原理的に数学の（ある適当な仕方ではっきり定義された部類に属する）すべての問題を1つずつ解決できる一般的な機械的手続きは存在するか」（41頁）という問いである。分り易く言い換えるとすれば、どんな数学上の問題も自動的に解いてしまうプログラムは原理的に存在し得るか、ということになるだろう。
この「機械的手続き」を私達はまさにアルゴリズムと呼んでいるわけだが、やや意外なことに、「決定問題」が提起された当時の数学においては、その「機械的手続き」が何を意味するのかが明確でなかったという。
「テュー リング機械」は、コンピュータ科学者だったアラン・テューリングが1935-36年に導入した概念で、「決定問題」における「機械的手続き」の内容を明確 にし、「決定問題」に取り組むためのもの。「テューリング機械」は単なる概念であって物理的な機械ではないものの、そのアイディアは、まさに現在のコン ピューターと同じものと考えて差支えない。
本章では結局、ドイツで活躍した数学者ゲオルク・カントールの対角線論法の変形を適用し、数学的問題を決定する一般的なアルゴリズム（テューリング機械）はあり得ないことが示される。
細かい手続き的な部分についても相当の頁が割かれているが、これはおそらく、アルゴリズムといわれるものの具体的イメージを読者が抱けるようにとの配慮からだろう。そのため本章はそれなりの分量があるように見えるものの、その結論は上のようにシンプルである。
と ころで本章の最後には、アメリカの論理学者アロンゾ・チャーチによるラムダ算法なるものの短い説明がある。正直言って説明の中の数式を私はあまりよく理解 できなかったが、テューリング機械によるアルゴリズムの説明がやや物理的イメージによりかかり言葉による説明を要したものであったのに対し、ラムダ算法は それを完全に数式によって表現している点が重要なのであろう。
これでアルゴリズムが原理的に有する限界の一つが証明された。次の章からペンローズは、人間の意識活動がそうした限界を有するアルゴリズムの遂行としては説明できないことの議論へ進む。
第2章では、以後の議論で重要になるいくつかの概念について説明がなされている。「決定問題」、「テューリング機械」、「計算可能」などの概念がそれである。
「決定問題」は、ドイツの大数学者ダヴィット・ヒルベルトが提起した数学上の問題で、 「原理的に数学の（ある適当な仕方ではっきり定義された部類に属する）すべての問題を1つずつ解決できる一般的な機械的手続きは存在するか」（41頁）という問いである。分り易く言い換えるとすれば、どんな数学上の問題も自動的に解いてしまうプログラムは原理的に存在し得るか、ということになるだろう。
この「機械的手続き」を私達はまさにアルゴリズムと呼んでいるわけだが、やや意外なことに、「決定問題」が提起された当時の数学においては、その「機械的手続き」が何を意味するのかが明確でなかったという。
「テュー リング機械」は、コンピュータ科学者だったアラン・テューリングが1935-36年に導入した概念で、「決定問題」における「機械的手続き」の内容を明確 にし、「決定問題」に取り組むためのもの。「テューリング機械」は単なる概念であって物理的な機械ではないものの、そのアイディアは、まさに現在のコン ピューターと同じものと考えて差支えない。
本章では結局、ドイツで活躍した数学者ゲオルク・カントールの対角線論法の変形を適用し、数学的問題を決定する一般的なアルゴリズム（テューリング機械）はあり得ないことが示される。
細かい手続き的な部分についても相当の頁が割かれているが、これはおそらく、アルゴリズムといわれるものの具体的イメージを読者が抱けるようにとの配慮からだろう。そのため本章はそれなりの分量があるように見えるものの、その結論は上のようにシンプルである。
と ころで本章の最後には、アメリカの論理学者アロンゾ・チャーチによるラムダ算法なるものの短い説明がある。正直言って説明の中の数式を私はあまりよく理解 できなかったが、テューリング機械によるアルゴリズムの説明がやや物理的イメージによりかかり言葉による説明を要したものであったのに対し、ラムダ算法は それを完全に数式によって表現している点が重要なのであろう。
これでアルゴリズムが原理的に有する限界の一つが証明された。次の章からペンローズは、人間の意識活動がそうした限界を有するアルゴリズムの遂行としては説明できないことの議論へ進む。