teruji-kun Hirata-Juku...天才UFO

HOME | 道具・力学 | 熱・化学 | 電気・磁気 | 量子・相対論 | 電子・IT・新技術

* 電子・IT・新技術5:プログラム計算方式(1936年:チューリング、
1944年:フォンノイマン)

Q78:現在のコンピュータに実行出来ない情報処理(計算)はあるのだろうか?もしあるとしたら、それはどのような問題か?(かなり難問)

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

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

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

「無限長の(磁気)記録テープと記録再生ヘッドから成り、
 1)テープ記録区画上の記号aを読み取り、
 2)ヘッドが有する状態qとの演算出力bを同区画上に書き込み、ヘッド状態をpにし、
 3)ヘッドを左右区画に移動(m)か静止させる。」という動作を行うもの。

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

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

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

*NEXT

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

内部リンク

外部リンク