チューリングマシンを学ぼう！
セミナー概要
「チューリング・マシン」は、今から80年以上前の1936年に、当時24歳だったアラン・チューリングが計算のモデルとして提案した、とてもシンプルな構造を持つ「マシン」です。ある意味、究極のRISCマシンです。
もちろん、その時代には、現在のようなコンピューターは、影も形もありませんでした。それにもかかわらず、チューリング・マシンは、コンピュータの働きの最も重要なモデルであり続けています。それは、驚くべきことです。
セミナーの前半で、次のような内容でチューリング・マシンの基本を学びます。
● テープとヘッッド
● 状態と状態の遷移
● チューリングマシンの命令とその実行
● 簡単なチューリングマシンのプログラム
セミナーの後半では、「万能チューリング・マシン」の話をします。万能チューリング U とは、どんなチューリングマシンMの実行も実行可能なチューリングマシンです。
具体的には、万能チューリングマシンUのテープの先頭には、あるチューリングマシンMの記述（Mの命令セット）が文字列として与えられていて、その後ろに、Mへの入力文字列が与えられます。こうした時、Uは、Mの出力文字列を出力します。
ノイマンが、固定されたハードウェアでプログラムを実装するスタイルから、メモリーにプログラムをロードする「ストアド・プログラミング」のスタイルを提唱したことはよく知られていますが、万能チューリングマシンのアイデアは、「ストアド・プログラミング」そのものであることは、もっと注目されていいことだと思います。
また、現代風に言えば、万能チューリングマシンUは、任意のチューリングマシンMに対するシミュレータであり、インタープリターです。セミナーでは、こうした万能チューリングを構成する上で必要な三つの準備をします。
一つは、チューリングマシンを複数のテープを持つように拡張すること。もう一つは、チューリング・マシンの入力にチューリングマシンのプログラムを与えるために、命令自体を文字列で与えるノテーションを与えることです。三つ目に、文字列として与えられた命令セットを「書き換えて」、別の働きをするチューリング・マシンの命令セットを生成すると言う手法を紹介します。
残念ながら、時間の制約で、「万能チューリングマシン」そのもののプログラムの提示は、割愛しました。
（2021/01/29 マルレク基礎）
