チューリングマシン：計算の基礎

チューリングマシン：計算の基礎

計算機の原点

計算機、今で言うコンピュータの仕組みを知る上で、チューリング機械は欠かせません。この機械は、イギリスの数学者、アラン・チューリングが１９３６年に考えた計算の模型です。後のコンピュータ作りに大きな影響を与え、今の情報化時代を築く土台となる役割を果たしました。

チューリング機械は簡単な作りでありながら、どんな計算でもこなせる力を持っています。無限に続くテープと、そのテープに記号を読み書きする装置からできています。装置は、テープの記号を読み取り、内部の状態に応じて記号を書き換えたり、テープ上を移動したりします。計算は、この読み書きと移動を繰り返すことで行われます。例えば、足し算をする機械、掛け算をする機械、それぞれに合わせた動きの手順を定めることで、様々な計算に対応できるのです。これは、計算という行為の本質を捉え、理論的に分析できる画期的な考えでした。

一見すると単純なこの機械ですが、どんな複雑な計算でも手順を踏めば実行できるという事実は驚くべきことです。この事実は、計算するとはどういうことかを深く考えるきっかけを与え、計算の限界についても探求する道を開きました。また、チューリング機械は、現実のコンピュータの動作原理を理解する上でも役立ちます。私たちの身の回りにあるコンピュータは、様々な部品で構成され、複雑なプログラムを動かしていますが、基本的な動作はチューリング機械と同じです。データを読み込み、処理し、結果を出力するという流れは、チューリング機械のテープへの読み書きと移動に対応しています。

つまり、チューリング機械は、現代のコンピュータの基礎となる理論を提供していると言えるのです。この機械を学ぶことで、コンピュータがどのように計算を実行しているのかを根本から理解することができ、情報技術への理解もより深まるでしょう。

構造

計算機科学において礎となる概念であるチューリング機械は、驚くほど単純な構造を持ちながら、あらゆる計算を実行できる能力を秘めています。この機械は、主に三つの部分から成り立っています。

まず、情報を記録するためのテープがあります。このテープは、左右どちらの方向にも無限に伸びており、たくさんの小さな区画に分かれています。それぞれの区画には、あらかじめ決められた記号を書き込んだり、消したりすることができます。まるで、無限に長い巻物に、一つずつ文字を書き込んでいくような様子を思い浮かべると分かりやすいでしょう。このテープこそが、計算を行うための情報の保管場所となります。

次に、機械の頭脳とも言える有限制御部があります。これは、機械全体の動作を制御する重要な部分です。有限制御部は、機械が現在どのような状態にあるかを把握し、テープから読み取った記号に基づいて、次に行うべき動作を決定します。例えば、「テープから記号を読み取る」、「記号を書き込む」、「テープ上を移動する」、「状態を変える」といった指示を、あらかじめ決められた規則に従って実行します。まるで、計算の手順書を読みながら、指示に従って計算を進めていく人のようです。

最後に、テープを読み書きするヘッドがあります。ヘッドは、テープ上を左右に移動し、現在見ている区画の記号を読み取ったり、新しい記号を書き込んだりします。まるで、巻物の上を指でなぞりながら、文字を読んだり書き込んだりする人の手のようです。

これらの三つの要素、すなわち無限に伸びるテープ、制御を行う有限制御部、そして記号を読み書きするヘッドが協調して動作することで、チューリング機械は複雑な計算を可能にしています。一見単純な構造ですが、その組み合わせは無限の可能性を秘めており、現代の計算機科学の基礎を築く重要な役割を果たしています。

動作

計算機の基本的な働きを真似た仕組みであるチューリング機械は、時間を細かく区切って動きます。これは、まるで歯車が規則正しく動く時計の針のように、一つ一つの動作が順番に行われることを意味します。それぞれの瞬間を「時刻」と呼ぶことにしましょう。時刻が一つ進むごとに、機械の「読み書きヘッド」と呼ばれる部分が活躍します。読み書きヘッドは、テープと呼ばれる記録媒体に書かれた記号を一つずつ読み取ります。テープには、たくさんの升目が並んでいて、それぞれの升目に記号を書き込むことができます。まるで、計算用の紙に数字や記号を書き込むようにです。

読み書きヘッドは、現在見ている升目に何が書かれているかを調べ、機械の頭脳である「有限制御部」の状態と見比べます。有限制御部は、機械全体の動作を指示する役割を持ち、現在の状態に応じて次に何をするかを決定します。この状態は、機械がどんな計算をしているのか、どの段階にあるのかを表す重要な情報です。

ヘッドは、読み取った記号と有限制御部の状態に基づいて、三つの動作を行います。まず、現在見ている升目に新しい記号を書き込みます。これは、まるで鉛筆で数字を消して別の数字を書き込むような作業です。次に、ヘッドはテープの上で左または右に一ますだけ動きます。最後に、有限制御部の状態を更新します。これは、計算の次の段階に進むための準備です。

機械はこの三つの動作を、決められた手順に従って繰り返し行うことで計算を進めます。それぞれの動作は、あらかじめ「遷移規則」として定められています。この遷移規則は、機械の設計図とも言える重要な部分で、どのような計算を行うかを決定づけます。適切な遷移規則を設定することで、足し算や掛け算のような単純な計算から、複雑な問題の解決まで、様々な処理を行うことができます。まるで、様々な部品を組み合わせることで色々な機械を作ることができるように、遷移規則を工夫することでチューリング機械は多様な計算を実行できるのです。

計算の可能性

計算とは、決められた手順に従って答えを求めることです。その手順を書き表したものが、計算手順書、つまり「算法」です。この算法に従って、様々な問題を解くことができる機械、それが計算機械です。計算機械の中でも、あらゆる計算可能な問題を解くことができるとされているのが、チューリング機械です。チューリング機械は、イギリスの数学者、アラン・チューリングによって考え出されました。

チューリング機械は、無限に長いテープと、そのテープを読み書きするヘッド、そして機械の内部状態を記憶する装置からできています。テープには、計算に必要な情報が記号として書き込まれています。ヘッドは、テープを読み取り、その記号と機械の内部状態に応じて、記号を書き換えたり、テープ上を移動したり、内部状態を変更したりします。この一連の動作を繰り返すことで、計算を進めていきます。

チューリング機械で計算できる問題は、どんなものでも計算機で計算できると考えられています。これは、チャーチ＝チューリングのテーゼと呼ばれています。例えば、足し算、引き算、掛け算、割り算のような計算はもちろん、もっと複雑な計算手順で答えを求める問題も、チューリング機械なら解くことができます。

チューリング機械は、数字だけでなく、文字や記号も扱うことができます。適切な記号表現を用いれば、文章の処理や記号を使った計算も可能です。このことから、チューリング機械は非常に幅広い問題を扱うことができる、汎用性の高い計算の仕組みであることが分かります。計算機科学の基礎となる重要な考えであり、現代の計算機の理論的な土台となっています。

関数の計算

計算機械としてのチューリング機械は、関数も計算できます。関数は、入力された値に対して、一定の規則に従って対応する値を出力するものです。この動作をチューリング機械で行うには、まず入力となる値をテープ上に表現します。例えば、数を表現する場合には、テープ上に印を付けることで、その数を表すことができます。一つの印が「１」を表し、二つの印が「２」を表すといった具合です。

次に、チューリング機械の規則を、計算したい関数に対応するように設定します。例えば、入力された数を二倍にする関数を計算したい場合、機械はテープを読み込みながら、印を見つけたら、その隣に新しい印を追加していくように設定します。これにより、元の印の数の二倍の印がテープ上に作られ、二倍の値が計算されます。

二つの数の足し算を行う関数も、チューリング機械で計算できます。二つの数をテープ上に、区切り文字を使って並べて書き込みます。機械は、最初の数の印を一つずつ消しながら、同時に二番目の数の右側に新しい印を一つずつ追加していく規則に従います。最初の数の印を全て消し終わると、テープ上には二つの数の合計を表す印が残ります。このようにして、足し算が実現できます。

少し複雑な関数であっても、数の表現方法や規則を工夫することで、チューリング機械で計算することができます。これは、現代の計算機が行っている計算の基礎となる動作と同じです。つまり、プログラムと呼ばれる命令の集まりによって様々な計算を行う現代の計算機の動作は、本質的にはチューリング機械の動作と同じと言えるのです。このことから、チューリング機械が現代の計算機の理論的な土台となっていることが分かります。

理論と実際

計算の仕組みを根本から理解するためには、現実の機械にとらわれずに、計算そのものの本質を探ることが重要です。そのために考え出されたのが、チューリング機械と呼ばれる理論上の計算模型です。チューリング機械は、現実世界に存在する機械ではありません。頭の中だけで想像できる、理論上の存在です。しかし、現代の電子計算機の設計思想の根底には、このチューリング機械の考え方が深く関わっています。

チューリング機械は、いくつかの部品から成り立っています。まず、無限に続くテープがあります。このテープには、いくつかの記号が書き込まれており、機械はこの記号を読み書きすることで計算を行います。次に、テープの上を動く読み書きヘッドがあります。このヘッドは、テープの記号を読み取り、書き換え、そして左右に移動することができます。そして、機械の動作を制御する制御部があります。制御部は、現在の状態と読み取った記号に応じて、ヘッドの動作を指示します。

電子計算機の主要部品である中央処理装置は、チューリング機械の制御部に似た役割を持っています。そして、電子計算機の記憶装置は、チューリング機械のテープに相当します。プログラムは、チューリング機械の状態遷移の規則に対応し、計算の手順を定めます。つまり、電子計算機で行われる計算は、チューリング機械の動作を模倣していると言えるのです。

チューリング機械は、計算の本質を抽象化することで、複雑な電子計算機の動作原理を分かりやすく説明する道具となります。現実の機械の物理的な制約にとらわれずに、計算の可能性と限界を探ることができるため、計算機科学の理論的な基礎を築く上で重要な役割を果たしています。計算とは何か、計算できることとできないこととは何か、といった問いに答えるための、強力な道具を提供してくれるのです。