『チューリングの計算理論入門』
チューリング・マシンからコンピュータへ
高岡詠子＝著

シェアツイートブックマーク

メニューページはこちら

計算とはなにか？
コンピュータは、なぜ万能なのか？
チューリング・マシンは
止まるのか、止まらないのか？

まえがき

この本は、毎日のように私たちが使うコンピュータの原理である「チューリングの計算理論」を紹介します。

現在のコンビュータはいろいろなことができます。文書作成はもちろん、帳簿計算や名簿の管理をするだけではなく、絵も描け、写真や動画を編集することもできます。インターネットでメールも送れますしWebブラウザを使ってオンラインショッピングや銀行振り込みもできます。1台のコンビュータをいろいろな用途に使うことができる、これをコンビュータの万能性と言いますが、この「コンビュータの万能性」を保証する理論がチューリングの計算理論です。

コンピュータはハードウェアだけあっても、ソフトウェアがなければ動きません。今では当たり前のような話かもしれませんが、歴史をたどってみれば、17世紀に発明された計算する機械は歯車で動いていて、特定の計算をすることしかできませんでした。つまり、現在のようにソフトウェアを入れ替えていろいろな用途に使用することはできませんでした。違う計算をするためには、歯車自身の構成を変えなければならなかったわけです。

チューリングは、今で言うソフトウェアという概念を考えだしました。この本で紹介する、チューリングの『計算可能数とその決定問題への応用』が出版された1930年代に、ソフトウェアを入れ替えて、1台の機械にさまざまな計算を行わせるという考え方はとても斬新だったのです。計算機科学の分野におけるノーベル賞をチューリング賞と言いますが、それだけすばらしい功績であったことが分かります。

この本の主題はチューリングの計算理論なのですが、それがどのように現在のコンピュータにつながるのか、その道筋が分かるように本書を書きました。その大筋をここで書いておきます。

チューリングは、どんな計算でもアルゴリズムさえ書くことができれば計算可能なことを、チューリング・マシンという計算モデルを使って理論的（数学的）に示しました。しかし、具体的にどのような方法でアルゴリズムを書くかについては、何も残しませんでした。もちろん、物理的機械としてチューリング・マシンを作るなど、まだ非現実的なことでした。そのような中、シャノンは論理演算の理論であるブール代数を使えば、あらゆるアルゴリズムを「回路」という物理的な手段で表現できるというアイディアを出しました。その「回路」を電子回路で実現したのが、現在のコンピュータなのです。

それでは、チューリングの計算理論の世界への扉を開きましょう。

著者高岡詠子（たかおか・えいこ）

東京都に生まれる。慶應義塾大学理工学部数理科学科卒業、同大学大学院理工学研究科計算機科学専攻博士課程修了。千歳科学技術大学総合光科学部准教授等を経て、現在上智大学理工学部情報理工学科准教授。博士（工学）。国際基督教大学、明治学院大学非常勤講師。専攻は、計算機科学、データベース、プログラミング教育、情報教育。主な著書は『eラーニングからブレンディッドラーニングへ』（共著、共立出版）、『学びとコンピュータハンドブック』（共著、CIEC)など。