チューリングマシンを学ぼう！

セミナー概要

「チューリング・マシン」は、今から80年以上前の1936年に、当時24歳だったアラン・チューリングが計算のモデルとして提案した、とてもシンプルな構造を持つ「マシン」です。ある意味、究極のRISCマシンです。

もちろん、その時代には、現在のようなコンピューターは、影も形もありませんでした。それにもかかわらず、チューリング・マシンは、コンピュータの働きの最も重要なモデルであり続けています。それは、驚くべきことです。

セミナーの前半で、次のような内容でチューリング・マシンの基本を学びます。
　●　テープとヘッッド
　●　状態と状態の遷移
　●　チューリングマシンの命令とその実行
　●　簡単なチューリングマシンのプログラム

セミナーの後半では、「万能チューリング・マシン」の話をします。万能チューリング U とは、どんなチューリングマシンMの実行も実行可能なチューリングマシンです。

具体的には、万能チューリングマシンUのテープの先頭には、あるチューリングマシンMの記述（Mの命令セット）が文字列として与えられていて、その後ろに、Mへの入力文字列が与えられます。こうした時、Uは、Mの出力文字列を出力します。

ノイマンが、固定されたハードウェアでプログラムを実装するスタイルから、メモリーにプログラムをロードする「ストアド・プログラミング」のスタイルを提唱したことはよく知られていますが、万能チューリングマシンのアイデアは、「ストアド・プログラミング」そのものであることは、もっと注目されていいことだと思います。

また、現代風に言えば、万能チューリングマシンUは、任意のチューリングマシンMに対するシミュレータであり、インタープリターです。セミナーでは、こうした万能チューリングを構成する上で必要な三つの準備をします。

一つは、チューリングマシンを複数のテープを持つように拡張すること。もう一つは、チューリング・マシンの入力にチューリングマシンのプログラムを与えるために、命令自体を文字列で与えるノテーションを与えることです。三つ目に、文字列として与えられた命令セットを「書き換えて」、別の働きをするチューリング・マシンの命令セットを生成すると言う手法を紹介します。

残念ながら、時間の制約で、「万能チューリングマシン」そのもののプログラムの提示は、割愛しました。

（2021/01/29 マルレク基礎）

講演資料「チューリングマシンを学ぼう！」 (ダウンロード)