講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
本セミナー「チューリングマシンを学ぼう！」は、2021年1月29日に開催されたマルレク基礎シリーズの一講義です。コンピュータ・サイエンスの根本的な問いである「計算とは何か」を探求するために、その理論的基盤を構成するチューリングマシンを取り上げています [p.2]。
チューリングマシンは、テープの上をヘッドが左右に移動しながら文字を読み書きするという、極めて単純なモデルです。しかしこの単純さこそが本質であり、現代のあらゆるコンピュータと「計算能力」において同等であることが知られています。講師は初学者を念頭に置きつつ、同時に過去にこのテーマを学んだことのある方にも知識の再整理として役立てることを目指しています [p.2]。
セミナーは三部構成をとっています。第一部では「テープ」と「ヘッド」という物理的部品の機能解説から始まり、チューリングマシンの最重要概念である「状態」と「状態の遷移」の仕組みを丁寧に展開します [p.3]。第二部ではいよいよプログラミングに踏み込み、命令の表記法を導入したうえで、文字列の長さの計算、偶奇判定、文字列コピーといった具体的なプログラム例を通じて、変数も配列も関数もないプリミティブな計算モデルが日常のプログラミングと本質的に同じものであることを示します [p.4]。第三部では複数のテープを持つ拡張モデルへと議論を広げ、さらに複数のチューリングマシンが協調動作する様子、コントローラとエグゼキュータによる1ステップ実行制御という発展的テーマを扱います [p.5]。
本セミナーで扱いきれなかった「計算可能性」「計算複雑性」との深い繋がりは後日の「マルゼミ」に委ねられており、本セミナーはその前提となる強固な直観と技術的基礎を構築することを目的としています [p.5]。Interactive Proofを初めて定式化したGoldwasserらの論文図は、複数のチューリングマシンと複数のテープが現実の理論研究においてどのように用いられるかを示す具体例として冒頭に紹介されており [p.6]、抽象的なモデルが最先端の計算理論に直結していることを示す好例となっています。
講義のロードマップ
ここでは、セミナーの講演資料がどのようなパートから構成されているかを示します。また、それぞれのパートのポイントを紹介します。
■ Part I: チューリングマシンの基礎
チューリングマシンの「テープ」と「ヘッド」という二つの物理的部品がどのように機能するかを視覚的に理解させ、続いて「状態」と「状態の遷移」という概念的核心へと誘導します。ヘッドが文字を読み書きしながらテープ上を移動するにつれ、マシンの状態が変化していくという動作イメージを確立することが、この部の最重要目標です [p.9]。
■ Part II: チューリングマシンをプログラムする
チューリングマシンの「命令」を5要素の組（現在状態・読み文字・書き文字・移動方向・次状態）として定式化し、文字列表記 `State Read→Write:Direction NextState` を導入します。この記法のもとで具体的なプログラムを記述し、チューリングマシンが現実の計算問題を解決できることを実証します [p.112, p.128]。
■ Part III: 複数のテープと複数のマシン
命令の表記を `(n)State Read→Write:Direction (m)State’` へ拡張することで複数テープを自然に扱えるようにします。さらに二台のチューリングマシンを「並列（M1⊗M2）」または「直列（M1∘M2）」に組み合わせる理論を展開し、最後にControllerとExecuterの役割分担による1ステップ実行制御という高度なアーキテクチャを構築します [p.180, p.187]。
ページのナビゲート