TENSAI-UFO．．．天才UFO vr2.0

Ｑ７８：現在のコンピュータに実行出来ない情報処理（計算）はあるのだろうか？もしあるとしたら、それはどのような問題か？（かなり難問）

　この限界論は現在でも正しい。そしてコンピュータには解けない問題が少なからず存在することを示している。つまり、「あらゆる数学的問題を解く究極のアルゴリズムは存在しない」のである。この事実は、人間の思考活動が機械によって完全には置き換えられない事を意味し、機械には負けないぞ、という安心感をもたらしたかもしれない。しかし、アルゴリズム化できる問題は想像以上に多く、実務上の問題はほとんどコンピュータ処理が可能であることもわかっている。ところでコンピュータはいつ誰が発明したのであろう。機械式アナログ計算機については、パスカルの項（道具・力学１５話）で紹介した。ここでは現在のコンピュータのベースである、プログラム式デジタル計算機の始まりを見ていくことにする。

　プログラム方式は意外なところから始まった、織機（はたおり機）である。1801年パンチカードを差し替える事で、自在の模様が織り込めるジャカード織機が誕生した（仏、ジャカール；1752-1834）。これは1720年代から現れ始めた自動デザイン織り機を改善実用化したものだが、ナポレオンが繊維産業奨励を行ったこともあり、産業機器として発展した。このパンチカードのコンセプトは1833年、英の数学者バベッジ（Charles Babbage、英、1791～1871年）が考案したプログラム式計算機に採用されることになる。当時、天文や航海などのため三角関数や対数の数表を使って多くの手計算がなされていた。しかし数表にも計算にも多くの誤りがあった上、単調で退屈な計算作業に不満がつのっていたのである。そこでこれらの計算を機械にやらせられないものかとバベッジは考えた。そして「差分法」を生かした簡潔で精度の高い関数計算ができるアルゴリズムを考案し、それを歯車式計算機で実現させる装置を発明する（1822）。彼は政府から莫大な資金を得る事に成功その実現を目指したが、当時の歯車精度の悪さのため完成を見なかった。しかしバベッジはさらに優れた装置「解析機関（1833）」を発明する、そしてこの解析機関が意外な支援者を得たのである。イギリスの-詩人バイロンの娘で伯爵夫人の数学愛好家エイダ・ラブレス（Augusta Ada King, Countess of Lovelace、英、1815～1852年）がこの装置に強い興味を持ち、バベッジの計算機について解説本を著したのだ。彼女はその中で2進法のアイディアを導入し、試作の為の資金援助まで行う。しかし再び不幸が起き、1852年、彼女の急死（享年37歳）によって資金が耐え、計算機はまたもや完成を見なかった。しかしこれこそがパンチカード式のプログラム・デジタル計算機の始まりと言える。

　20世紀に入り、計算機の本質とその限界について画期的な論文が1936年に現れた。アラン・チューリング（Alan Mathison Turing、英、1912～1954年）による（万能）計算機のモデル化とその数学的考察だが、モデル構成は信じられないほど単純である。それは当時発明されたテープレコーダからの類推で次のように成り立っている。、

それは「無限長の（磁気）記録テープと記録再生ヘッドから成り、
 １）テープ記録区画上の記号aを読み取る
 ２）ヘッドが有する状態qと入力aとの演算出力bを同区画上に書き込み、ヘッド状態をpにする
 ３）ヘッドを左右区画に移動（m）するか静止させる。以上の操作を連続的に静止するまで行う

　この操作を（q,a,p,b,m）と表記すると、驚くべきことに、あらゆる計算がこの組み合わせで実現され、最新コンピュータも全てこの規則の枠に収まってしまう事が分かっている。「チューリング・マシン」と呼ばれるこのコンピュータの原理的モデルは、当時のテープレコーダからの具体性を持った類推であるが、熱のカルノーサイクル（熱・化学１１話）に相当する究極の計算機モデルでもあったのだ。

　チューリングは両親がインド駐在中に妊娠しロンドンで1912年に誕生、兄と共に英国にいた父親の知人に育てられる。言葉は3週間で覚え、早期から数学とパズルに天才性を示した。高校時代、古典は嫌いで学ばず、数学と科学に熱中する。16歳でアインシュタインの論文を理解しこれに注釈を与えた。ケンブリッジ大で数学を学び23歳でフェロー称号を授与される。ただかなりの変人であり、かつゲイでもあった。1928年、数学の大御所ヒルベルトは「決定問題」を提言（与えられた論理が証明可能か否かを決定する手続きの有無を示す問題）。その重要性を感じたチューリングは計算機をモデル化（上記に書いた内容）し、このモデルによる「判定可能性」を調べる事で決定問題にチャレンジしたのである。そして1936年「計算可能数と決定問題への応用」という歴史的論文を発表、先のクイズの回答で示したように「そのような手続きは存在しない」という否定的な結論を出した。つまりどのような計算機でも処理できない問題が存在することが分かったのだ。ゲーデル（電子・IT４話）に遅れる事５年後の事であり、数学の真理を計算機モデルで分析できる事を示したと言えるだろう。チューリングはその後、暗号の問題などにも取り組み成果を上げたが、1952年同性愛者であることが知られ逮捕されてしまう。当時、同性愛は違法だったのだ。そして2年後の1954年「白雪姫」にちなみリンゴに青酸をひたして自殺する、41歳のことであった。（トランジスタ技術、2015年4月号に掲載）

宿題７８：チューリング・マシンがあらゆるコンピュータの理想マシンなら、それを実用化すれば立派なコンピュータができそうだが、なぜ実用化されていないのだろう？

NEXT

次は何を読もうか↓（下の目次か右側のリンクより選んで下さい）